if you cant see or that picture seem not clear , please feel free to ask me, thank you

if you cant see or that picture seem not clear , please feel free to ask me, thank you

No vote yet

11 votes

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

TopNewestThe generating function for the Fibonacci numbers is \(G(x) = \frac{x}{1-x-x^2}\). (Think of the infinite geometric series and what terms combine to make \(x^n\)...). So, you want to solve \(\frac{a}{1-a-a^2} = 2\) or \(2a^2 +3a -2 = 0\). Since we must have \(0<a<\frac{\sqrt{5}-1}{2}\), this leaves \(a=\frac{1}{2}\). – Eric Edwards · 4 years ago

Log in to reply

– Tim Vermeulen · 4 years ago

Could you elaborate on how you found that closed form?Log in to reply

\( G(x) = x+x^2+2 x^3+3 x^4+5 x^5+8 x^6+13 x^7+\text{...} \)

\( \frac{G(x)}{x} = 1+x+2 x^2+3 x^3+5 x^4+8 x^5+13 x^6+\text{...} \)

\( \frac{G(x)}{x}-G(x) = 1+x^2+x^3+2 x^4+3 x^5+5 x^6+8 x^7+\text{...} \)

\( x G(x) = x^2+x^3+2 x^4+3 x^5+5 x^6+8 x^7+13 x^8+\text{...} \)

And finally,

\( \frac{G(x)}{x}-G(x)-x G(x)=1 \)

Solve this for \( G(x) \) to get \( G(x) = \frac{x}{1−x−x^2} \) – Ivan Stošić · 4 years ago

Log in to reply

– Tim Vermeulen · 4 years ago

Wow, that's amazing. It's like the first time I saw a proof of the sum of a geometric series, where suddenly all the terms canceled out.Log in to reply

Wilf's Generatingfunctionology, which deals with formal generating functions. The second edition is available online for free on the author's site. Using this, you can actually generate a formal proof. – George Williams · 4 years ago

I highly recommendLog in to reply

– Tim Vermeulen · 4 years ago

That's looking really good, thank you.Log in to reply

– NurFitri Hartina · 4 years ago

that's very nice book, thanksLog in to reply