Post Reply 
(50g) Nth Fibonacci Number
02-27-2015, 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.
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: (50g) Nth Fibonacci Number - Gerald H - 02-22-2015, 09:48 AM
RE: (50g) Nth Fibonacci Number - Joe Horn - 02-22-2015, 09:06 PM
RE: (50g) Nth Fibonacci Number - Offroad - 02-23-2015, 03:07 AM
RE: (50g) Nth Fibonacci Number - rprosperi - 02-26-2015, 01:42 PM
RE: (50g) Nth Fibonacci Number - Han - 02-26-2015, 07:39 PM
RE: (50g) Nth Fibonacci Number - rprosperi - 02-26-2015, 08:23 PM
RE: (50g) Nth Fibonacci Number - Joe Horn - 02-26-2015, 10:19 PM
RE: (50g) Nth Fibonacci Number - Han - 02-27-2015, 03:29 AM
RE: (50g) Nth Fibonacci Number - rprosperi - 02-27-2015, 01:31 PM
RE: (50g) Nth Fibonacci Number - rprosperi - 02-27-2015, 01:43 PM
RE: (50g) Nth Fibonacci Number - Thomas Klemm - 02-27-2015 05:58 AM
RE: (50g) Nth Fibonacci Number - rprosperi - 02-27-2015, 01:48 PM
RE: (50g) Nth Fibonacci Number - Han - 02-27-2015, 02:22 PM
RE: (50g) Nth Fibonacci Number - Gerald H - 02-27-2015, 03:27 PM



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