4

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$

  • 5
    https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression – Wojowu Feb 14 '16 at 11:06
  • 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 '16 at 11:08
  • @Wojowu I saw that formula... I just wanted to know its derivation or a simpler formula if it exists. –  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
  • 3
    @AndyRock My link contains a derivation of this formula. – Wojowu Feb 14 '16 at 11:10
  • @Wojowu , Is that the derivation? Well, sorry, It was quite above my level. Thank you anyway for pointing it out. –  Feb 14 '16 at 11:12

2 Answers2

3

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.

Matt B
  • 3,915
  • Isn't $\beta$ having a negative sign in the middle? Anyway, this derivation is much clearer than the one in wikipedia. –  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
  • Do we derive this formula with the tool from recurrence relations please? I found recurrence relations taught at discrete mathematics. – Avv Jan 05 '22 at 20:02
2

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.

Win Vineeth
  • 3,504
  • 1
    The fibonacci series is all integers..How can this weird expression be the equation for it? –  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. –  Feb 14 '16 at 11:18
  • I know how to find this with generating functions but not with Laplace domain. How is that done ? – Saikat Feb 14 '16 at 11:24
  • @AndyRock Its fascinating how operations on irrational numbers always return natural numbers ! – Saikat Feb 14 '16 at 11:25
  • 1
    Observe that $S={s_1,s_2}={(1\pm \sqrt 5)/2}$ is the set of solutions of $x^2=x+1.$ So if $ y\in S$ then$ y^{n+1}=y^n+y^{n-1}.$ We can find $A,B$ with$ 0=A s_1^0+B s_2^0=A+B,$ and $1=A s_1+Bs_2.$ Then $ F_n=A s_1^n +B s_2^n$ for all $ n.$ – DanielWainfleet Feb 14 '16 at 11:25