# How to prove Fibonacci summation? [closed]

How would I prove the following statement:

$\forall n \in \mathbb{N}$,

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

where $F_{k}$ denotes the $k^{th}$ Fibonacci number.

I understand that I'd have to use mathematical induction to prove this, but how would I formally write out a proof for this?

I'm also a little confused about the logic/algebra behind Fibonacci, once I begin to solve this.

Thank you!

## closed as off-topic by Namaste, Daniel W. Farlow, Shailesh, Alex Provost, JonMark PerryJul 12 '17 at 4:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Namaste, Daniel W. Farlow, Shailesh, Alex Provost, JonMark Perry
If this question can be reworded to fit the rules in the help center, please edit the question.

• Verify it is true for $n=1$, then assume $$\sum_{k=1}^{n-1} F_{k}^{2} = F_{n-1}F_{n}$$ and add $F_n^2$ to both sides. – N74 Jul 11 '17 at 20:13
• might not really be what you're after, but here's a nice visual proof. – Dando18 Jul 11 '17 at 20:22

## 3 Answers

Note I'm using the definition of Fibonacci Numbers where: \begin{align*} F_1 & = 1 \\ F_2 & = 1 \end{align*} I'm considering $F_0$ to be "undefined" because it makes the sum on the LHS act a little weird. This is fine - we're using induction to prove it for $n\geq 1$, and can prove it ourselves for $n = 0$ potentially (or leave it be, as I am).

Base Case:

We need to verify it for $n = 1$. This just says that: $$\sum_{k = 1}^1 F_k^2 = F_1 F_2\implies 1^2 = 1\times 1$$ This is clearly true.

Inductive Hypothesis:

Assume that: $$\sum_{k = 1}^{n-1} F_k^2 = F_{n-1} F_{n}$$ Add $F_n^2$ to both sides: $$F_n^2 + \sum_{k =1}^{n-1}F_k^2 = F_{n-1}F_n + F_n^2$$ Note that we can rewrite the left hand side as $\sum_{k = 1}^n F_k^2$, and the right hand side as: $$F_{n-1}F_n + F_n^2 = F_n(F_{n-1}+F_n) = F_nF_{n+1}$$ where the last equality is from how the Fibonacci sequence is defined.

So, we have that the equality holding for the $n-1$th case implies it holds for the $n$th case, and we've thus finished the induction.

Fibonacci is defined by

$$F_1=F_2=1$$ $$F_{n}=F_{n-1}+F_{n-2}$$

For $n=1$ the statement is true:

$$F_1^2=1^2=1\cdot 1=F_1\cdot F_2$$

Assume it is true for $n=m$:

$$\sum_{k=1}^{m}F_k^2=F_m F_{m+1}$$

This implies that it is true for $n=m+1$ : $$\sum_{k=1}^{m+1}F_k^2=\sum_{k=1}^{m}F_k^2+F_{m+1}^2=F_mF_{m+1}+F_{m+1}^2$$

$$=(F_{m+2}-F_{m+1})F_{m+1}+F_{m+1}^2=F_{m+1}F_{m+2}.$$

Hint: $\;F_{n+1}=F_n+F_{n-1}\,$ by the definition of Fibonacci numbers. Multiplying by $\,F_n\,$ gives:

$$F_{n+1} F_n = F_n^2 + F_{n-1} F_n \quad\iff\quad F_n^2 = F_{n+1} F_n - F_{n} F_{n-1}$$

Summing the latter relation up from $2$ to $n$ and telescoping:

\require{cancel} \begin{align} \sum_{k=2}^{n} F_{k}^{2} &= (\cancel{\color{red}{F_3 F_2}} - F_2 F_1) + (\bcancel{\color{blue}{F_4 F_3}} - \cancel{\color{red}{F_3 F_2}}) + (\cancel{F_5F_4}-\bcancel{\color{blue}{F_4F_3}})+ \cdots + (F_{n+1} F_n - \cancel{F_{n} F_{n-1}}) \\ &= - 1 + F_{n+1} F_n \end{align}