×

The Explicit Formula for Fibonacci Sequence

First, let's write out the recursive formula: $a_{n+2}=a_{n+1}+a_n$ where $$a_{ 1 }=1,\quad a_2=1$$

Now, the expression will be modified in 2 different, but similar, ways.

First modification: $a_{n+2}-\alpha a_{n+1}=\beta (a_{n+1}-\alpha a_ n)$ Define a new sequence like this: $b_n=a_{ n+1 }-\alpha a_{ n }$ Then, the modified version of the Fibonacci Sequence looks like this: $b_{n+1}=\beta b_n$ As you can see, it's telling us that the sequence $$b_n$$ is a geometric progression, so we can write the explicit form of $$b_n$$ like this: $b_{ n }=b_{ 1 }\beta ^{n-1}=(a_{1+1}-\alpha a_1)\beta^{n-1}=(a_{2}-\alpha a_1)\beta^{n-1}=(1-\alpha )\beta^{n-1}$

Second modification: $a_{n+2}-\beta a_{n+1}=\alpha (a_{n+1}-\beta a_ n)$ Define a new sequence like this: $c_n=a_{ n+1 }-\beta a_{ n }$ Then, the modified version of the Fibonacci Sequence looks like this: $c_{n+1}=\alpha c_n$ As you can see, it's telling us that the sequence $$c_n$$ is a geometric progression, so we can write the explicit form of $$c_n$$ like this: $c_{ n }=c_{ 1 }\alpha ^{n-1}=(a_{1+1}-\beta a_1)\alpha^{n-1}=(a_{2}-\beta a_1)\alpha^{n-1}=(1-\beta )\alpha^{n-1}$

Now, recall that the original version of the Fibonacci Sequence was $$a_{n+2}=a_{n+1}+a_n$$. Rewrite it as $1a_{n+2}-1a_{n+1}-1a_n=0$

Our first modified version of the Fibonacci Sequence was $$a_{n+2}-\alpha a_{n+1}=\beta (a_{n+1}-\alpha a_ n)$$, and our second modified version of the Fibonacci Sequence was $$a_{n+2}-\beta a_{n+1}=\alpha (a_{n+1}-\beta a_ n)$$

Both of them can be rewritten as $1a_{ n+2 }-(\alpha +\beta )a_{n+1}+\alpha \beta a_n=0$

The above 2 equations have to be the same, so we can say that $\alpha \beta =-1,\quad \alpha +\beta =1\Longrightarrow \alpha =1-\beta \quad and\quad \beta =1-\alpha$

Substituting it into the 2 modifications yields...

First Modification: $b_n=(1-\alpha )\beta^{n-1}=\beta \times \beta ^{n-1}=\beta^n$ Recalling our definition of $$b_n$$, $a_{n+1}-\alpha a_n=\beta ^n$

Second Modification: $c_n=(1-\beta )\alpha^{n-1}=\alpha \times \alpha ^{n-1}=\alpha^n$ Recalling our definition of $$c_n$$, $a_{n+1}-\beta a_n=\alpha ^n$

(We're almost done) Subtracting those 2 equations gives us $\{ a_{ n+1 }-\alpha a_{ n }\} -\{ a_{ n+1 }-\beta a_{ n }\} =\beta ^{ n }-\alpha ^{ n }\longrightarrow (\beta -\alpha )a_{ n }=\beta ^{ n }-\alpha ^{ n }\\ \therefore a_{ n }=\frac { \beta ^{ n }-\alpha ^{ n } }{ \beta -\alpha }$ which is the explicit form of the Fibonacci Sequence.

If we can find the values of $$\alpha$$ and $$\beta$$, then we'll be done. With a bit of thinking, this is quite easy.

Remember that $$\alpha \beta =-1,\quad \alpha +\beta =1$$ This is telling us that $$\alpha$$ and $$\beta$$ are the roots of $$x^2-x-1=0$$ since the sum is 1 and the product is -1. Solving it yields $\alpha =\frac { 1-\sqrt { 5 } }{ 2 } ,\quad \beta =\frac { 1+\sqrt { 5 } }{ 2 }$

Finally, substitute the values of $$\alpha$$ and $$\beta$$ into the explicit formula.

$a_{ n }=\frac { \beta ^{ n }-\alpha ^{ n } }{ \beta -\alpha } =\frac { \left( \frac { 1+\sqrt { 5 } }{ 2 } \right) ^{ n }-\left( \frac { 1-\sqrt { 5 } }{ 2 } \right) ^{ n } }{ \frac { 1+\sqrt { 5 } }{ 2 } -\frac { 1-\sqrt { 5 } }{ 2 } } =\frac { \left( \frac { 1+\sqrt { 5 } }{ 2 } \right) ^{ n }-\left( \frac { 1-\sqrt { 5 } }{ 2 } \right) ^{ n } }{ \sqrt { 5 } }$

Note by Nick Lee
2 years, 4 months ago

Sort by:

한국분이세요? 피보나치 수열은 극한값으로구하고 특성방정식으로 끼워넣으시는게 제일편해요! · 2 years, 3 months ago

한번 보여주실 수 있으세요? 아직 수열은 배우고 있는 중이라서... · 2 years, 3 months ago

고등학교 과정은 아니지만 특성방정식이라는게 있어요. 그게 이제 극한의 개념을 약간 이용한건데 수열 배우시면 극한도 혹시 배우셨나요? 그럼 이야기가 좀 편해져서요~^^ · 2 years, 3 months ago

네. · 2 years, 3 months ago

http://j1w2k3.tistory.com/330 참조하세요. 점화식을 특성방정식으로 생각해서 하는 방법입니다. 이 방법은 이제 피보나치 수열의 consecutive 두항의 비율이 그 방정식의 해가 되죠(황금비). · 2 years, 3 months ago

Gracias, mi amigo. 제가 했던 방법과 거의 유사하지만 더 간결하게 정리해놓았네요. · 2 years, 3 months ago

근데요, 여기잇는 중딩들을 어케 대학교 과정을 알아요? 실력이대단한가보죠? · 2 years, 3 months ago

그게 아니라 이건 그냥 제가 수학에 관심이 많아서 알게 된거에요. · 2 years, 3 months ago

@Calvin Lin I learned this method from my math teacher, but is there a much easier way to derive the explicit formula for the Fibonacci Sequence? · 2 years, 3 months ago