Using backtracking to convert from recursive to explicit formula

Question

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 ~

Answer 1

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.