Fibonacci recurrence relation - Principle of Mathematical Induction

Question

The problem:

Let $F_n$ be the nth term of the Fibonacci sequence:

$F_0 = 0$

$F_1 = 1$

$F_n = F_{n-1} + F_{n-2}$ for $n\geq2$

Prove that $\sum_{i=1}^{n} F_i^2 = F_nF_{n+1}$ for all $n \in\mathbb{N}$

My attempt to prove this using the induction hypothesis is:

1) With $n = 1$, the equation holds true: $F_{1}^2 = F_{1}F_{n+1}$ because $1^2 = 1*1$.

2) Now we have to prove that $\sum_{i=1}^{n} F_i^2 = F_nF_{n+1} \implies \sum_{i=1}^{n+1} F_i^2 = F_{n+1}F_{n+2}$

We know that $\sum_{i=1}^{n+1} F_i^2 = \sum_{i=1}^{n} F_i^2 + F_{n+1}^2$, and if we assume that the antecedent is true we get:

$\sum_{i=1}^{n+1} F_i^2 = F_{n}F_{n+1} + F_{n+1}^2$

If we replace this last equation in the consequent we get:

$F_{n}F_{n+1} + F_{n+1}^2 = F_{n+1}F_{n+2}$

Finally, if we divide both sides by $F_{n+1}$ we end up with the Fibonacci recurrence equation:

$F_{n+2} = F_{n+1} + F_{n}$

We know this holds for all $n\in\mathbb{N}$, because $F_n$ is defined as the nth term of the Fibonacci sequence by the premises of the problem. Therefore we have proven (2).

Thus, by the Principle of Mathematical Induction: $\sum_{i=1}^{n} F_i^2 = F_nF_{n+1}$ for all $n \in\mathbb{N}$

QUESTION: Is this proof correct? And if not, where is the mistake?

Answer 1

Let’s analyze formal structure of the proof. Let $P_n=\sum_{i=1}^{n} F_i^2 = F_nF_{n+1}$. According to principle of mathematical induction from your reference, we have to prove $P_1$ (what you did in (1) ) and $P_n\Rightarrow P_{n+1}$ for all $n\in\Bbb N$ (what you stated in (2)).

We know that $\sum_{i=1}^{n+1} F_i^2 = \sum_{i=1}^{n} F_i^2 + F_{n+1}^2$,

This holds by the definition of a sum.

and if we assume that the antecedent is true

Yes, proving that $P_n$ implies $P_{n+1}$ we can assume that $P_n$ is true.

we get: $\sum_{i=1}^{n+1} F_i^2 = F_{n}F_{n+1} + F_{n+1}^2$

Right, by the above. Concerning this comment, when we write this, we don’t need to assume that the consequent ($P_{n+1}$) is true. It suffices to assume that the antecedent ($P_{n}$) is true, what we did above. Also we don’t need to prove that the antecedent is equivalent to the consequent, that is $P_n \Leftrightarrow P_{n+1}$.

If we replace this last equation in the consequent we get:

$F_{n}F_{n+1} + F_{n+1}^2 = F_{n+1}F_{n+2}$

Finally, if we divide both sides by $F_{n+1}$ we end up with the Fibonacci recurrence equation:

$F_{n+2} = F_{n+1} + F_{n}$

This is the subtle place. We have to prove the consequent ($P_{n+1}$) using the true equality $F_{n+2} = F_{n+1} + F_{n}$, but not to deduce this equality from the consequent. A formally correct argument is, for instance:

“By the above $\sum_{i=1}^{n+1} F_i^2=F_{n}F_{n+1} + F_{n+1}^2=(F_{n} + F_{n+1}) F_{n+1}=F_{n+2} F_{n+1}$, which implies the consequent”.

Answer 2

All the "$\Rightarrow$" that you write are in fact "$\Leftrightarrow$". So you can start from $F_{n+2}=F_{n+1}+F_n$.

Answer 3

You are working from a statement you have to prove to a statement you know is true. This can work but is a bit risky because of the logic.

For example let's say I'm trying to work out if $3=-3$? (Ignoring the fact that it is obviously false). Now if I square both sides then I get that $9=9$ which I know is true and so deduce that $3=-3$ is also true. However, this would clearly be wrong of me. The problem comes because $3=-3 \Rightarrow 9=9$ but $9=9 \nRightarrow 3=-3$. Because in squaring the logic only goes one way (this is because the function is not injective).

For a logic deduction to be correct, you have to have a truthful statement implying the statement you are trying to determine/prove the truth of. The problem with your answer is that it is similar to the $3=-3$ answer in its structure. This can work if you show that all the logic works in reverse as well, which in this case (unlike the $3=-3$ example) I think it does (although you'd need to show that).

A possibly preferable approach is to work from what you know to be true, towards what you need to prove, and only in that direction. This can be done by factorising your expression on the right of $$\sum_{i=1}^{n+1} F_i^2 = F_{n}F_{n+1} + F_{n+1}^2$$ and working from there.

Answer 4

I’m just a last year high school student so, take what I’m saying with a grain of salt. But isn’t the entire point of induction is that you "assume" the statement is true and if the result comes out logically then it is true. Lets take this example and prove through induction:

$\sum_{n=1}^{\infty}n = 1$ for $n\in[1, \infty)$

When $n=1$

$LHS=RHS$

Know we ASSUME the thesis or statement is true for all positive integers $n=k$

$\sum_{n=1}^{\infty}k = 1$

We then solve it to prove its wrong even though we assumed its true. So, if I was you, I might ask the professor for proof on the invalidity of your proof.

Answer 5

This identity is readily proved from the Fibonacci mosaic, as seen in the image below $$\sum_{i=1}^{n} F_i^2 = F_nF_{n+1}$$