Wko

Hvordan man løser recidiv relationer

I forsøget på at finde en formel for nogle matematiske sekvens, er et fælles mellemliggende skridt til at finde den n'te sigt, ikke som en funktion af n, men i form af tidligere form af sekvensen. For eksempel, mens det ville være rart at have en lukket form, funktion for n th løbetid Fibonacci nogle gange alt du har, er en gentagelse forhold, nemlig at hvert led i Fibonacci sekvens er summen af de to foregående betingelser. Denne artikel vil præsentere flere metoder til at udlede en lukket form, formel fra en gentagelse.

Steps

Hvordan man løser recidiv relationer. Betragt en aritmetisk sekvens, såsom 5, 8, 11, 14, 17, 20.
Hvordan man løser recidiv relationer. Betragt en aritmetisk sekvens, såsom 5, 8, 11, 14, 17, 20.

Arithmetic

  1. 1
    Betragt en aritmetisk sekvens, såsom 5, 8, 11, 14, 17, 20,....
  2. 2
    Da hver valgperiode er 3 større end den tidligere, kan det udtrykkes som en gentagelse som vist.
  3. 3
    Erkend, at en gentagelse af formen a n = a n-1 + d er en aritmetisk sekvens.
  4. 4
    Skriv det lukkede formular formel for et aritmetisk sekvens, eventuelt med ubekendte som vist.
  5. 5
    Løs for eventuelle ubekendte afhængigt af hvordan sekvensen blev initialiseret. I dette tilfælde, da 5 var 0 th sigt formlen er en n = 5 + 3n. Hvis du i stedet ville have 5 for at være den første valgperiode, ville du få en n = 2 + 3n.

Geometrisk

  1. 1
    Betragt en geometrisk sekvens, såsom 3, 6, 12, 24, 48,....
  2. 2
    Eftersom hvert udtryk er dobbelte af den tidligere, kan det formuleres som en gentagelse som vist.
  3. 3
    Erkend, at en gentagelse af formen a n = r * a n-1 er en geometrisk sekvens.
  4. 4
    Skriv det lukkede formular formel for en geometrisk sekvens, eventuelt med ubekendte som vist.
  5. 5
    Løs for eventuelle ubekendte afhængigt af hvordan sekvensen blev initialiseret. I dette tilfælde var siden 3. 0-th sigt, formlen er en n = 3 * 2 n. Hvis du i stedet ville have 3 for at være den første valgperiode, ville du få en n = 3 * 2 (n-1).

Polynomisk

  1. 1
    Overvej sekvensen 5, 0, -8, -17, -25, -30,... afgivet den viste rekursion.
  2. 2
    Enhver rekursion af formen vist hvor p (n) er ethvert polynomium i n, vil have et polynomium lukket form, formel for graden én højere end graden af p.
  3. 3
    Skriv den almindelige form af et polynomium af den nødvendige grad. I dette eksempel er p kvadratisk, så vi får brug for en kubisk at repræsentere sekvensen a n.
  4. 4
    Da en generel kubisk har fire ukendte koefficienter, er fire begreber af sekvensen kræves for at løse det resulterende system. Enhver fire vil gøre, så lad os bruge tal 0, 1, 2 og 3. Kørsel fornyet baglæns for at finde den -1 th sigt kan give et nemmere system til at løse, men er ikke nødvendig.
  5. 5
    Løs resulterende system af grader (p) 2 ligninger i deg (p) = 2 ubekendte som vist.
  6. 6
    Hvis en var et af de udtryk, du brugte til at løse for koefficienterne, får du den konstante løbetid polynomium for gratis og kan umiddelbart reducere systemet til at deg (p) en ligninger i deg (p) en ubekendte som vist.
  7. 7
    Løs lineære ligninger for at finde c 3 = 1/3, c 2 = -5 / 2, c 1 = -17/6 og c = 5. Præsentere den lukkede formel for en n som et polynomium med kendte koefficienter.

Lineær

  1. 1
    Dette er den første metode stand til at løse fibonacci sekvens i indledningen, men fremgangsmåden løser en gentagelse, hvor n th sigt er en lineær kombination af de tidligere k vilkår. Så lad os prøve det på forskellige viste eksempel, hvis første udtryk er 1, 4, 13, 46, 157,....
  2. 2
    Skriv det karakteristiske polynomium for gentagelse. Dette er fundet ved at erstatte hver a n i recidiv med x n og dividere med x (nk) efterlader et monic polynomium af grad k og et nul konstant sigt.
  3. 3
    Løs det karakteristiske polynomium. I dette tilfælde har den karakteristiske grad 2, så vi kan bruge den kvadratiske formel til at finde sine rødder.
  4. 4
    Ethvert udtryk for den viste form opfylder rekursion. C jeg er nogen konstanter og bunden af eksponenterne er rødderne til den karakteristiske findes ovenfor. Dette kan kontrolleres ved induktion.
    • Hvis den karakteristiske har en multipel rod, er dette trin ændres en smule. Hvis r er en rod af multiplicitet m, brug (c 1 r n + c2 nr n + c 3 n 2 r. n +... + c m n m-1 r n) i stedet for blot at (c 1 r n). For eksempel starter sekvensen 5, 0, -4, 16, 144, 640, 2240,... opfylder den rekursive forhold a n = 6a n-1 - 12a n-2 + 8a n-3. Det karakteristiske polynomium har en tredobbelt rod 2 og den lukkede form formel a n = 5 * 2 ​​n - 7 * n * 2 n + 2 * n 2 * 2 n.
  5. 5
    Find c i at tilfredsstille de angivne oprindelige betingelser. Som med polynomiet eksempel, gøres dette ved at skabe et lineært system af ligninger fra de oprindelige betingelser. Da dette eksempel har to ubekendte, har vi brug to valgperioder. Enhver to vil gøre, så tager 0 th og 1 m for at undgå at skulle rejse et irrationelt tal til en høj effekt.
  6. 6
    Løs det resulterende system af ligninger.
  7. 7
    Sæt de resulterende konstanter i den generelle formel som løsningen.

Generering funktioner

  1. 1
    Overvej rækkefølgen 2, 5, 14, 41, 122... afgivet den viste rekursion. Dette kan ikke løses ved enhver af de ovennævnte metoder, men en formel kan findes ved hjælp af frembringende funktioner.
  2. 2
    Skriv den frembringende funktion af sekvensen. En frembringende funktion er simpelthen en formel potensrække hvor koefficienten til x n er n th sigt af sekvensen.
  3. 3
    Manipulere frembringende funktion som vist. Målet i dette trin er at finde en ligning, der vil tillade os at løse for den frembringende funktion A (x). Uddrag den indledende periode. Påfør gentagelse relation til de resterende vilkår. Opdel sum. Uddrag konstante vilkår. Anvende den definition af A (x). Brug formlen for summen af ​​en geometrisk serie.
  4. 4
    Find den frembringende funktion a (x).
  5. 5
    Find koefficienten af x n i a (x). De metoder til at gøre dette vil variere afhængigt af præcis, hvad A (x), ser ud, men den metode partielle fraktioner, kombineret med at kende den frembringende funktion for en geometrisk sekvens, fungerer her som vist.
  6. 6
    Skriv formlen for a n ved at identificere koefficienten x n i et (x).

Tips

  • Nogle af disse metoder er regnekraft med mange muligheder for at gøre en dum fejl. Det er godt at kontrollere formlen mod et par kendte vilkår.
  • Induktion er også en populær teknik. Det er ofte let at bevise ved induktion, at en bestemt formel opfylder en bestemt rekursion, men problemet er det kræver gætte formlen på forhånd.