Niet homogene recursie
Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
- Berichten: 3.330
Niet homogene recursie
Los op:
\(a_{n+1}=2a_n+1\)
Volgens mijn verstand kan er niets bestaan en toch bestaat dit alles?
-
- Berichten: 7.068
Re: Niet homogene recursie
Ik gok:
Het ontgaat me op het moment even hoe je dit ook alweer in zijn algemeenheid moet oplossen...
\(a_n = 2^n \cdot a_0 + (2^n - 1)\)
Als ik deze gok controleer met volledige inductie dan blijkt hij te kloppen. Het ontgaat me op het moment even hoe je dit ook alweer in zijn algemeenheid moet oplossen...
- Berichten: 5.679
Re: Niet homogene recursie
Algemene regel: als
\(a_n = p \cdot a_{n-1}+q\)
, dan \(a_n = p^n \cdot a_0 + \frac{1-p^n}{1-p}q\)
.In theory, there's no difference between theory and practice. In practice, there is.
- Berichten: 3.330
Re: Niet homogene recursie
Vraag niet volledig.Ik herhaal de vraag:
\(a_{n+1}=2a_n+1\mbox{ en }a_0=0\)
Volgens mijn verstand kan er niets bestaan en toch bestaat dit alles?
-
- Berichten: 7.068
Re: Niet homogene recursie
Waarom vul je niet gewoon nul in in de antwoorden die je al gekregen hebt?Ik herhaal de vraag:
\(a_n = 2^n -1\)
- Berichten: 3.330
Re: Niet homogene recursie
EvilBro schreef:
Deze recursievgl. komt voor als men het minimum aantal verplaatsingen moet bepalen bij de torens van hanoi.
Ik had de antwoorden niet gezien. Als men dit oplost zoals een differentiaalvgl d.w.z. eerst de homogene en dan een particuliere oplossing zoeken van de algemene dan zult ge jouw oplossing vinden hoop ik.Waarom vul je niet gewoon nul in in de antwoorden die je al gekregen hebt?
Deze recursievgl. komt voor als men het minimum aantal verplaatsingen moet bepalen bij de torens van hanoi.
Volgens mijn verstand kan er niets bestaan en toch bestaat dit alles?
- Berichten: 24.578
Re: Niet homogene recursie
Inderdaad en de oplossing (u(n) = 2^n-1), zijn precies de Mersenne-getallen; bekend van onder meer priemgetallen van deze vorm.
"Malgré moi, l'infini me tourmente." (Alfred de Musset)
- Berichten: 84
Re: Niet homogene recursie
Op mijn site heb ik naar aanleiding van deze topic een goeie cursus geplaatst (onderaan de page) die o.a. oplossingsmethoden voor recurrenties omvat:
Mijn Webpage
Mijn Webpage
- Berichten: 3.330
Re: Niet homogene recursie
Los op:
\(a_{n+2}^2-5a_{n+1}^2+6a_n^2=7n\mbox{ en }a_0=a_1=1\)
Volgens mijn verstand kan er niets bestaan en toch bestaat dit alles?
- Berichten: 5.679
Re: Niet homogene recursie
Die bleek lastiger dan gedacht...kotje schreef:Los op:
\(a_{n+2}^2-5a_{n+1}^2+6a_n^2=7n\mbox{ en }a_0=a_1=1\)
Om te beginnen even de kwadraten wegdenken, krijg je een recursieve definitie
\(b_{n+2}=5b_{n+1}-6b_n+7n\)
(waarbij \(b_n=a_n^2\)
).Vervolgens werk je die factor n weg door
\(b_{n+3}-6b_{n+2}\)
te bekijken, dat is \(-11b_{n+1}+6b_n+7\)
(hangt niet meer af van n). Je kunt de recursie dus ook schrijven als: \(b_{n+3}=6b_{n+2}-11b_{n+1}+6b_n+7\)
Dan moet ook nog die losse factor 7 eruit: bekijk \(b_{n+4}-7b_{n+3}\)
, dat wordt \(-17b_{n+2}+17b_{n+1}-6b_n\)
Kortom, jouw vergelijking is hetzelfde als deze 4e-graads homogene recursie:\(b_{n+4}=7b_{n+3}-17b_{n+2}+17b_n-6b_n\)
.Karakteristieke veelterm is
\(x^4-7x^3+17x^2-17x+6=(x-3)(x-2)(x-1)^2\)
Daarom heeft \(b_n\)
een oplossing van deze vorm:\(b_n= 3^n c_1 + 2^n c_2 + 1^n(c_3+c_4 n)\)
voor onbekende \(c_i\)
Als we de eerste 4 oplossingen (\(b_0\)
t/m \(b_3\)
) invullen levert dit 4 vergelijkingen voor de 4 onbekende \(c_i\)
's. \(b_0=1\)
en \(b_1=1\)
zijn gegeven, met de hand reken je uit dat \(b_2=-1\)
en \(b_3=-4\)
, invullen geeft: \(b_n = (3\cdot 3^n-20\cdot 2^n+14n+21)/4\)
.Oplossing van de oorspronkelijke vergelijking is daarom:
\(a_n = \pm \frac{1}{2} \sqrt{3\cdot 3^n-20\cdot 2^n+14n+21}\)
(merk op dat \(b_2\)
en \(b_3\)
negatief zijn, en dus dat \(a_2\)
en \(a_3\)
imaginair zijn).In theory, there's no difference between theory and practice. In practice, there is.
- Berichten: 3.330
Re: Niet homogene recursie
Ik kom tot hetzelfde antwoord maar wel op de volgende manier:
Ik stel
Ik stel
\(b_n=a_n^2\mbox{ dan }b_0=b_1=1\)
1)Homogene vgl.\(b_{n+2}-5b_{n+1}+6b_n=0\)
oplossen geeft:\(b_n=c_12^n+c_23^n\)
2)Particuliere oplos.\(b_n^{(p)}=A+Bn\)
Invullen en uitrekenen geeft:\(b_n^{(p)}=\frac{7}{2}n+\frac{21}{4}\)
3)Algemene oplos.\(b_n=c_12^n+c_23^n+\frac{7}{2}n+\frac{21}{4}\)
Rekening houden met de begin voorwaarden krijgen we:\(b_n=\frac{-20}{4}2^n+\frac{3}{4}3^n+\frac{7}{2}n+\frac{21}{4}\)
De vierkantswortel hieruit trekken geeft de gevraagde oplossing.Volgens mijn verstand kan er niets bestaan en toch bestaat dit alles?
- Berichten: 3.330
Re: Niet homogene recursie
Los op:
\(a_n^2-2a_{n-1}=0\mbox{ },n\geq1\mbox{ },a_0=2\)
Volgens mijn verstand kan er niets bestaan en toch bestaat dit alles?
- Berichten: 3.330
Re: Niet homogene recursie
Evilbro schreef:
Ik zoek achter de algemene oplossing
Dit is een particuliere oplossing.\(a_n=2\)
Ik zoek achter de algemene oplossing
Volgens mijn verstand kan er niets bestaan en toch bestaat dit alles?
- Berichten: 5.679
Re: Niet homogene recursie
Voor iedere n iskotje schreef:Evilbro schreef:
Dit is een particuliere oplossing.
Ik zoek achter de algemene oplossing
\(a_k = 2\ (\forall k<n),\ a_n=-2\)
ook een oplossing, dat leidt dan vanaf n tot een andere reeksontwikkeling (bij iedere volgende stap steeds 2 mogelijkheden).In theory, there's no difference between theory and practice. In practice, there is.