Fibonacci Recurrence Relations

Question

Solve the recurrence relation $f(n) = f(n − 1) + f(n − 2)$ with initial conditions $f(0)=1$, $f(1)=2.$

So I understand that it grows exponentially so $f(n) = r^n$ for some fixed $r$. This means substituting this $r^n = r^n-1 + r^n-2$ which gives the characteristic equation of $r ^ 2 - r - 1 = 0$. I'm not 100% sure where to move on from here.

While there is a full and correct solution, it is worth pointing out a small correction to your argument. The growth of the sequence can be seen to be exponential growth, but that doesn't mean that $r^n$ is necessarily a solution. You guess a solution of that type, use the recurrence relation to get two possible solutions, use linearity of the relation to see that any linear combination of the two will also be a solution, then use that flexibility (2 equations, 2 unknowns) to math to the initial conditions. With retrospect, we can understand why the method works and use it more (continued) — Aaron, May 23 '17 at 01:45
....generally, but until you've developed more machinery and a different perspective, you should think about this in terms of "guess a solution, see how well it works, try to patch the holes to make everything good." — Aaron, May 23 '17 at 01:46

score 2 · Accepted Answer · answered May 22 '17 at 23:59

2

Now that you have $$r^2-r-1=0$$ solve for $r$ to get $$r=\frac{1\pm \sqrt{5}}{2}$$ now let $$r_+=\frac{1+ \sqrt{5}}{2}$$ and $$r_-=\frac{1- \sqrt{5}}{2}$$ And let us define the two sequences $a_n$ and $b_n$ as $$a_n=r_+^n$$ $$b_n=r_-^n$$ We can say that $$f(n)=c_1a_n+c_2b_n$$ Where $c_1$ and $c_2$ are some constants, since $a_n$ and $b_n$ both have the property that each term is the sum of the previous two. Now you need to find $c_1$ and $c_2$ so that $$c_1a_0+c_2b_0=2$$ $$c_1a_1+c_2b_1=1$$ Can you solve the system to find $c_1$ and $c_2$? Once you do that, you will have your formula: $$f(n)=c_1a_n+c_2b_n$$

answered May 22 '17 at 23:59

Franklin Pezzuti Dyer

39,754
9
73
166

Ah I see so you use a quadratic formula to solve for r. Can I use simultaneous equations to solve for c1 and c2 ? – M.Jones May 23 '17 at 00:02
wouldn't I have to just solve for a0,b0,a1,b1 ? instead of C? – M.Jones May 23 '17 at 22:58
No. Those are each geometric sequences that I already defined. You can get those values by plugging in $0$ and $1$ for $a_n=r_+^n$ and $b_n=r_-^n$ and then solving for $c_1$ and $c_2$. Once you find the two constants, the explicit formula for $f(n)$ will be $c_1a_n+c_2b_n$, or $c_1r_+^n+c_2r_-^n$ – Franklin Pezzuti Dyer May 23 '17 at 23:05
Why does it have to be 0 and 1 ? like is there any significance ? – M.Jones May 23 '17 at 23:26
Yes, since you want the 0th term to be $2$ and the 1st term to be $1$. That was part of the question. – Franklin Pezzuti Dyer May 23 '17 at 23:27
Ahh yeah I see , so I'd go a0 = 0 , a1 = 0 , b0 = 1 , b1 = 1 – M.Jones May 23 '17 at 23:30
then use simultaneous and solve for c1 ,c2 – M.Jones May 23 '17 at 23:31
1

Yep, that is correct. – Franklin Pezzuti Dyer May 23 '17 at 23:34

Cye Waldman · Answer 2 · 2017-05-23T16:33:24.403

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,2 \text{ & } f_1=1$.

So, specializing to your case, we can say

$$ \alpha,\beta= \varphi,\psi(=-1/\varphi) $$

which are the usual Fibonacci values, since $a=b=1$. Then,

$$ \begin{align} f_n &=\left(2-\frac{1}{2}\right) \frac{\varphi^n-\psi^n}{\varphi-\psi}+\frac{1}{2} \left(\varphi^n+\psi^n\right)\\ &=\left(\frac{3}{2}\right) \frac{\varphi^n-\psi^n}{\varphi-\psi}+\frac{1}{2} \left(\varphi^n+\psi^n\right)\\ &=\frac{3}{2}F_n+\frac{1}{2}L_n \end{align} $$

where $F_n$ and $L_n$ are the Fibonacci and Lucas sequences, respectively. Of course, this analysis can be customized to any arbitrary initial condition problems.

EDIT NOTE (the following day)

There is a much simpler solution here. The initial conditions are in the Fibonacci sequence $(F_3 \text{ & } F_4)$ and the sequence is the Fibonacci sequence, therefore

$$f_n=F_{n+2}$$

This result is in agreement with my previous result. We can demonstrate that $\frac{3}{2}F_n+\frac{1}{2}L_n=F_{n+2}$ as follows:

$$ 3F_n+L_n=2F_{n+2}\\ L_n=F_n+2F_{n-1}\\ F_{n+2}=F_{n+1}+F_{n}=F_{n}+F_{n-1}+F_{n}=2F_n+F_{n-1}\\ 3F_n+F_n+2F_{n-1}=2(2F_n+F_{n-1}),\quad \text{QED} $$

Disclosure: this post is derived largely from a previous one: Decimal Fibonacci Number?

Fibonacci Recurrence Relations

2 Answers2

Linked

Related