In: Computer Science
The Fibonacci sequence is defined as F_1 = 1, F_2 = 1, and F_n = F_n-1 + F_n-2 for n >= 3. Calculate the sum F_1 + F_2 + ... + F_n using the fundamental theorem of summation.
The Fibonacci number is related to the number theory in mathematics. In the number series, every element of the series is obtained by the sum of two preceding numbers except the first two elements, then this type of series is called a Fibonacci number of series.
The Fibonacci sequence is defined by F1 = 1, F2 = 1, and Fn = Fn−1 + Fn−2 for n ≥ 3.
Its first few terms are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . . .
Fibonacci sums: Prove that Fi = Fn+2 − 1 for all n ∈ N.
Solution: We seek to show that, for all n ∈ N,
Fi = Fn+2 − 1.
Base case: When n = 1, the left side of (∗) is F1 = 1, and the right side is F3 − 1 = 2 − 1 = 1, so both sides are equal and (∗) is true for n = 1.
Induction step: Let k ∈ N be given and suppose (∗) is true for n = k. Then
Fi = Fi + Fk+1
= Fk+2 − 1 + Fk+1 (by ind. hyp. (∗) with n = k)
= Fk+3 − 1 (by recurrence for Fn)
Thus, (∗) holds for n = k + 1, and the proof of the induction step is complete.
Conclusion: By the principle of induction, it follows that (∗) is true for all n ∈ N.