# Fibonacci recurrence relation - Principle of Mathematical Induction

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?

• The proof is fine, if awkwardly written. You need to point out that at each step the implications go both ways. – lulu Apr 20 at 13:28
• I still don't understand why I should show that the implication goes both ways. – mateleco Apr 20 at 14:14
• Because, as written, you assume the desired result when you write $\sum_{i=1}^{n+1}F_i^2=F_nF_{n+1}+F_{n+1}^2=F_{n+1}F_{n+2}$ . You then deduce from that a true fact, namely the usual Fibonacci recursion. But so what? Knowing that $B$ is true and that $A\implies B$ tells me nothing at all about $A$. Of course knowing that $B$ is true and that $A\iff B$ does prove $A$. – lulu Apr 20 at 14:17
• But in that step, I did not want to demonstrate that the antecedent is true, I just wanted to demonstrate 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}$ is true. – mateleco Apr 20 at 14:32
• Then, in (1) I prove that the initial case ($n = 1$) holds. If it holds, since I know 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}$, then $\sum_{i=1}^{n} F_i^2 = F_nF_{n+1}$ holds for all n. – mateleco Apr 20 at 14:36

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”.

• Thank you very much for your proof and corrections. "We have to prove the consequent (Pn+1) using the true equality Fn+2=Fn+1+Fn, but not to deduce this equality from the consequent." Okay, this makes a lot of sense now. So I was proving that $A \land B$, instead of $A \implies B$, but doesn't $A\land B \implies (A \rightarrow B)$? – mateleco Apr 23 at 5:52
• @mateleco Right, $A\wedge B$ implies $A\to B$ because if $A\wedge B$ then both $A$ and $B$ are true. But we don’t prove $P_n \wedge P_{n+1}$, because we already assumed $P_n$. I guess that it can be stated more clear that we not only “replace this last equation in the consequent” (that is reformulate the consequent), but to prove the consequent. – Alex Ravsky Apr 23 at 6:07
• Your should know better than me what you proved, :-) but this formalisation of your arguments looks plausible. I only add the following small remark to the last sentence. Since we proved that $P_{n}\to P_{n+1}$ is true, formally $S\Rightarrow (P_{n}\to P_{n+1})$ is true too for any admissible statement $S$. :-) But $P_{n}\to P_{n+1}$ needs to be proved first. – Alex Ravsky Apr 23 at 8:36

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}$$

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

• Sorry. If you start from $F_{n+2}=F_{n+1}+F_n$ then you multiply by $F_{n+1}$. Then $F_{n+1}F_{n+2}=F_{n+1}^2+F_nF_{n+1}$. Replace your induction hypothesis and you get thesis. – El31 Apr 20 at 13:23

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.

• I also understood your example: $(a = b) \implies (a^2 = b^2)$, but the contrapositive is not true: $(a^2 = b^2)$ does not imply $(a = b)$. – mateleco Apr 20 at 18:27
• "A possibly preferable approach is to work from what you know to be true". My only question now is: how do you know $\sum_{i=1}^{n+1} F_i^2 = F_{n}F_{n+1} + F_{n+1}^2$ is true? – mateleco Apr 20 at 18:34
• As far as I know, that expression comes from the assuption of $\sum_{i=1}^{n} F_i^2 = F_nF_{n+1}$, but we don't know whether it is true or not. – mateleco Apr 20 at 19:06
• We assume that it works for some value of n, then use this argument to show that it works for the next value of n. This in turn means it works for the next one, and thus the next one and so on for all integers. However, you are right in saying that there seems to be a hole in the logic at the start. This is what the base case is needed for (when you've got n=1). You manually show that this is true, then the argument implies that n=2 also works, thus n=3, n=4, etc. That is the principle of mathematical induction. Google mathematical induction if you're struggling to get your head around it. – Joz Apr 20 at 21:21
• Exactly. That was what I was referring to. Nice explanation of mathematical induction. – mateleco Apr 20 at 21:27

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.

• I always recommend this answer for people having trouble with induction. Once you have the base case, you assume it is true for $k$ and prove it is true for $k+1$. You are not assuming what you want to prove because you are proving it for one more down the line. – Ross Millikan Apr 20 at 14:25
• @RossMillikan Statements like "You are not assuming what you want to prove because you are proving it for one more down the line." are HIGHLY ambiguous and should be avoided at all costs. I don't know if you're saying (1) you are not assuming what you want to prove, and the reason is that you are proving it for one more down the line or (2) You might be assuming it, but the reason you would be is not because you are proving it for one more down the line. I actually don't know what you're saying. – mathworker21 Apr 22 at 22:05