Guess a closed form for the sum F 1 + F 3 + . . . + F 2n1 , where n > 0 is a nat
ID: 3664543 • Letter: G
Question
Guess a closed form for the sum F1 + F3 + . . . + F2n1 , where n > 0 is a natural number and (Fk )k0 are Fibonacci numbers. This closed form may involve Fibonacci numbers. Show by induction that your guess is correct.
Hint: Let us consider the values of these sums for small n’s for a clue. Here is a reminder of the initial segment of Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, . . . where the numbers Fi with odd indices i are in bold. Let us compute the smallest sums:
F1 = 1
F1 + F3 = 1 + 2 = 3
F1 + F3 + F5 = 3 + 5 = 8
F1 + F3 + F5 + F7 = 8 + 13 = 21
F1 + F3 + F5 + F7 + F9 = 21 + 34 = 55
The outcomes we obtain are all Fibonacci. And there is a pattern.
Explanation / Answer
From the small sums, we cud see a simple pattern.
F1 = 1 = F2
F1 + F3 = 1 + 2 =3 = F4
F1 + F3 + F5 = 3 + 5 = 8 = F6
F1 + F3 + F5 + F7 = 8 + 13 = F8
F1 + F3 + F5 + F7 + F9 = 21 + 34 = 55 = F10
Hence , we can guess the closed form for F1 + F3 + . . . + F2n1 = F2n
--------------------------------------------------------------------------------------------------------------
Proof my Mathematical Induction :
To prove : F(n): F1 + F3 + . . . + F2n1 = F2n where n > 0 is a natural number and (Fk)k0 are Fibonacci numbers
1. Basis or base case
n = 1.
F(1) = 1 = F(2) , F(1) holds true
2.
Assume F(k) holds (for some unspecified value of k). It must then be shown that F(k + 1) holds, that is
Assume F(k) : F1 + F3 + . . . + F2k1 = F2k holds true.
To prove F(k+1) holds true is F(k) holds true.
that is, F(k+1) : F1 + F3 + . . . + F2k1+F2k+1 = F2k+2
Using the induction hypothesis that F(k) holds, the left-hand side can be rewritten to:
F1 + F3 + . . . + F2k1+F2k+1 = F2k+2
F2k + F2k+1 = F2k+2
Using definition of fibinocci numbers , Fm + Fm+1 = Fm+2 , sum of consecutive terms gives the next term in the sequence.
Thus , F2k + F2k+1 = F2k+2 is true.
thereby showing that indeed F(k + 1) holds.
Since both the basis and the inductive step have been performed, by mathematical induction on n, the statement F(n) holds for all natural numbers n>1.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.