Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $F_n$ be the $n$th Fibonacci number. Let $\alpha = \frac{1+\sqrt5}2$ and $\beta =\frac{1-\sqrt5}2$.

How to prove that $\alpha^n=\alpha\cdot F_n + F_{n-1}$?

I'm completely stuck on this question. I've managed to take the equation form of $F$ and come down to:

$$\frac1{\sqrt 5}(\alpha^n(\alpha+\alpha^{-1}) - \beta^n(\alpha+\beta^{-1}))$$

But I'm lost from there on. I'm not looking for the answer, but any pointers would be great :)!

share|improve this question
    
Welcome to Math.SE. Thank you for your question. To help us answer it, please share the context, as well as what you've tried so far. If this is homework, please tag it as such. Also, it will be much easier for everyone if you use MathJax to format your question. –  vadim123 Jun 15 '13 at 13:48
1  
    
@vadim123: done thanks to myuseristhis:). Thanks for the headsup –  Bas Jun 15 '13 at 13:55
    
Are you trying to find out what $\alpha$ and $\beta$ are? I think your coefficients are wrong... –  Goos Jun 15 '13 at 13:55
1  
Do you mean $F_{n+1}$? Alway, what are $\alpha,\beta$? –  Thomas Andrews Jun 15 '13 at 13:58

3 Answers 3

up vote 3 down vote accepted

It's easier to prove this by induction. Note that $F_1\alpha + F_0=\alpha+0=\alpha^1$.

Then use that $\alpha$ is a root of $x^2-x-1=0$ to show that if $\alpha^n=F_n\alpha+F_{n-1}$ then it follows that $\alpha^{n+1}=F_{n+1}\alpha + F_{n}$.

share|improve this answer
    
Could you explain what $\alpha$ is a root of $x^2 -x -1=0$ means? –  Bas Jun 15 '13 at 14:18
    
@Bas: That means that $\alpha$ is a number that satisfies the equation. So we have $\alpha^2-\alpha-1=0$. –  Fredrik Meyer Jun 15 '13 at 14:25

First, for $n=1$, $$ \begin{align} \alpha^1 &=\alpha F_1+F_0\\ &=\alpha\cdot1+0\\ &=\alpha \end{align} $$ Suppose it's true for $n$, then because $\alpha^2=\alpha+1$, $$ \begin{align} \alpha^{n+1} &=\alpha\cdot\alpha^n\\ &=\alpha(\alpha F_n+F_{n-1})\\ &=\alpha^2F_n+\alpha F_{n-1}\\ &=(\alpha+1)F_n+\alpha F_{n-1}\\ &=\alpha(F_n+F_{n-1})+F_n\\ &=\alpha F_{n+1}+F_n \end{align} $$ Thus, it is true for $n+1$. By induction, the identity is true for all $n\ge1$.

share|improve this answer
    
the realization that $\alpha^2=\alpha+1$ did it. This was even introduced in one of the assignments before this one, should have known this :'). Thanks a lot! –  Bas Jun 15 '13 at 14:34

Using Euler-Binet Formula,

$$F_{n+1}=\frac{\alpha^{n+1}-\beta^{n+1}}{\alpha-\beta}$$

$$=\frac{\alpha^n(\alpha-\beta)+\beta\cdot \alpha^n-\beta^{n+1}}{\alpha-\beta}$$

$$=\alpha^n+\beta\cdot \frac{\alpha^n-\beta^n}{\alpha-\beta}$$

$$=\alpha^n+\beta\cdot F_n =\alpha^n-\frac{F_n}\alpha\text{ as }\alpha\cdot \beta=-1$$

$$\implies \alpha\cdot F_{n+1}+F_n=\alpha^{n+1} $$

share|improve this answer
    
@ThomasAndrews, was just going to complete this –  lab bhattacharjee Jun 15 '13 at 14:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.