Find the solution of the recurrence relation $f_n = f_{n-1} + f_{n-2}$ with $f_0 = f_1 = 1$
I had someone show me how to solve/prove this using the linear difference equation, but I had never been exposed to such equation (I think that's more advance than what I'm currently studying), how would I had been able to solve this (without knowing that equation)? Is there a more straight forward solution to this using mathematical induction instead? I was first gonna do $n = 2$, and while that simply shows $f_2 = 2$, that doesn't confirm any base cases (from what I understand anyway) and I can't use $n = 1$ or $n = 0$ (from what I have tried). So I'm assuming do I need some kind of closed form equation on the left hand side or? I'm barely starting to learn proofs, any insight would be grateful. Thanks.
$\endgroup$ 23 Answers
$\begingroup$Suppose I tell you that a sequence ${a_0,a_1,...}$ is defined recursively by:
$$a_{n+1}=3a_{n}$$
Then you notice from this that to get to the next number in the sequence, you multiply by $3$. And by playing around with the sequence, you notice that it's solution is basically:
$$a_n=a_0(3)^n$$
Now suppose I give you:
$$f_{n+2}-f_{n+1}-f_n=0$$
And ask you to solve it.
A good guess to the solution would be something of the form $f_n=c_1r^n$ as we seen from the first example. Here $c_1$ and $r$ are constants. plugging this into the equation above and dividing by $c_1$ on both sides, we get:
$$r^{n+2}-r^{n+1}-r^n=0$$
Dividing by $r^n$ on both sides we get (note that the solution $r=0$ is lost, but it is not that interesting):
$$r^2-r-1=0$$
$$r=\frac{1+\sqrt{5}}{2},\\\ \frac{1-\sqrt{5}}{2}$$
Any choice of $r$ above will satisfy the equation. However if we combine the two possible values of $r$, we get yet another solution:
$$a_n=c_1(\frac{1+\sqrt{5}}{2})^n+c_2(\frac{1-\sqrt{5}}{2})^n$$
In which case now ,given the initial values of your sequence:
$$f_0=1$$
$$f_1=1$$
You may solve for the constants in the equation, and check to make sure that it satisfies all conditions.
$\endgroup$ $\begingroup$Hint:
Search solutions to the recurrence relation in the form $r^n$ (i.e. geometric sequences) for a suitable $r$. This will lead you to a quadratic equation for $r$, with two solutions $r_1$ and $r_2$..
Then check any linear combination of solutions is a solution. Hence for any $\lambda, \mu$, $\lambda r_1^n+\mu r_2^n$ is a solution.
Finally, check there is only one of these solutions that satisfy the initial conditions.
$\endgroup$ 2 $\begingroup$Hint to the hint: As $$f_{n+2} - f_{n+1} - f_n = 0$$, the immediate quadratic equation is $$r^2 - r - 1 = 0$$. If you solve that through $$ x = \frac {-b \pm \sqrt {b^2 - 4ac}}{2a} $$ you will obtain two values: $r_1$ and $r_2$.
As @Bernard says, you have to calculate $\lambda $ and $\mu $ in $f (n) = \lambda r_1^n+\mu r_2^n$, expression that is true for certain lambda and mu for all $n \geq 0$.
For that, try to relate $f (0)$ and $f (1) $ with $\lambda $ and $\mu $ and you will obtain a system with 2 equations and 2 variables.
Solve it and you will obtain lamda and mu. Substitute back and you will obtain what you were looking for:
$$f (n) =\lambda r_1^n+\mu r_2^n$$
$\endgroup$
