Hvordan løse rekursjonslikninger

Aritmetikk

1. 1
   Betrakt en aritmetisk sekvens slik som 5, 8, 11, 14, 17, 20,....
2. 2
   Siden hver sikt er større 3 enn den foregående, kan den uttrykkes som et tilbakefall som vist.
3. 3
   Erkjenne at noen gjentakelse av formen a _n = a _n-1 + d er en aritmetisk sekvens.
4. 4
   Skriv den lukkede formen formel for en aritmetisk sekvens, eventuelt med ukjente faktorer som vist.
5. 5
   Løs for eventuelle ukjente avhengig av hvor sekvensen ble initialisert. I dette tilfelle, siden 5 var 0 ^th sikt, er formelen a _n = 5 + 3n. Hvis du i stedet, ville du fem å være den første periode, vil du få en _n = 2 + 3n.

Geometrisk

1. 1
   Betrakt en geometrisk sekvens slik som 3, 6, 12, 24, 48,....
2. 2
   Siden hver sikt er det dobbelte av den, kan den uttrykkes som et tilbakefall som vist.
3. 3
   Erkjenne at noen gjentakelse av formen a _n = r * a _n-1 er en geometrisk sekvens.
4. 4
   Skriv den lukkede formen formel for en geometrisk sekvens, eventuelt med ukjente faktorer som vist.
5. 5
   Løs for eventuelle ukjente avhengig av hvor sekvensen ble initialisert. I dette tilfellet, siden 3 var 0 ^th sikt, er formelen en _n = 3 * 2 ^n. Hvis du i stedet, ville du 3 for å være den første periode, vil du få en _n = 3 * 2 ^(n-1).

Polynom

1. 1
   Tenk sekvensen 5, 0, -8, -17, -25, -30,... gitt av rekursjon vist.
2. 2
   Enhver rekursjon av den form som er vist, hvor p (n) er en hvilken som helst polynomisk med n, vil ha en lukket form polynom av grad formel ett høyere enn graden av p.
3. 3
   Skriv den generelle form av et polynom av den nødvendige grad. I dette eksemplet er kvadratisk p, så vil vi ha en kubisk å representere en sekvens _N.
4. 4
   Siden en generell kubisk har fire ukjente koeffisienter er fire leddene av sekvensen som kreves for å løse det resulterende system. Hvilken som helst fire vil gjøre, så la oss bruke begreper 0, 1, 2 og 3. Kjøring av gjentakelse bakover for å finne den -1 ^th sikt kan gi en enklere system for å løse, men er ikke nødvendig.
5. 5
   Løs det resulterende system av grader (p) to ligninger i ° (p) = 2 ukjente som vist.
6. 6
   Hvis en var ett av vilkårene du brukte til å løse for koeffisientene, får du konstant løpetid polynom for gratis og kan umiddelbart redusere systemet til grader (p) en ligninger i grader (p) en ukjente som vist.
7. 7
   Løs systemet av lineære ligninger for å finne c ₃ = 1/3, _2-c = -5 / 2, c = ₁ -17 / 6, og c = 5. Presentere den lukkede formelen for en _n som et polynom med kjente koeffisienter.

Lineær

1. 1
   Dette er den første fremgangsmåte i stand til å løse de fibonacci sekvens i innledningen, men metoden løser noen regelmessighet hvor ^n-te sikt er en lineær kombinasjon av de tidligere k betingelser. Så la oss prøve den på annet eksempel vist som første leddene 1, 4, 13, 46, 157,....
2. 2
   Skriv den karakteristiske polynom av tilbakefall. Dette finner du ved å erstatte hver en _n i tilbakefall av x ⁿ og dividere med x ^(nk) forlater en monic polynom av grad k og en null konstant sikt.
3. 3
   Løs den karakteristiske polynomet. I dette tilfellet har den karakteristiske grad 2, slik at vi kan bruke den kvadratiske formelen til å finne sine røtter.
4. 4
   Enhver ekspresjon av den form som er vist tilfredsstiller rekursjon. C _jeg er noen konstanter og bunnen av eksponentene er røttene til den karakteristiske funnet ovenfor. Dette kan kontrolleres ved induksjon.
   • Hvis den karakteristiske har en multippel rot, er dette trinnet endret litt. Hvis r er en rot av mangfold m, bruke (c _en r ⁿ + c ₂ nr ⁿ + c ₃ n ^to r ⁿ +... + c _m n ^m-1 r ⁿ⁾ i stedet for bare (c _en r ⁿ⁾. For eksempel, rekkefølgen som starter 5, 0, -4, 16, 144, 640, 2240,... tilfredsstiller den rekursive relasjon et _n = 6a _n-1 - 12a _n-2 + 8a _n-3. Den karakteristiske polynom har en trippel roten av to og lukket form formelen a _n = 5 * 2 ^​​n - 7 * n * 2 ⁿ + 2 * n ² * 2 ^n.
5. 5
   Finn den c _jeg som tilfredsstiller de angitte startbetingelsene. Som med den polynomiske eksempel er dette gjort ved å lage et lineært system av ligninger fra de innledende betingelser. Siden dette eksempelet har to ukjente, trenger vi to begrepene. Enhver to vil gjøre, så ta 0 ^th og 1 ^st å unngå å måtte heve en irrasjonell nummer til en høy effekt.
6. 6
   Løs den resulterende system av likninger.
7. 7
   Plugg de resulterende konstantene i den generelle formel som løsning.

Genererer funksjoner

1. 1
   Betrakt sekvens 2, 5, 14, 41, 122... gitt av rekursjon vist. Dette kan ikke løses ved noen av de ovennevnte metoder, men en formel kan finnes ved hjelp av generering funksjoner.
2. 2
   Skriv den genererer funksjon av sekvensen. En genererer funksjonen er rett og slett en formell makt serie der koeffisienten til x ⁿ er n ^th term i sekvensen.
3. 3
   Manipulere generere funksjon som vist. Målet i dette trinnet er å finne en ligning som vil tillate oss å løse for den genererer funksjon A (x). Pakk den første perioden. Påfør gjentakelse forhold til de øvrige vilkårene. Splitte summen. Pakk konstant vilkår. Bruk definisjonen av A (x). Bruke formelen for summen av en geometrisk rekke.
4. 4
   Finn den genererer funksjon a (x).
5. 5
   Finn koeffisient x ^N i a (x). Metodene for å gjøre dette vil variere avhengig av hva A (x) ser ut, men metoden for partielle fraksjoner, i kombinasjon med å kjenne den genererer funksjon av en geometrisk sekvens, fungerer her som vist.
6. 6
   Skriv formelen for en _n ved å identifisere koeffisienten til x ⁿ i en (x).