The Explicit Formula for Fibonacci Sequence

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

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


First modification: an+2αan+1=β(an+1αan)a_{n+2}-\alpha a_{n+1}=\beta (a_{n+1}-\alpha a_ n) Define a new sequence like this: bn=an+1αanb_n=a_{ n+1 }-\alpha a_{ n } Then, the modified version of the Fibonacci Sequence looks like this: bn+1=βbnb_{n+1}=\beta b_n As you can see, it's telling us that the sequence bnb_n is a geometric progression, so we can write the explicit form of bnb_n like this: bn=b1βn1=(a1+1αa1)βn1=(a2αa1)βn1=(1α)βn1b_{ 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: an+2βan+1=α(an+1βan)a_{n+2}-\beta a_{n+1}=\alpha (a_{n+1}-\beta a_ n) Define a new sequence like this: cn=an+1βanc_n=a_{ n+1 }-\beta a_{ n } Then, the modified version of the Fibonacci Sequence looks like this: cn+1=αcnc_{n+1}=\alpha c_n As you can see, it's telling us that the sequence cnc_n is a geometric progression, so we can write the explicit form of cnc_n like this: cn=c1αn1=(a1+1βa1)αn1=(a2βa1)αn1=(1β)αn1c_{ 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 an+2=an+1+ana_{n+2}=a_{n+1}+a_n. Rewrite it as 1an+21an+11an=01a_{n+2}-1a_{n+1}-1a_n=0

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

Both of them can be rewritten as 1an+2(α+β)an+1+αβan=01a_{ 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 αβ=1,α+β=1α=1βandβ=1α\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: bn=(1α)βn1=β×βn1=βnb_n=(1-\alpha )\beta^{n-1}=\beta \times \beta ^{n-1}=\beta^n Recalling our definition of bnb_n, an+1αan=βna_{n+1}-\alpha a_n=\beta ^n

Second Modification: cn=(1β)αn1=α×αn1=αnc_n=(1-\beta )\alpha^{n-1}=\alpha \times \alpha ^{n-1}=\alpha^n Recalling our definition of cnc_n, an+1βan=αna_{n+1}-\beta a_n=\alpha ^n


(We're almost done) Subtracting those 2 equations gives us {an+1αan}{an+1βan}=βnαn(βα)an=βnαnan=βnαnβα\{ 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 αβ=1,α+β=1\alpha \beta =-1,\quad \alpha +\beta =1 This is telling us that α\alpha and β\beta are the roots of x2x1=0x^2-x-1=0 since the sum is 1 and the product is -1. Solving it yields α=152,β=1+52\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.

an=βnαnβα=(1+52)n(152)n1+52152=(1+52)n(152)n5a_{ 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
4 years, 11 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

@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?

Nick Lee - 4 years, 10 months ago

Log in to reply

See Linear Recurrence Relations, which was from a note written up by @Daniel Chiu

Calvin Lin Staff - 4 years, 10 months ago

Log in to reply

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

찬홍 민 - 4 years, 9 months ago

Log in to reply

한번 보여주실 수 있으세요? 아직 수열은 배우고 있는 중이라서...

Nick Lee - 4 years, 9 months ago

Log in to reply

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

찬홍 민 - 4 years, 9 months ago

Log in to reply

@찬홍 민 네.

Nick Lee - 4 years, 9 months ago

Log in to reply

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

찬홍 민 - 4 years, 9 months ago

Log in to reply

@찬홍 민 Gracias, mi amigo. 제가 했던 방법과 거의 유사하지만 더 간결하게 정리해놓았네요.

Nick Lee - 4 years, 9 months ago

Log in to reply

@Nick Lee 근데요, 여기잇는 중딩들을 어케 대학교 과정을 알아요? 실력이대단한가보죠?

찬홍 민 - 4 years, 9 months ago

Log in to reply

@찬홍 민 그게 아니라 이건 그냥 제가 수학에 관심이 많아서 알게 된거에요.

Nick Lee - 4 years, 9 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...