Fibonacci and Lucas series technique

Question

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?

Answer 1

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

Answer 2

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

Q.E.D.

A similar argument can be made for the Lucas numbers.