# Is there a formula for fibonacci sequence?

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$

• en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression – Wojowu Feb 14 '16 at 11:06
• 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 '16 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 '16 at 11:09
• Just a technicality, but this is not a series but a sequence. – Ennar Feb 14 '16 at 11:09
• @AndyRock My link contains a derivation of this formula. – Wojowu Feb 14 '16 at 11:10

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.

• Isn't $\beta$ having a negative sign in the middle? Anyway, this derivation is much clearer than the one in wikipedia. – user313384 Feb 14 '16 at 11:19
• Thanks - I've fixed it now. – Matt B Feb 14 '16 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$. – DanielWainfleet Feb 14 '16 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 '16 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.

• The fibonacci series is all integers..How can this weird expression be the equation for it? – user313384 Feb 14 '16 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 '16 at 11:16
• @Ennar Oh god!! that's right! How does that happen? Anyway, thanks for that. – user313384 Feb 14 '16 at 11:18
• I know how to find this with generating functions but not with Laplace domain. How is that done ? – user230452 Feb 14 '16 at 11:24
• @AndyRock Its fascinating how operations on irrational numbers always return natural numbers ! – user230452 Feb 14 '16 at 11:25