Explicit Formula for the nth Fibonacci Number

[DivGradCurl]

Problem

$$f(x) = \frac{x}{1-x-x^2} = \sum _{n=1} ^{\infty} f_n x^n$$

By writing $$f(x)$$ as a sum of partial fractions, find an explicit formula for the nth Fibonacci number.

My work

$$\frac{x}{1-x-x^2} = \frac{-4}{(2x + \sqrt{5} + 1)(2x - \sqrt{5} + 1)} = \frac{A}{2x + \sqrt{5} + 1} + \frac{B}{2x - \sqrt{5} + 1}$$

Heaviside's method gives:

$$\left. \frac{-4}{2x - \sqrt{5} + 1} = A + \frac{B(2x + \sqrt{5} + 1)}{2x - \sqrt{5} + 1} \right] _{x= -\frac{(\sqrt{5}+1)}{2}} \Longrightarrow A = \frac{2}{\sqrt{5}}$$

$$\left. \frac{-4}{2x + \sqrt{5} + 1} = \frac{A(2x - \sqrt{5} + 1)}{2x + \sqrt{5} + 1} + B \right] _{x= \frac{\sqrt{5}-1}{2}} \Longrightarrow B = -\frac{2}{\sqrt{5}}$$

Thus,

$$f(x) = \frac{2}{\sqrt{5}} \left( \frac{1}{2x + \sqrt{5} + 1} - \frac{1}{2x - \sqrt{5} + 1} \right)$$

Then

$$(2x - \sqrt{5} + 1)^{-1} = \frac{1}{1-\sqrt{5}}\left( 1 + \frac{2x}{1-\sqrt{5}} \right) ^{-1} = \frac{1}{1-\sqrt{5}} \sum _{n=0} ^{\infty} \binom{-1}{n} \left( \frac{2x}{1-\sqrt{5}} \right) ^n = \sum _{n=0} ^{\infty} \frac{(-1)^n 2^n}{\left( 1-\sqrt{5}} \right) ^{n+1}}x^n$$

$$(2x + \sqrt{5} + 1)^{-1} = \frac{1}{\sqrt{5}+1}\left( 1 + \frac{2x}{\sqrt{5}+1} \right) ^{-1} = \frac{1}{\sqrt{5}+1} \sum _{n=0} ^{\infty} \binom{-1}{n} \left( \frac{2x}{\sqrt{5}+1} \right) ^n = \sum _{n=0} ^{\infty} \frac{(-1)^n 2^n}{\left( \sqrt{5}+1} \right) ^{n+1}}x^n$$

$$f(x) = \frac{2}{\sqrt{5}} \left\{ \sum _{n=0} ^{\infty} \left[ \frac{(-1)^n 2^n}{\left( \sqrt{5}+1} \right) ^{n+1}}x^n \right] - \sum _{n=0} ^{\infty} \left[ \frac{(-1)^n 2^n}{\left( 1-\sqrt{5}} \right) ^{n+1}}x^n \right] \right\}$$

What else can I do?

Thanks

 

[Hurkyl]

Find a way to combine the two sums into one. :tongue2:

 

[DivGradCurl]

Yes, I'm a bit confused with such a trivial thing. Let me show you why...

$$f(x) = \frac{1}{\sqrt{5}} \sum _{n=0} ^{\infty} \left[ (-1)^n \left( \frac{2}{ \sqrt{5}+1}} \right) ^{n+1} + (-1)^{n+1} \left( \frac{ 2}{1-\sqrt{5}}}\right) ^{n+1} \right] x^n$$

I've tested my guess, but it doesn't work. I'm having difficulty combining the changing signs. Could you please explain that? Probably, it's just a lapse.

Thanks

 

[Hurkyl]

Then one of your intermediate steps is wrong! Can you think of a good way to test them?

BTW, unless I've made an arithmetic error, your final answer works for me...

(but yes, one of your intermediate steps is wrong)

 

[dextercioby]

Redo all your calculations,beginning with the first line,namely the partial fraction decomposition where u miss the "x".That's why you could't retrieve this formula
where u need to get,formulas #6 & #13

Daniel.

P.S.Try to put the radicals to the numerator...

 

[Zurtex]

HAHAHAHA

Had to prove this in my exam today, it is so much easier than that but I don't know how to help without giving it all away

 

[dextercioby]

HAHAHAHA

Had to prove this in my exam today, it is so much easier than that but I don't know how to help without giving it all away

Happy Birthday,Zurtex!And yes,you're right,let's let him do the calculations...


Daniel.

 

[DivGradCurl]

I couldn't find a way to have the radicals just in the numerator, but here is what I now have:

$$f(x) = \frac{x}{1-x-x^2} = \frac{-4x}{(2x + \sqrt{5} + 1)(2x - \sqrt{5} + 1)} = \frac{A}{2x + \sqrt{5} + 1} + \frac{B}{2x - \sqrt{5} + 1}$$

Heaviside's method gives:

$$\left. \frac{-4x}{2x - \sqrt{5} + 1} = A + \frac{B(2x + \sqrt{5} + 1)}{2x - \sqrt{5} + 1} \right] _{x= -\frac{(\sqrt{5}+1)}{2}} \Longrightarrow A = \frac{-\sqrt{5}}{5}-1$$

$$\left. \frac{-4x}{2x + \sqrt{5} + 1} = \frac{A(2x - \sqrt{5} + 1)}{2x + \sqrt{5} + 1} + B \right] _{x= \frac{\sqrt{5}-1}{2}} \Longrightarrow B = \frac{\sqrt{5}}{5}-1$$

Then

$$f(x) = \left( \frac{-\sqrt{5}}{5}-1 \right) \sum _{n=0} ^{\infty} \left[ \frac{(-1)^n 2^n}{\left( \sqrt{5}+1} \right) ^{n+1}}x^n \right] + \left( \frac{\sqrt{5}}{5}-1 \right) \sum _{n=0} ^{\infty} \left[ \frac{(-1)^n 2^n}{\left( 1-\sqrt{5}} \right) ^{n+1}}x^n \right]$$

Thanks for pointing it out

 

[dextercioby]

Sorry,i was referring to the last line.The last formula should be "adjusted" as to resemble the famous one which appears on the "wolfram" site...

Daniel.

 

[Hurkyl]

I couldn't find a way to have the radicals just in the numerator, but here is what I now have:

You recall the method of rationalizing the denominator?

 

[DivGradCurl]

I've just confirmed what I said earlier... memory lapse :rofl:. Anyway...

$$f(x) = \frac{x}{1-x-x^2} = \frac{-4x}{(2x + \sqrt{5} + 1)(2x - \sqrt{5} + 1)} = -4x \left( \frac{2x-\sqrt{5}+1}{4x^2 + 4x -4} \right) \left( \frac{2x+\sqrt{5}+1}{4x^2 + 4x -4} \right) = \frac{-4x}{4x^2 + 4x -4}$$

$$f(x) = -4x \left\{ \frac{1}{4x(x+1)} \left[ 1 - \frac{1}{x(x+1)} \right] ^{-1} \right\} = \frac{-1}{x+1} \sum _{n=0} ^{\infty} \binom{-1}{n} \left[ \frac{-1}{x(x+1)} \right] ^n = - \sum _{n=0} ^{\infty} \frac{1}{x^n (x+1)^{n+1}}$$

There probably is something else that I miss here.

 

[dextercioby]

What did u do here?Where did the radicals go...??

Daniel.

 

[DivGradCurl]

I did not use partial fractions at all in my previous post, which is not what I intended to do. By the way, I finally have the solution. :tongue:

$$f(x) = \frac{x}{1-x-x^2} = \frac{-4x}{(2x + \sqrt{5} + 1)(2x - \sqrt{5} + 1)} = \frac{A}{2x + \sqrt{5} + 1} + \frac{B}{2x - \sqrt{5} + 1}$$

Heaviside's method gives:

$$\left. \frac{-4x}{2x - \sqrt{5} + 1} = A + \frac{B(2x + \sqrt{5} + 1)}{2x - \sqrt{5} + 1} \right] _{x= -\frac{(\sqrt{5}+1)}{2}} \Longrightarrow A = \frac{-\sqrt{5}}{5}-1$$

$$\left. \frac{-4x}{2x + \sqrt{5} + 1} = \frac{A(2x - \sqrt{5} + 1)}{2x + \sqrt{5} + 1} + B \right] _{x= \frac{\sqrt{5}-1}{2}} \Longrightarrow B = \frac{\sqrt{5}}{5}-1$$

Also consider

$$(2x + \sqrt{5} + 1) ^{-1} = \frac{1}{\sqrt{5}+1} \left( 1 + \frac{2x}{\sqrt{5}+1} \right) ^{-1} = \frac{\sqrt{5}-1}{4} \sum _{n=0} ^{\infty} \binom{-1}{n} \left( \frac{2x}{\sqrt{5}+1} \right) ^n = \frac{\sqrt{5}-1}{4} \sum _{n=0} ^{\infty} \left( \frac{1-\sqrt{5}}{2} \right) ^n x^n$$

and

$$(2x - \sqrt{5} + 1) ^{-1} = \frac{1}{1-\sqrt{5}} \left( 1 + \frac{2x}{1-\sqrt{5}} \right) ^{-1} = \frac{-\left( 1 + \sqrt{5} \right)}{4} \sum _{n=0} ^{\infty} \binom{-1}{n} \left[ \frac{-\left( 1 + \sqrt{5} \right)}{2} x \right] ^n = \frac{-\left( 1 + \sqrt{5} \right)}{4} \sum _{n=0} ^{\infty} \left( \frac{1+\sqrt{5}}{2} \right) ^n x^n$$

which allows us to obtain

$$f(x) = \frac{A}{2x + \sqrt{5} + 1} + \frac{B}{2x - \sqrt{5} + 1} = \left( \frac{-\sqrt{5}}{5}-1 \right) \left( \frac{\sqrt{5}-1}{4} \right) \sum _{n=0} ^{\infty} \left[ \left( \frac{1-\sqrt{5}}{2} \right) ^n x^n \right] + \left( \frac{\sqrt{5}}{5}-1 \right) \left[ \frac{-\left( 1 + \sqrt{5} \right)}{4} \right] \sum _{n=0} ^{\infty} \left[ \left( \frac{1+\sqrt{5}}{2} \right) ^n x^n \right]$$

$$f(x) = \frac{-1}{\sqrt{5}} \sum _{n=0} ^{\infty} \left[ \left( \frac{1-\sqrt{5}}{2} \right) ^n x^n \right] + \frac{1}{\sqrt{5}} \sum _{n=0} ^{\infty} \left[ \left( \frac{1+\sqrt{5}}{2} \right) ^n x^n \right] = \frac{1}{\sqrt{5}} \sum _{n=0} ^{\infty} \left[ \left( \frac{1+\sqrt{5}}{2} \right) ^n - \left( \frac{1-\sqrt{5}}{2} \right) ^n \right] x^n$$

Hence, we find

$$F_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right) ^n - \left( \frac{1-\sqrt{5}}{2} \right) ^n \right]$$

And again, thank you guys for all the help!