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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there a formula for fibonacci sequence? If yes, how to derive it. I was told in class yesterday about this series, and I want to know if we can generalize it to any n.

If you don't know what the series is, It is a function such that $f(n)=f(n-1)+f(n-2)$ and $f(1)=1$ , $f(2)=1$

share|cite|improve this question
5  
5  
Just to point it out, googling "fibonacci number formula" gives, in the first result, a page on which this formula is given. – Wojowu Feb 14 at 11:08
    
@Wojowu I saw that formula... I just wanted to know its derivation or a simpler formula if it exists. – user313384 Feb 14 at 11:09
    
Just a technicality, but this is not a series but a sequence. – Ennar Feb 14 at 11:09
3  
@AndyRock My link contains a derivation of this formula. – Wojowu Feb 14 at 11:10
up vote 2 down vote accepted

For the derivation, notice that this is defined as $f(n)=f(n-1)+f(n-2)$ so we form the auxiliary quadratic equation $k^2=k+1$. Solving this we find roots $\alpha= \frac{1}{2}(1+\sqrt{5})$ and $\beta=\frac{1}{2}(1-\sqrt{5})$.

This means our solution will have the form $f(n)=A\alpha^n + B\beta^n$ for some constants $A,B$ which are determined using the initial conditions $f(1)=f(2)=1$. This gives the closed form expression above.

share|cite|improve this answer
    
Isn't $\beta$ having a negative sign in the middle? Anyway, this derivation is much clearer than the one in wikipedia. – user313384 Feb 14 at 11:19
    
Thanks - I've fixed it now. – Matt B Feb 14 at 11:22
    
Let $M$ be the $2x2$ matrix whose top row is $(1,1)$ and lower row $ (0,1).$ For positive $n,$ the top row of $ M^n$ is $(F_{n+1}, F_n)$ and lower row $(F_n,F_{n-1})$. Proof by induction on $n$. – user254665 Feb 14 at 11:30
    
Sorry, but this does not seem an effective explanation. It is impossible to follow, unless one already knows the method. Why does the solution have to have the form $A\alpha^n+B\beta^n$? Why that polynomial? – Federico Poloni Feb 14 at 15:37

Yes there is

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

You can prove this by induction or by converting to laplace domain.

share|cite|improve this answer
1  
The fibonacci series is all integers..How can this weird expression be the equation for it? – user313384 Feb 14 at 11:08
    
@AndyRock, use binomial formula on $(\frac{1+\sqrt 5}2)^n$ and $(\frac{1-\sqrt 5}2)^n$ separately. All irrational parts will cancel each other. – Ennar Feb 14 at 11:16
    
@Ennar Oh god!! that's right! How does that happen? Anyway, thanks for that. – user313384 Feb 14 at 11:18
    
I know how to find this with generating functions but not with Laplace domain. How is that done ? – user230452 Feb 14 at 11:24
    
@AndyRock Its fascinating how operations on irrational numbers always return natural numbers ! – user230452 Feb 14 at 11:25

Your Answer

 
discard

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