# Prove that $E_{n+1}= F_nA + F_{n+1}B$

We have the following definitions

$E_0 =A, E_1=B,$

$E_{n+2} = E_{n+1} +E_n$, for $n \geq 0$

This is my scratch work

$E_0=A, E_1 = B, E_2= A+B, E_3= A +2B, E_4= 2A+3B, E_5= 3A +5B, E_6= 5A + 8B...$

Noticing that the coefficients of these equations are the Fibonacci numbers we can directly see that

$E_{n+1}= F_nA + F_{n+1}B$

Is this a good enough proof? I realized I didn't use this relation $E_{n+2} = E_{n+1} +E_n$, but I did not see it necessary.

• how do you go from what you have noticed (which includes up to only $E_6$) to what you concluded ($E_{n+1}$, for all $n$) ? – Mirko Apr 24 '17 at 2:07
• @Mirko Should I do a prove by induction on n? – Squanchinator Apr 24 '17 at 2:13
• yes, that would be an option (and would consist a proof :) – Mirko Apr 24 '17 at 2:20

Induction is really the easiest route:

Just sum

$\quad E_{n}= F_{n-1}A + F_{n}B$

$\quad E_{n+1}= F_nA + F_{n+1}B$

to get

$\quad E_{n+2}= F_{n+1}A + F_{n+2}B$

Here is a formal derivation of your result. The sequence you have found is a generalization of the Fibonacci sequence.

There have been many extensions of the sequence with adjustable (integer) coefficients and different (integer) initial conditions, e.g., $f_n=af_{n-1}+bf_{n-2}$. (You can look up Pell, Jacobsthal, Lucas, Pell-Lucas, and Jacobsthal-Lucas sequences.) Maynard has extended the analysis to $a,b\in\mathbb{R}$, (Ref: Maynard, P. (2008), “Generalised Binet Formulae,” $Applied \ Probability \ Trust$; available at http://ms.appliedprobability.org/data/files/Articles%2040/40-3-2.pdf.)

We have extended Maynard's analysis to include arbitrary $f_0,f_1\in\mathbb{R}$. It is relatively straightforward to show that

$$f_n=\left(f_1-\frac{af_0}{2}\right) \frac{\alpha^n-\beta^n}{\alpha-\beta}+\frac{f_0}{2} (\alpha^n+\beta^n)$$

where $\alpha,\beta=(a\pm\sqrt{a^2+4b})/2$.

The result is written in this form to underscore that it is the sum of a Fibonacci-type and Lucas-type Binet-like terms. It will also reduce to the standard Fibonacci and Lucas sequences for $a=b=1 \ \text{and} \ f_0=0, f_1=1$.

So, specializing to your case, we can say

$$E_n=\left(B-\frac{A}{2} \right)F_n+\frac{A}{2}L_n$$

where

$$F_n,L_n=\frac{\varphi^n \mp \psi^n}{\varphi \mp \psi}\\ \varphi,\psi=(1\pm \sqrt{5})/2$$

Ergo,

$$E_n=BF_n+\frac{A}{2}(L_n-F_n)=AF_{n-1}+BF_n$$

since $L_n-F_n=2F_{n-1}$.

This proves the OP's assertion.