Matematik

Bevis med induktion

18. juni kl. 13:10 af MelanieKM - Niveau: Universitet/Videregående

Proof using induction that C(n) = 2Fn+1− 1

Gerne en step by step guide til løsning, da jeg finder dette meget vanskligt. 


Brugbart svar (0)

Svar #1
18. juni kl. 13:16 af Anders521

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


Svar #2
18. juni kl. 13:19 af MelanieKM

Det er opgave 5 i vedhæftede pdf dokument. 

Vedhæftet fil:Workshop 2.pdf

Brugbart svar (0)

Svar #3
18. juni kl. 15:55 af peter lind

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


Brugbart svar (0)

Svar #4
18. juni kl. 16:17 af peter lind

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.


Brugbart svar (0)

Svar #5
18. juni kl. 21:40 af Soeffi

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

Vedhæftet fil:Fibonacci.png

Brugbart svar (1)

Svar #6
19. juni kl. 00:11 af Soeffi

#5. Opgave 5: Man skal finde C(n) = antallet af knuder i træet, der har Fib(n) eller Fn 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·Fn+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·F1 - 1 = 1 og C(1) = 2·F2 - 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·Fn+1 - 1, hvilket giver:

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

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

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

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


Svar #7
19. juni kl. 11:14 af MelanieKM

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


Brugbart svar (1)

Svar #8
19. juni kl. 11:43 af Soeffi

#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)...

Skriv et svar til: Bevis med induktion

Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk? Klik her for at oprette en bruger.