Well, I have the following two problems involving Fibonacci sequences and Lucas numbers.

I know that they share the same technique, but I don't have clear the procedure:

$$f_n = f_{n-1} + f_{n-2}: f_0 =0, f_1=1$$

$$l_n=l_{n-1} +l_{n-2}:l_0=2,l_1=1$$

Now, I want to prove that:

$$\sum\limits_{k=0}^nf_k= f_{n+2}-1 $$

$$\sum\limits_{k=0}^n l_k^2= l_nl_{n+1} +2$$

My question is, what kind of technique should be used to deal with such problems?


2 Answers 2


Both Fibonacci and Lucas numbers can be expressed as $f_n = a \alpha^n + b \beta^n$, for some $a,b \in \mathbb R$ (different pairs for each sequence), where $\alpha,\beta$ are the roots of $X^2=X+1$. (Their precise value is not really important here.)

This allows us to find $\sum\limits_{k=1}^nf_k$ by simply summing two geometric series:

$$ \sum\limits_{k=1}^nf_k = \sum\limits_{k=0}^nf_k = a \sum\limits_{k=0}^n\alpha^k + b \sum\limits_{k=0}^n\beta^k = a\frac{\alpha^{n+1}-1}{\alpha-1}+b\frac{\beta^{n+1}-1}{\beta-1} = a(\alpha^{n+2}-\alpha)+b(\beta^{n+2}-\beta)\\= f_{n+2}-(a\alpha+b\beta)=f_{n+2}-f_1=f_{n+2}-1 $$


You can use strong induction over $n$.

For the Fibonacci numbers:

The base case ($n=0$) holds, since $f_0 = f_2 -1$

Induction hypothesis: Assume that $\sum_{k=1}^m f_k=f_{m+2}-1$ holds for all $m \leqslant n$.

Now we want to show that $f_{n+3}-1=\sum_{k=1}^{n+1} f_k$.

$$\begin{align} f_{n+3}-1 &= f_{n+1} + f_{n+2} -1\\ &=\{\text{induction hypothesis}\}\\ &=\sum_{k=1}^{n-1}f_k+1+\sum_{k=1}^{n}f_k+1-1\\ &=\color{red}{f_1}+\color{blue}{f_2}+\dots+\color{cyan}{f_{n-1}}+\color{green}{f_1}+\color{red}{f_2}+\color{blue}{f_3}+\dots+\color{cyan}{f_{n}}+1\\ &=\color{green}{f_1}+\color{red}{f_1+f_2}+\color{blue}{f_2+f_3}+\dots+\color{cyan}{f_{n-1}+f_n}+1\\ &=\color{green}{f_1}+\color{red}{f_3}+\color{blue}{f_4}+\dots+\color{cyan}{f_{n+1}}+1\\ &=\color{green}{f_1}+\sum_{k=1}^{n+1}f_k - f_1-f_2+1\\ &= \sum_{k=1}^{n+1}f_k \end{align}$$


A similar argument can be made for the Lucas numbers.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.