Bevis med induktion

#0 Hvad er C og F? Gerne kom med hele opgaveteksten.

Det er opgave 5 i vedhæftede pdf dokument. 

Det er helt forkert. Se https://da.wikipedia.org/wiki/Fibonacci-tal Bortset fra de 3 første tal er det ikke fibonaccirækken

Undskyld. Fejl i 3.

Det er spørgsmål 2 der er forkert. Det er jo en direkte definition af fibonaccitallene, så der behøves ikke noget bevis.

3. Kan også bevises direkte.

#0. Indsætter opgavetekst til og med spørgsmål 5.

#5. Opgave 5: Man skal finde C(n) = antallet af knuder i træet, der har Fib(n) eller F_n i roden.

Hvis man ser på det viste træ (figur 2), så kan man udlede følgende rekursionsformel for c(n):  

C(n) = C(n-2) + C(n-1) + 1. (Et træ er de to foregående træer lagt sammen plus en ny rod).

Man skal ved induktion bevise, at C(n) = 2·F_n+1 - 1.

Man har at C(0) = 1 og C(1) = 1, da de ikke kræver beregning.

Dette stemmer med formlen: C(0) = 2·F₁ - 1 = 1 og C(1) = 2·F₂ - 1 = 1.

Man indsætter herefter induktionsantagelsen i rekursionsformlen for C(n) og gør prøve:

Venstre: C(n)               Højre: C(n-2) + C(n-1) + 1. Heri indsættes: C(n) = 2·F_n+1 - 1, hvilket giver:

Venstre: 2·F_n+1 - 1       Højre: (2·F_n - 1) + (2·F_n-1 - 1) + 1

Venstre: 2·F_n+1 - 1       Højre: 2·(F_n - 1 + F_n-1 - 1) + 1

Venstre: 2·F_n+1 - 1       Højre: 2·F_n+1 - 2 + 1

Venstre: 2·F_n+1 - 1       Højre: 2·F_n+1 - 1 

Tak for et maget brugbart svar. :D

Jeg har dog et enkelt spørgsmål:

Hvor kommer +1 fra i nedenstående formel? 

C(n) = C(n-2) + C(n-1) + 1

#7. 

#6... C(n) = C(n-2) + C(n-1) + 1. (Et træ er de to foregående træer lagt sammen plus en ny rod)...