• Matematisk induksjon og rekursjon
• Svak og sterk induksjon
• Rekursive definisjoner
• Differenslikninger
• Lineær, homogen differenslikning, 1. orden
• Lineær, inhomogen differenslikning, 1. orden
• Lineær, homogen differenslikning, 2. orden
• Lineær, inhomogen differenslikning, 2. orden
• Rekursiv og iterativ programmering
• Resept på løsning av differenslikninger

Stikkord:
^{[Merk et av ordene og bruk søkefunksjonen (Ctrl-F) i nettleseren til å bla opp]}
basistrinn   differenslikning   generell løsning   homogen   induksjon   induksjonstrinn   inhomogen   iterativ   karakteristisk likning   lineær   Matlab   Maxima   partikulær løsning   rekursiv definisjon   rekursjon   rekursjonslikning   startverdi   tallfølge

Matematisk induksjon og rekursjon

En gammel fortelling dreier seg om riskorn på et sjakkbrett plassert etter følgende mønster,

Rute 1 har ett korn,
rute 2 har to korn,
rute 3 har fire korn,
- og videre slik at neste rute har dobbelt så mange korn som foregående rute.
Hvor mange korn er det på siste rute? Hvor mange korn er det tilsammen?

Et sjakkbrett har 8x8 ruter organisert fra A1 til H8, men her forenkler vi og sier at rutene indekseres i ordningen 1-64. Vi lar heltallet n være ruteindeks. Antall korn på rute nr. n er en funksjon av n. I vanlig matematikk ville vi vel ha uttrykt antallet som en funksjon av n, a(n), slik at a(3)=4, a(5)=16, osv. Men siden det her alltid dreier seg om heltallsverdier av n skriver vi dette funksjonsuttrykket som a_n, der indeksen n angir den uavhengige variabelen i funksjonen. Holder du riktig telling vil vi her ha at for eksempel a₇=64 og a₁₀=512.

Antall korn på en tilfeldig rute k kan vi finne ved å iterere, det vil si stare med a₁=1 og fortsette etter mønsteret a₂=2⋅a₁, a₃=2⋅a₂=2(2⋅a₁), a₄=..., til vi kommer til k. Alternativt kan vi bruke det vi vet om geometriske tallfølger til å finne a_k. Metoden vi skal lære nedenfor er å sette opp slike problem som en differenslikning og løse denne.

Oppgaven her er å finne et funksjonsuttrykk for a_n ut fra de to opplysningene
    a_n = 2 ⋅ a_n-1
    a₁ = 1 (startbetingelse)

Her går vi rett på sak og henter løsningen, a_n = 2^n-1 - og på siste rute i sjakkbrettet bør det altså være plass til
2^64-1 = 9223372036854775808 korn.

Hvordan skulle vi tilsvarende sette opp en slik differenslikning for å finne antal korn tilsammen så langt hvis vi nettop har lagt det rette antallet korn på rute n? Her lar vi sumfunksjonen være s_n, med altså s₁=1, s₂=3, s₃=7, ...

Oppgaven her er å finne et funksjonsuttrykk for s_n ut fra de to opplysningene
    s_n = s_n-1 + 2^n-1
    s₁ = 1 (startbetingelse)

Dette siste likningsoppsettet kan muntlig formuleres omtrent slik:
"Antall korn tilsammen på brettet til og med rute n er lik antall korn på alle de foregående rutene summert med antallet korn som legges på rute n - og på første rute er summen 1 korn."

Igjen går vi rett på sak og viser løsningen, s_n = 2ⁿ-1. Et pent lite uttrykk som vi senere skal finne som løsningen på den lineære, inhomogene differenslikningen
        s_n - s_n-1= 2^n-1 ,       s₁ = 1.

Vi svinger innom nok et begrep før vi går videre, induksjonsbevis. Hvordan kan vi overbevise oss at s_n = 2ⁿ-1 er løsningen på den siste differenslikningen ovenfor? Jo, vi ser at formelen gir riktig sum for rute nr. 1, og så antar at formelen gir riktig sum for alle ruter tom. en viss rute k - og så legger vi til antall korn på neste rute - og ser om vi kunne ha regnet det hele ut med samme formel. Vi skal nå altså bevise en formel eller et utsagn som en slags alternativ løsningsteknikk. Her er teknikken i korte trekk:

Formelen gir riktig sum for n=1, s₁ = 2¹-1=1.
Vi antar at formelen gjelder for rute nr. k, altså s_k = 2^k-1
Legger vi til antall korn på neste rute (med indeks k+1) får vi summen til og med rute k+1,
s_k+1 = s_k + a_k+1
Setter inn for s_k og a_k+1,
s_k+1 = 2^k-1 + 2^(k+1)-1
s_k+1 = 2^k + 2^k - 1 = 2^k+1-1
- og vi konkluderer med at hvis formelen gjelder for rute k, så gjelder den også for rute k+1 - og siden den helt sikker gjelder for rute 1, vil den også gjelde for rute 2 - og 3 - og 4 - og iterativt opp til den ruta vi vil.

Antall riskorn på brettet skulle dermed bli 2⁶⁴-1 = 18446744073709551615 - en haug større enn Mount Everest og omtrent 1000 ganger verdens årsproduksjon av ris.

Svak og sterk induksjon

Svak induksjon
Et utsagn P(n) kan vises å være sant for alle n ved matematisk induksjon på følgende måte,

Basistrinnet,
        Vis at utsagnet P(1) er sant.
Induksjonsstrinnet,
        Vis at dersom P(n) er sann, så er P(n+1) også sann for n=1,2,3,...

Det bygger på et sant basisutsagn og et bevis for at hvis utsagnet P(n) er sant så er P(n+1) også sant for en viss verdi av n. Det bevises ikke direkte at utsagnet er sant for alle verdier av n, men ved å legge til at 'siden P(1) er sann, så er P(2) sann, og siden P(2) er sann, så er P(3) sann, og så videre til et hvilket som helst tilfelle'– så gjelder det for alle.

Sterk induksjon
Bevis ved svak induksjon er basert på basistrinnet P(1) og at hvis påstanden P(N) gjelder for en eller annen verdi av n, så kan det vises at P(n+1) også gjelder. For å gjøre beviset komplett må vi formelt i tillegg gjenta at 'P(2) gjelder fordi P(1) gjelder, P(3) gjelder fordi P(2) gjelder, osv...' Sterk induksjon skiller seg fra svak induksjon ved at induksjonstrinnet skal vise at dersom alle påstander P(1), P(2), ..., P(n) er sanne så må også P(n+1) være sann.

Basistrinnet,
        Vis at utsagnet P(1) er sant.
Induksjonsstrinnet,
        Vis at dersom P(1), P(2), ..., P(n) alle er sann, så er P(n+1) også sann for n=1,2,3,...

Rekursive definisjoner

En tallfølge kan formuleres

• eksplisitt, med formel for det generelle leddet
• rekursivt, med sammenhengen mellom leddene

Definisjon 1
Den enkleste form for rekursiv definisjon er basert på at verdien av et ledd i en tallfølge kan uttrykkes ved hjelp av det foregående ledd,
        basis: y₁ er definert
        rekursjon: y_n er definert ved uttrykk i y_n-1.

a)                               b)
87654321   8765432-   876543--   876543--
--------   --------   2-------   21------
--------   1-------   1-------   --------

                                 c)
87654---   876541--   876541--   87654---
21------   2-------   --------   --------
3-------   3-------   32------   321-----

d)         e)            f)
8765----   876-----  //  876-----
4321----   4321----  //  --------
--------   5-------  //  54321---

Definisjon 2
En tallfølge kan også beskrives ved at verdien av et ledd er gitt av et uttrykk der verdiene av de to foregående (eller flere) leddene inngår:
        basis: y₁ og y₂ er definert
        rekursjon: y_n er definert ved uttrykk i y_n-1 og y_n-2.

Differenslikninger

En differenslikning eller rekursjonslikning er en rekursiv definisjon av en tallfølge der vi skal finne et eksplisitt uttrykk for det generelle leddet som funksjon av indeksvariabelen. Med startverdier vil vi finne en partikulær løsning – uten startverdier kan vi finne en generell løsning.

En homogen differenslikning setter opp sammenhengen mellom to eller flere ledd i en tallfølge og ingen andre konstanter eller variabler, for eksempel
        y_n = 2y_n-1 - y_n-2 , n≥2 , y₀=0 , y₁=1.

En inhomogen differenslikning setter opp sammenhengen mellom to eller flere ledd i en tallfølge og andre konstanter eller variabler, eksempel
        y_n = 2y_n-1 +(n-1)⋅3ⁿ , n≥1 , y₀=5.

En lineær differenslikning setter opp sammenhengen mellom to eller flere ledd i en tallfølge der leddene er lineære (ikke potenser eller rotuttrykk). Vi løser bare lineære differenslikninger med konstante koeffisienter – slik som de to likningene ovenfor.

Lineær, homogen differenslikning, 1. orden

Her er tre tallfølger,

    n=0   n=1   n=2   n=3   ...
  {   2,    6,   18,   54,  ...   }
  {   5,   15,   45,  135,  ...   }
  {   C,   3C,   9C,  27C,  ...   }

Alle følgene er slik at 'verdien av neste ledd er lik 3 ganger foregående ledd', altså y_n = 3 y_n-1, men de skiller seg på startbetingelsene, y₀=2 for den første, y₀=5 for den andre og y₀=C for den tredje.
Løsningen på den homogene differenslikningen y_n = 3 y_n-1 er generelt y_n = C⋅3ⁿ. En spesiell løsning finner vi først når vi kjenner verdien av ett ledd i følgen - og hvilken indeks det har, her for eksempel y₀=2.
Dette er en homogen differenslikning av 1. orden med konstant koeffisient. Tallfølgen som beskrives er også kjent som en geometrisk følge - der det er et konstant forhold mellom to naboledd.
Metoden for å løse slike likninger er oppsummert her:

Ordnet likning,
        y_n - a y_n-1 = 0 + def.område + startverdi
Generell løsning,
        y_n = C aⁿ , der C finnes av startverdi.

Lineær, inhomogen differenslikning, 1. orden

Her er tre tallfølger,

    n=0       n=1       n=2       n=3   ...
  {   2,       10,       38,      126,  ...   }
  {   5,       19,       65,      207,  ...   }
  {   C,    3*C+4,   9*C+20,  27*C+72,  ...   }

Alle følgene er slik at 'verdien av neste ledd er lik 3 ganger foregående ledd lagt sammen med 4 ganger indeksen', altså y_n = 3 y_n-1 + 4n, men de skiller seg på startbetingelsene, y₀=2 for den første, y₀=5 for den andre og y₀=C for den tredje.
Løsningen på den tilsvarende homogene differenslikningen y_n = 3 y_n-1 er generelt y_n = C⋅3ⁿ, og leddene som vi får ved å sette inn for n inngår som en del av leddverdiene i tallfølgen for denne inhomogene likningen. Dette betyr at løsningen på en inhomogen differenslikning består av to komponenter: (1) løsningen på den tilsvarende homogene likningen, lagt sammen med (2) en partikulær løsning av den inhomogene likningen. Vi skriver dette som y_n = y_n^(h) + y_n^(p). Den partikulære løsningen er et uttrykk 'av samme' type som det inhomogene leddet.
Metoden for å løse slike likninger er oppsummert her:

Ordnet likning,
        y_n - a y_n-1 = f(n) + def.område + startverdi
Løsningen er summen av løsingen på den tilsvarende homogene likninga, y_n^(h)
og en partikulær løsning av den inhomogene likninga av samme uttrykkstype som det inhomogene leddet, y_n^(p).
Samlet løsning: y_n = y_n^(h) + y_n^(p)

Den partikulære løsninga prøves 'av samme type' som det inhomogene leddet etter følgende skjema:

Løsningsmetoden er generelt slik:

1. Ordne likninga: y_n - a y_n-1 = f(n) + def.område + startverdi
2. Generell løsning på homogen liking er: y_n^(h) = C aⁿ .
3. Tipp generell partikulær løsning y_n^(p) ut fra homogent ledd og skjemaet ovenfor.
   Finn de ukjente konstantene i generell, partikulær løsning ved innsetting av y_n^(p) i opprinnelig likning.
   Sett verdiene inn i y_n^(p).
4. Løsningen er y_n = y_n^(h) + y_n^(p) = C aⁿ + y_n^(p), der den ukjente konstanten C kan bestemmes av startverdien.

Resepten starter med å finne generell løsning, men venter med å gå videre med denne. Hvis det er sammenfall mellom y_n^(p) og y_n^(h) skal y_n^(p) multipliseres med n (evt n², n³, ...).

Lineær, homogen differenslikning, 2. orden

En 2. ordens homogen differenslikning er ut uttrykk for verdien av et ledd i en tallfølge gitt av verdiene på de to foregående leddene, y_n = a₁ y_n-1 + a₂ y_n-2, der a₁ og a₂ er konstanter. På ordnet form blir det y_n - a₁ y_n-1 - a₂ y_n-2 = 0 - og gjerne en startverdi. Løsningen på en slik likning er forbausende enkel, y_n = C⋅λⁿ. La oss sette denne generelle løsningen inn i likningen, og gjøre noen forenklinger,

y_n - a₁ y_n-1 - a₂ y_n-2 = 0     (setter inn for y_n,)
C⋅λⁿ - a₁ C⋅λ^n-1 - a₂ C⋅λ^n-2 = 0     (dividerer med C⋅λ^n-2,)
λ² - a₁ λ - a₂ = 0     (karakteristisk likning)

Denne karakteristiske likninga har generelt to røtter, λ₁ og λ₂, med tilhørende løsning på differenslikinga, y_n = C₁⋅λ₁ⁿ + C₂⋅λ₂ⁿ. Hvis den karakteristiske likninga har sammenfallende eller komplekse røtter blir det ikke fullt så enkelt. Her er løsningsmetoden oppsummert:

Ordnet likning,
        y_n - a₁ y_n-1 - a₂ y_n-1 = 0 + def.område + startverdier
Likninga har en karakteristisk likning λ² - a₁ λ - a₂ = 0 med 3 mulige løsningstyper:
(1) to ulike, reelle røtter, λ₁ ≠ λ₂:
        y_n = A λ₁ⁿ + B λ₂ⁿ
(2) sammenfallende røtter, λ₁ = λ₂ = λ:
        y_n = A λⁿ + B n λⁿ
(3) komplekskonjugerte røtter, λ_1,2 = r e^±φi
        y_n = rⁿ(C cos(nφ) + D sin(nφ))

Lineær, inhomogen differenslikning, 2. orden

Ordnet likning,
        y_n - a₁ y_n-1 - a₂ y_n-1 = f(n) + def.område + startverdier
Det inhomogene leddet f(n) er gjerne et polynom i n (c n^r...), en eksponent i n, (c αⁿ...) eller en kombinasjon (c n^r αⁿ...), som tidligere vist for 1. orden.
Løsningen er generelt y_n = y_n^(h) + y_n^(p),
der y_n^(h) er løsningen av den homogene likninga y_n - a₁ y_n-1 - a₂ y_n-1 = 0
og y_n^(p) er en partikulær løsning av y_n - a₁ y_n-1 - a₂ y_n-1 = f(n) .
Den partikulære løsningen vil være av samme type som det inhomogene leddet.
Dersom y_n^(p) inngår i y_n^(h) multipliseres y_n^(p) med n, n², n³, ...
Likninga har en karakteristisk likning λ² - a₁ λ - a₂ = 0 med 3 mulige løsningstyper:
(1) to ulike, reelle røtter, λ₁ ≠ λ₂:
        y_n = A λ₁ⁿ + B λ₂ⁿ
(2) sammenfallende røtter, λ₁ = λ₂ = λ:
        y_n = A λⁿ + B n λⁿ
(3) komplekskonjugerte røtter, λ_1,2 = r e^±φi
        y_n = rⁿ(C cos(nφ) + D sin(nφ))

Løsningsmetoden er generelt slik:

1. Ordne likninga, y_n - a y_n-1 = f(n) + def.område + startverdi
2. Sett opp karakteristisk likning, λ² - a₁ λ - a₂ = 0 og finn røttene i denne.
   Bruk tabellen for de 3 mulige løsningstypene og finn generell form for y_n^(h) .
3. Tipp generell partikulær løsning y_n^(p) ut fra homogent ledd og skjemaet ovenfor.
   Finn de ukjente konstantene i generell, partikulær løsning ved innsetting av y_n^(p) i opprinnelig likning. Sett verdiene inn i y_n^(p).
4. Løsningen er y_n = y_n^(h) + y_n^(p) = C aⁿ + y_n^(p), der den ukjente konstanten C kan bestemmes av startverdien.

Resepten ovenfor starter med å finne generell løsning for y_n^(h), men venter med å gå videre med denne til vi ser uttrykket for y_n^(p). Hvis det er sammenfall mellom y_n^(p) og y_n^(h) skal alle leddene i y_n^(h) multipliseres med n (evt n², n³, ...).

Matlab har et symbolsk tillegg med eget GUI, MuPad, som kan løse visse typer differenslikninger, men feiler på de siste eksemplene. Alternativet Maxima løser slike likninger etter at vi laster inn et tillegg. Så taster vi inn oppgaven,

%i.  load(solve_rec);
%i.  solve_rec(y[n]-6*y[n-1]+9*y[n-2]=2^n, y[n], y[0]=1, y[1]=2);
%o.  y[n]=2^(n+2)+(n-3)*3^n
%i.  solve_rec(y[n]-y[n-1]-2*y[n-2]=2*n, y[n], y[0]=-1, y[1]=1);
%o.  y[n]=2^(n+1)-(-1)^n/2-n-5/2

Rekursiv og iterativ programmering

Kjenner du til Matlab/Octave kan vi demonstrere prinsippene iterasjon og rekursjon med et par programeksempler.
Først beregnes fakultet for et tall iterativt etter prinsippet   n! = 1⋅2⋅3⋅...⋅n.
Deretter rekursivt etter prinsippet   n! = n⋅(n-1)!   ∧ 0!=1.

    function svar = fak_iter( n )
    % FAK_ITER Beregner n! = 1*2*3*4*...*n iterativt.
    if n >= 0
        svar = 1;
        for k = 2:n
            svar = svar * k;
        end
    else
        svar = NaN;
    end
    end

>> fak_iter(10)
ans =  3628800
>> fak_iter(0)
ans =  1
>> fak_iter(-7)
ans = NaN

Det er kommandoen svar = svar * k som gjør jobben, etter hver runde blir den nye verdien av svar lik forrige verdi multiplisert med rundenummeret k. Funksjonen fak_iter beregner riktig for alle n>=0, men er satt til å returnere NaN for n<0. For eksempel vil 5! bli beregnet med gjentakelsene
    svar = 1
    svar = 1 * 2 = 2
    svar = 2 * 3 = 6
    svar = 6 * 4 = 24
    svar = 24 * 5 = 120

Neste eksempel er funksjonen fak_reku som gjentar seg selv med nye funksjonskall helt til den har gjort jobben,

    function svar = fak_reku( n )
    % FAK_REKU Beregner n! = n * (n-1)! rekursivt til 0!=1.

    if n == 0
        svar = 1;
    else
        svar = n * fak_reku(n-1);
    end
    end

>> fak_reku(5)
ans =  120
>> fak_reku(0)
ans =  1
>> fak_reku(-4)
error: max_recursion_depth exceeded

Funksjonen fak_reku beregner riktig for alle n>=0, men feiler for negative n-verdier fordi det ikke er tatt hensyn til dette i koden slik som i fak_iter. Her blir 5! beregnet med rekursjonsstegene

5*fak_reku(4)
   4*fak_reku(3)
      3*fak_reku(2)
         2*fak_reku(1)
            1*fak_reku(0)
            = 1
         = 2
      = 6
   = 24
= 120

Det kan se ut som om funksjonen fak_reku kaller seg selv 5 ganger, men det som skjer er at det er 5 selvstendige utgaver av funksjonen som kjøres. Ved en kjede rekursive funksjonskall vil det ikke bli laget returverdi før det innerste funksjonskallet returnerer med 1 ved testen if n==0. Deretter gir nest innerste funksjonskall returverdi - og slik i en kjede tilbake til ytterste kall.

Det bør også nevnes at for store n-verdier (n > 21) vil vi ikke få et eksakt heltallsvar i Matlab/Octave på grunn av måten tall blir representert på.