Hint til forklaring

[FredrikM]

Hei.

Er en oppgave jeg har tenkt en del på:

Betrakt sekvenser av lengde n bestående av 0'ere og 1'ere der første siffer er 1 og 1'ere aldri følger etter hverandre. La [tex]a_n[/tex] betegne antallet av slike sekvenser. Forklar hvorfor a_n tilfredsstiller differensligningen
[tex]a_n = a_{n-1} + a_{n-2} , n > 2, a_1=a_2=1[/tex]
Finn [tex]a_n[/tex] ved å løse ligningen.

Siste del går helt enkelt og greit (etter lange, stygge algebraiske uttrykk). Men forklaringsdelen er verre.

Noen som kan hinte litt? Jeg ser jo ved å skrive opp de mulige kombinasjonene for n=1, n=2, osv, at dette ser ut til å stemme, men jeg har problemer med å skjønne hvorfor det må være slik.

Takk?

[Karl_Erik]

Du kan dele inn antallet sekvenser inn i to typer: de med siste siffer lik 0 og de med første siffer lik 1. Hjelper det litt?

EDIT: første != siste

[FredrikM]

Etter å ha lett en stund fant jeg et løsningsforslag et sted (ja, jeg vet det er juks =/), og det var omtrent som følger:

For n=1, er det kun mulig med èn kombinasjon, altså 1. For n=2 er det fremdeles kun èn kombinasjon mulig, altså 10.

PS: Karl_Erik: Antar du mener siste siffer?

Nå kan vi granske to tilfeller:

T1: Om siste siffer er 0, kan foregående siffer være både 1 og 0, vi har altså n-1 muligheter for hvordan uhm... ting kan være.

T2: Om siste siffer er 1, må foregående være 0, og vi kan da velge mellom n-2 forskjellige muligheter.

Også følger det visstnok at differenslikningen er slik den. ^ se over.

Det jeg ennå ikke helt fatter, er hvor plusstegnet kommer fra. Eller sagt kanskje noe bedre; hvordan man tenker kombinatorisk med differenslikninger.

[Karl_Erik]

Du har helt rett; mente siste siffer. Uansett, kan forklare det for deg. Det siste sifferet kan være enten 0 eller 1. Om den er 0 kan sifferet foran være hva som helst, og for å lage en sekvens med lengde n trenger vi en sekvens med lengde (n-1) fordan det siste sifferet. Antallet slike sekvenser er lik a[sub]n-1[/sub].

Om det siste sifferet er 1 må det nest siste sifferet være 0. For å lage en sekvens med lengde n trenger vi altså en sekvens med lengde (n-2) som kan stå foran de to siste tallene. Antallet slike sekvenser er lik a[sub]n-2[/sub].

I og med at alle sekvenser med lengde n må høre til i en av disse to gruppene (og ingen sekvens hører til i begge gruppene - finnes ingen sekvenser som både slutter på 1 og 0) må det totale antallet sekvenser med lengde n være summen av disse to gruppene, som blir a[sub]n-1[/sub] + a[sub]n-2[/sub].

[FredrikM]

Takk skal du ha! Nå forstod jeg en hel del mer.