(50g) Nth Fibonacci Number
02-27-2015, 05:58 AM
Post: #13
 Thomas Klemm Senior Member Posts: 1,545 Joined: Dec 2013
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 »

 Messages In This Thread (50g) Nth Fibonacci Number - Eddie W. Shore - 02-21-2015, 03:31 PM 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 - Thomas Klemm - 02-26-2015, 10:45 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 - Thomas Klemm - 02-26-2015, 11:04 PM RE: (50g) Nth Fibonacci Number - Thomas Klemm - 02-27-2015, 05:10 AM 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 RE: (50g) Nth Fibonacci Number - Thomas Klemm - 03-02-2015, 02:11 AM

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