\(if\quad { x }^{ 2 }=x+1\quad and\quad n\ge 2\quad Then\quad { x }^{ n }={ f }_{ n }x+{ f }_{ n-1 }\)

Can anybody provide me a derivation for this Lemma ? I was able to prove this lemma by applying the principle of mathematical induction. However I believe there are variety of proofs and derivations for this lemma. It would be better if all the proofs and derivations are posted in this note. A BIG THANKS to contributors.

## Comments

Sort by:

TopNewestWell, use Binet's Formula. You will get it. It's easy. Binet's formula is \({f}_{k} = \frac{{\phi}^{k} - {(1-\phi)}^{k}}{\sqrt{5}}\) – Kartik Sharma · 1 year, 10 months ago

Log in to reply

Golden ratio:\({ x }^{ 2 }=x+1\)

It is also given that \(n\ge 2\)

Now,\(\quad { x }^{ 3 }={ x }^{ 2 }.x\\ \therefore \quad { x }^{ 3 }=(x+1).x\quad ....{ (x }^{ 2 }=x+1)\\ \therefore \quad { x }^{ 3 }={ x }^{ 2 }+x\\ \therefore \quad { x }^{ 3 }=2x+1\quad ....{ (x }^{ 2 }=x+1)\)

Similarly it can be proven that,

\({ x }^{ 4 }=3x+2\\ { x }^{ 5 }=5x+3\\ { x }^{ 6 }=8x+5\)

Thus we can conclude that \({ x }^{ n }={ f }_{ n }x+{ f }_{ n-1 }\)

We know the fact that the roots of golden ratio are \(\phi \) and \(1-\phi\)

Now we can deduce two equations:

\({ \phi }^{ n }=f_{ n }\phi +{ f }_{ n-1 }\quad \quad \quad \quad \quad \quad \quad \quad ....1)\\ (1-{ \phi ) }^{ n }=f_{ n }(1-\phi )+{ f }_{ n-1 }\quad \quad ....2)\)

Subtract equation 2 from 1 to yield Binet's formula

This was taught to me by my cousin. So, from above, I think Binet's formula was derived from this lemma. – Inderjeet Nair · 1 year, 10 months ago

Log in to reply

– Kartik Sharma · 1 year, 10 months ago

Yeah I thought of that too but I thought Binet's formula would have been better.Log in to reply

– Inderjeet Nair · 1 year, 10 months ago

Can you please explain in detail on how we can use this formula to derive the above Lemma?Log in to reply

To prove the binets formula, i will give a hint

the

nthfibonnaci (\(f_n\) ) number is the coefficient of \(x^n\) in\(\frac {1}{1-x-x^2}\)

now use partial fraction to break it down, you will know your answer as soon as you will do that

btw \(\phi \quad\) is one of the roots of the denominator of the infinite polynomial i gave

(note that the denominator is not the same quadratic as the one you gave, but the roots of this one and the one you gave are very common, you will see) – Mvs Saketh · 1 year, 10 months ago

Log in to reply

– Inderjeet Nair · 1 year, 10 months ago

Can you please elaborate.Log in to reply

can you please tell what \(f_n\) stands for? – Mvs Saketh · 1 year, 10 months ago

Log in to reply

– Saigeetha Jayakumar · 1 year, 10 months ago

Fn is the nth fibonacci numberLog in to reply