3
$\begingroup$

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$

$\endgroup$
  • 5
    $\begingroup$ en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression $\endgroup$ – Wojowu Feb 14 '16 at 11:06
  • 5
    $\begingroup$ Just to point it out, googling "fibonacci number formula" gives, in the first result, a page on which this formula is given. $\endgroup$ – Wojowu Feb 14 '16 at 11:08
  • $\begingroup$ @Wojowu I saw that formula... I just wanted to know its derivation or a simpler formula if it exists. $\endgroup$ – user313384 Feb 14 '16 at 11:09
  • $\begingroup$ Just a technicality, but this is not a series but a sequence. $\endgroup$ – Ennar Feb 14 '16 at 11:09
  • 3
    $\begingroup$ @AndyRock My link contains a derivation of this formula. $\endgroup$ – Wojowu Feb 14 '16 at 11:10
3
$\begingroup$

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.

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy