(50g) Nth Fibonacci Number

02272015, 05:58 AM
Post: #13




RE: (50g) Nth Fibonacci Number
A poor man's approach to solve the recurrence would be to use the ansatz
\(x_n=\alpha\cdot\phi^n\) Insert this into the recursive definition \(x_{n+2}=x_{n+1}+x_n\): \(\alpha\cdot\phi^{n+2}=\alpha\cdot\phi^{n+1}+\alpha\cdot\phi^n\) Divide both sides by \(\alpha\cdot\phi^n\): \(\phi^2=\phi+1\) This is the quadratic equation for the golden ratio which has two solutions: \(\phi_1,\phi_2\) Now use the linear combination of both: \(x_n=\alpha_1\cdot\phi_1^n+\alpha_2\cdot\phi_2^n\) The initial values \(x_0=0\) and \(x_1=1\) can be used to determine the unknown factors \(\alpha_1\) and \(\alpha_2\). Definitely not as cool as using generating functions and partial fraction decomposition and stuff. Cheers Thomas PS: I feel a little bit like cheating as there's no explanation for why this ansatz works. 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)