Proof of the formula for the sum of the first n Fibonacci numbers
- Get link
- X
- Other Apps
Hello everyone. Today we will prove the formula for the sum of the first \(n \) Fibonacci numbers. We will use the method of mathematical induction as a proof method.
Theorem: \(\forall n \in \mathbb {N} _0, \quad \displaystyle \sum_ {j = 0} ^ nF_j = F_ {n + 2} -1 \)
Proof:
1. Base case (n = 0) \[\displaystyle \sum_ {j = 0} ^ 0F_j = F_ {2} -1 \] \[F_ {0} = F_ {2} -1 \] \[0 = 1-1 \] \[0 = 0 \]
2. Induction hypothesis (n = m)
Suppose that: \[\displaystyle \sum_ {j = 0} ^ mF_j = F_ {m + 2} -1 \]
3. Inductive step (n = m + 1)
Using the assumption from the second step, we will prove that: \[\displaystyle \sum_ {j = 0} ^ {m + 1} F_j = F_ {m + 3} -1 \] So, \[\displaystyle \sum_ { j = 0} ^ {m + 1} F_j = \displaystyle \sum_ {j = 0} ^ {m} F_j + F_ {m + 1} = \] \[F_ {m + 2} -1 + F_ {m +1} = \] \[F_ {m + 1} + F_ {m + 2} -1 = \] \[F_ {m + 3} -1 \]
\(\blacksquare\)
- Get link
- X
- Other Apps
Comments
Post a Comment