(50g) Nth Fibonacci Number
02-27-2015, 03:29 AM (This post was last modified: 02-27-2015 03:31 AM by Han.)
Post: #11
 Han Senior Member Posts: 1,883 Joined: Dec 2013
RE: (50g) Nth Fibonacci Number
Another way to produce the constants obtained in Eddie's solution is to use formal series and generating functions to solve recurrence equations. Let $$a_n$$ denote the $$n$$th term, and let
$f(x) = \sum_{n=0}^\infty a_n x^n$
$a_{n+2} = a_{n+1} + a_{n} \quad \Longrightarrow \quad a_{n+2}\cdot x^{n+2} = x \cdot a_{n+1}\cdot x^{n+1} + x^2 \cdot a_n \cdot x^n$
Summing each side with $$n = 0, 1, 2, \dotsm$$ produces
$\sum_{n=0}^\infty a_{n+2} x^{n+2} = x \sum_{n=0}^\infty a_{n+1}x^{n+1} + x^2 \sum_{n=0}^\infty a_n x^n \quad \Longrightarrow \quad f(x)-a_1 x - a_0 = x \cdot [ f(x)-a_0 ] + x^2f(x)$
Solve for $$f(x)$$ to obtain
$f(x) = \frac{a_1 x -a_0x + a_0}{1-x-x^2} = \frac{1}{1-x-x^2}$
In the last equality, we (for simplicity's sake) assume that $$a_0 = a_1 = 1$$. Using a partial fraction decomposition with $$\alpha = -\frac{1}{2}(1-\sqrt{5})$$ and $$\beta = -\frac{1}{2}(1+\sqrt{5})$$ gives
$f(x) = \frac{-1}{(x-\alpha)(x-\beta)} = \frac{A}{x-\alpha} + \frac{B}{x-\beta}$
or
$-1 = A\cdot (x-\beta) + B\cdot (x-\alpha)$
Letting $$x= \alpha$$ and then $$x=\beta$$ produces $$A = -\frac{1}{\alpha-\beta} = -\frac{1}{\sqrt{5}}$$ and $$B = \frac{1}{ \sqrt{5}}$$ respectively. Now rewrite $$f(x)$$ as a sum of power series:
$f(x) = \frac{1}{\sqrt{5}} \left( -\frac{1}{x-\alpha} + \frac{1}{x-\beta} \right) = \frac{1}{\sqrt{5}}\left( \frac{1}{\alpha-x} - \frac{1}{\beta-x}\right) = \frac{1}{\sqrt{5}} \left( \frac{1}{\alpha\cdot (1-\frac{x}{\alpha})} - \frac{1}{\beta \cdot (1-\frac{x}{\beta})} \right) = \frac{1}{\sqrt{5}} \left( \frac{1}{\alpha} \sum_{n=0}^\infty \left(\frac{x}{\alpha}\right)^n - \frac{1}{\beta} \sum_{n=0}^\infty \left( \frac{x}{\beta}\right)^n \right)$
by making use of the identity
$\frac{1}{1-t} = \sum_{n=0}^\infty t^n$
So
$f(x) = \sum_{n=0}^\infty \underbrace{\frac{1}{\sqrt{5}}\left( \frac{1}{\alpha^{n+1}}-\frac{1}{\beta^{n+1}}\right)}_{\text{ this is } a_n} x^n$
The exponent $$n+1$$ (as opposed to $$n$$ ) is due to us setting $$a_0 = 1$$ and not $$a_0 = 0$$.

Graph 3D | QPI | SolveSys
 « 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)