(50g) Nth Fibonacci Number

[Thomas Klemm]

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.