Hur lösa återkommande relationer

Aritmetiskt

1. 1
   Betrakta en aritmetisk sekvens såsom 5, 8, 11, 14, 17, 20,....
2. 2
   Eftersom varje term är tre större än den tidigare, kan det uttryckas i en upprepning som visas.
3. 3
   Inse att en upprepning av formen a _n = a _n-1 + d är en aritmetisk sekvens.
4. 4
   Skriv den slutna formen formeln för en aritmetisk sekvens, eventuellt med okända som visas.
5. 5
   Lös för eventuella okända beroende på hur som sekvensen initieras. I detta fall, eftersom 5 var den ^{0: te} termen, är formeln a _n = 5 + 3n. Om istället, du ville 5 vara den första termen, skulle du få en _n = 2 + 3n.

Geometrisk

1. 1
   Betrakta en geometrisk sekvens såsom 3, 6, 12, 24, 48,....
2. 2
   Eftersom varje term är dubbelt föregående, kan det uttryckas i en upprepning som visas.
3. 3
   Inse att en upprepning av formen a _n = r * a _n-1 är en geometrisk sekvens.
4. 4
   Skriv den slutna formen formeln för en geometrisk sekvens, eventuellt med okända som visas.
5. 5
   Lös för eventuella okända beroende på hur som sekvensen initieras. I detta fall, eftersom 3 var den ^{0: te} termen är formeln a _n = 3 * 2 ^n. Om istället, du ville 3 för att vara den första termen, skulle du få en _n = 3 * 2 ^(n-1).

Polynom

1. 1
   Betrakta sekvensen 5, 0, -8, -17, -25, -30,... ges av den visade rekursion.
2. 2
   Varje rekursion av den form som visas, där p (n) är varje polynom i n, kommer att ha ett polynom sluten form formel av grad ett högre än graden av p.
3. 3
   Skriv den allmänna formen av ett polynom av den erforderliga graden. I detta exempel är p kvadratisk, så vi kommer att behöva en kubisk att representera sekvensen a _n.
4. 4
   Eftersom en allmän kubisk har fyra okända koefficienter, är fyra termer av sekvensen som krävs för att lösa det resulterande systemet. Alla fyra kommer att göra, så låt oss använda termer 0, 1, 2, och 3. Köra återfall bakåt för att hitta den -1 ^th sikt kan ge ett enklare system för att lösa, men är inte nödvändigt.
5. 5
   Lös det resulterande systemet av deg (p) 2 ekvationer i grader (p) = 2 okända som visas.
6. 6
   Om en var en av de termer du använde för att lösa de koefficienter, får du den konstanta termen i polynomet gratis och kan omedelbart reducera systemet till deg (p) 1 ekvationer i grader (p) 1 okända som visas.
7. 7
   Lös system av linjära ekvationer för att hitta C ₃ = 1/3, c ₂ = -5 / 2, c = ₁ -17/6, och c = 5. Presentera den slutna formeln för en _n som ett polynom med kända koefficienter.

Linjär

1. 1
   Detta är den första metoden kan lösa den Fibonacci-sekvensen i inledningen, men metoden löser en eventuellt återkommande där den ^{n: te} termen är en linjär kombination av de föregående k termer. Så låt oss prova på visas olika exempel, vars första termerna 1, 4, 13, 46, 157,....
2. 2
   Skriv det karakteristiska polynomet för återkomsten. Detta har konstaterats genom att ersätta varje a _n i återfall av x ⁿ och dividera med x ^(nk) lämnar en monic polynom av grad k och en noll konstant term.
3. 3
   Lös det karakteristiska polynomet. I detta fall har den karakteristiska grad 2 så att vi kan använda kvadratiska formel för att hitta sina rötter.
4. 4
   Varje uttryck av den visade formen uppfyller rekursion. Den c _jag är några konstanter och basen av exponenter är rötterna till den karakteristiska hittas ovan. Detta kan verifieras genom induktion.
   • Om egenskapen har en multipel rot, är detta steg modifieras något. Om r är en rot av multiplicitet m, använd (c ₁ r ⁿ + c ₂ nr ⁿ + c ₃ n ² r ⁿ +... + c _m n ^m-1 r ⁿ⁾ istället för att bara (c ₁ r ⁿ⁾. Till exempel, den sekvens som startar 5, 0, -4, 16, 144, 640, 2240,... uppfyller den rekursiva relationen a _n = 6a _n-1 - 12a _n-2 + 8a _n-3. Den karakteristiska polynomet har en trippel rot 2 och den slutna formen formeln a _n = 5 * 2 ^​​n - 7 * n * 2 ⁿ + 2 * n ² * 2 ^n.
5. 5
   Hitta c _jag att uppfylla de angivna ursprungliga villkoren. Som med polynomet exemplet görs detta genom att skapa ett linjärt ekvationssystem från de ursprungliga villkoren. Eftersom detta exempel har två okända, behöver vi två termer. Varje två kommer att göra, så ta det ^{0: e} och ^{1: a} för att slippa höja ett irrationellt tal till en hög effekt.
6. 6
   Lös det resulterande ekvationssystemet.
7. 7
   Anslut de resulterande konstanter i den allmänna formeln som lösningen.

Genererande funktioner

1. 1
   Betrakta sekvensen 2, 5, 14, 41, 122... ges av den visade rekursion. Detta kan inte lösas genom någon av ovanstående metoder, men en formel kan hittas med hjälp av genererande funktioner.
2. 2
   Skriv den genererande funktionen av sekvensen. En genererande funktion är helt enkelt en formell potensserie där koefficienten för x ⁿ är den ^{n: te} termen för sekvensen.
3. 3
   Manipulera den genererande funktionen som visas. Målet i detta steg är att finna en ekvation som ger oss möjlighet att lösa för den genererande funktionen A (x). Extrahera den första termen. Applicera återkommande förhållande till den återstående termer. Split summan. Utdrag konstanta termer. Använd definitionen av A (x). Använd formeln för summan av en geometrisk serie.
4. 4
   Hitta den genererande funktionen a (x).
5. 5
   Hitta koefficienten för x ⁿ i a (x). Metoderna för att göra detta kommer att variera beroende på exakt vad A (x) ser ut, men metoden för partiella fraktioner, i kombination med att veta den genererande funktionen av en geometrisk sekvens, fungerar här som visas.
6. 6
   Skriv formeln för a _n genom att identifiera koefficienten för x ⁿ i a (x).