2
$\begingroup$

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.

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ 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$) ? $\endgroup$ – Mirko Apr 24 '17 at 2:07
  • $\begingroup$ @Mirko Should I do a prove by induction on n? $\endgroup$ – Squanchinator Apr 24 '17 at 2:13
  • $\begingroup$ yes, that would be an option (and would consist a proof :) $\endgroup$ – Mirko Apr 24 '17 at 2:20
2
$\begingroup$

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$

| cite | improve this answer | | | | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$

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.