Using backtracking to convert from recursive to explicit formula How do I use backtracking to convert $a_n=a_{n-1}+a_{n-2}$ into an explicit formula?
I am stuck. Please guide me through the correct method.
Thank you for any comments/answers ~
 A: You can't have an explicit formula without starting conditions. But I guess you want the Fibonacci sequence so the starting conditions will be $a_0=a_1=1$. First of all let's use the characteristic polynomial of the definition which is $x^2-x-1$ (we got it by assuming the solution is of the form $a_n=\lambda n.n^c$ and moving sides, because you can get all the solutions using a linear combination of 2 solutions then we can just use these 2 solutions to find the rest). Now we can find it's roots which are $\frac{1\pm\sqrt{5}}{2}$. From that we get that the solution is of the form $a_n=\lambda n.A\cdot \left(\frac{1-\sqrt{5}}{2}\right)^n+B\cdot \left(\frac{1+\sqrt{5}}{2}\right)^n$. without starting conditions you can't know $A,B$ but if we assume $a_0=a_1=1$ then we can just solve an equation:
$$a_0=A+B=1 \\ a_1=A\cdot \frac{1-\sqrt{5}}{2}+B\cdot \frac{1+\sqrt{5}}{2}=1$$
If we solve that equation system we get that $A=\frac{5-\sqrt{5}}{10},B=\frac{5+\sqrt{5}}{10}$ and then we get:
$$a_n=\lambda n.\frac{5-\sqrt{5}}{10}\cdot \left(\frac{1-\sqrt{5}}{2}\right)^n+\frac{5+\sqrt{5}}{10}\cdot \left(\frac{1+\sqrt{5}}{2}\right)^n$$
and that would be a closed form formula for the Fibonacci numbers and you could use this method.
A: $a_0 = A$
$a_1 = B$
$a_2=a_0+a_1=A+B$
$a_3=a_2+a_1=A+B+A=2A+B$
$a_4=a_3+a_2=2A+B+A+B=3A+2B$
...
$a_n=a_{n-1}+a_{n-2}=Ф_{n-1}A+Ф_{n-2}B$
where $Ф_k$ is k-th fibonacci number
