Explicit Formula for Fibonacci Sequence

Fibonacci Sequence: 1,1,2,3,5,8,13,21,…1,1,2,3,5,8,13,21,\dots

{F0=0F1=1Fn+2=Fn+1+Fn\begin{cases}F_0=0\\F_1=1\\F_{n+2}=F_{n+1}+F_n\end{cases}

Fn+2−Fn+1−Fn=0F_{n+2}-F_{n+1}-F_n=0

Suppose Fn=rnF_n=r^n solves this equation for some r≠0r≠0.

rn+2−rn+1−rn=0rn(r2−r−1)=0r2−r−1=0r=1±52\begin{aligned} r^{n+2}-r^{n+1}-r^n&=0\\ r^n(r^2-r-1)&=0\\ r^2-r-1&=0\\ r&=\frac{1±\sqrt{5}}{2} \end{aligned}

Fn=A(1+52)n+B(1−52)nF_n=A\left(\frac{1+\sqrt{5}}{2}\right)^n+B\left(\frac{1-\sqrt{5}}{2}\right)^n solves Fn+2−Fn+1−Fn=0F_{n+2}-F_{n+1}-F_n=0.

F0=A(1+52)0+B(1−52)00=A+BB=−A\begin{aligned} F_0&=A\left(\frac{1+\sqrt{5}}{2}\right)^0+B\left(\frac{1-\sqrt{5}}{2}\right)^0\\ 0&=A+B\\ B&=-A \end{aligned}

F1=A(1+52)1+B(1−52)11=A(1+52)−A(1−52)1=A(1+52−1−52)1=A5A=15⇒B=−15\begin{aligned} F_1&=A\left(\frac{1+\sqrt{5}}{2}\right)^1+B\left(\frac{1-\sqrt{5}}{2}\right)^1\\ 1&=A\left(\frac{1+\sqrt{5}}{2}\right)-A\left(\frac{1-\sqrt{5}}{2}\right)\\ 1&=A\left(\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}\right)\\ 1&=A\sqrt{5}\\ A&=\frac{1}{\sqrt{5}}\Rightarrow B=-\frac{1}{\sqrt{5}} \end{aligned}

Fn=A(1+52)n+B(1−52)n=15(1+5)n2n−15(1−5)n2n=15[(1+5)n2n−(1+5)n2n]=15(1+5)n−(1−5)n2n\begin{aligned} F_n&=A\left(\frac{1+\sqrt{5}}{2}\right)^n+B\left(\frac{1-\sqrt{5}}{2}\right)^n\\ &=\frac{1}{\sqrt{5}}\frac{\left(1+\sqrt{5}\right)^n}{2^n}-\frac{1}{\sqrt{5}}\frac{\left(1-\sqrt{5}\right)^n}{2^n}\\ &=\frac{1}{\sqrt{5}}\left[\frac{\left(1+\sqrt{5}\right)^n}{2^n}-\frac{\left(1+\sqrt{5}\right)^n}{2^n}\right]\\ &=\frac{1}{\sqrt{5}}\frac{\left(1+\sqrt{5}\right)^n-\left(1-\sqrt{5}\right)^n}{2^n}\\ \end{aligned}

∴Fn=(1+5)n−(1−5)n2n5\therefore\boxed{F_n=\frac{\left(1+\sqrt{5}\right)^n-\left(1-\sqrt{5}\right)^n}{2^n\sqrt{5}}}

Proof by induction:

Base cases:

Fn∣n=0=(1+5)0−(1−5)0205=1−115=05=0Fn∣n=0=F0\begin{aligned} F_n\rvert_{n=0}&=\frac{\left(1+\sqrt{5}\right)^0-\left(1-\sqrt{5}\right)^0}{2^0\sqrt{5}}\\ &=\frac{1-1}{1\sqrt{5}}\\ &=\frac{0}{\sqrt{5}}\\ &=0\\ F_n\rvert_{n=0}&=F_0 \end{aligned}

Fn∣n=1=(1+5)1−(1−5)1215=1+5−1+525=2525=1Fn∣n=1=F1\begin{aligned} F_n\rvert_{n=1}&=\frac{\left(1+\sqrt{5}\right)^1-\left(1-\sqrt{5}\right)^1}{2^1\sqrt{5}}\\ &=\frac{1+\sqrt{5}-1+\sqrt{5}}{2\sqrt{5}}\\ &=\frac{2\sqrt{5}}{2\sqrt{5}}\\ &=1\\ F_n\rvert_{n=1}&=F_1 \end{aligned}

Inductive hypothesis: assume Fn=(1+5)n−(1−5)n2n5F_n=\frac{\left(1+\sqrt{5}\right)^n-\left(1-\sqrt{5}\right)^n}{2^n\sqrt{5}} is true for n=kn=k.

Fk=(1+5)k−(1−5)k2k5F_k=\frac{\left(1+\sqrt{5}\right)^k-\left(1-\sqrt{5}\right)^k}{2^k\sqrt{5}}

Fk+1=Fk+Fk−1=(1+5)k−(1−5)k2k5+(1+5)k−1−(1−5)k−12k−15=2(1+5)k−2(1−5)k+4(1+5)k−1−4(1−5)k−12k+15=2(1+5)k−1(1+5+2)−2(1−5)k−1(1−5+2)2k+15=(1+5)k−1(2+25+4)−(1−5)k−1(2−25+4)2k+15=(1+5)k−1(1+25+5)−(1−5)k−1(1−25+5)2k+15=(1+5)k−1(1+5)2−(1−5)k−1(1−5)22k+15Fk+1=(1+5)k+1−(1−5)k+12k+15■\begin{aligned} F_{k+1}&=F_k+F_{k-1}\\ &=\frac{\left(1+\sqrt{5}\right)^k-\left(1-\sqrt{5}\right)^k}{2^k\sqrt{5}}+\frac{\left(1+\sqrt{5}\right)^{k-1}-\left(1-\sqrt{5}\right)^{k-1}}{2^{k-1}\sqrt{5}}\\ &=\frac{2\left(1+\sqrt{5}\right)^k-2\left(1-\sqrt{5}\right)^k+4\left(1+\sqrt{5}\right)^{k-1}-4\left(1-\sqrt{5}\right)^{k-1}}{2^{k+1}\sqrt{5}}\\ &=\frac{2\left(1+\sqrt{5}\right)^{k-1}\left(1+\sqrt{5}+2\right)-2\left(1-\sqrt{5}\right)^{k-1}\left(1-\sqrt{5}+2\right)}{2^{k+1}\sqrt{5}}\\ &=\frac{\left(1+\sqrt{5}\right)^{k-1}\left(2+2\sqrt{5}+4\right)-\left(1-\sqrt{5}\right)^{k-1}\left(2-2\sqrt{5}+4\right)}{2^{k+1}\sqrt{5}}\\ &=\frac{\left(1+\sqrt{5}\right)^{k-1}\left(1+2\sqrt{5}+5\right)-\left(1-\sqrt{5}\right)^{k-1}\left(1-2\sqrt{5}+5\right)}{2^{k+1}\sqrt{5}}\\ &=\frac{\left(1+\sqrt{5}\right)^{k-1}\left(1+\sqrt{5}\right)^2-\left(1-\sqrt{5}\right)^{k-1}\left(1-\sqrt{5}\right)^2}{2^{k+1}\sqrt{5}}\\ F_{k+1}&=\frac{\left(1+\sqrt{5}\right)^{k+1}-\left(1-\sqrt{5}\right)^{k+1}}{2^{k+1}\sqrt{5}}\quad\blacksquare \end{aligned}

#Algebra

Note by Gandoff Tan
1 year, 7 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} ai−1 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

Wow!!!!!!!!!!!!!!!!!!! @Gandoff Tan

A Former Brilliant Member - 1 year, 1 month ago

The proof has used techniques to solve a recursion. Nice!

Mahdi Raza - 1 year, 1 month ago

What does n|n=1 mean? In Hungary we use a|b if a%b=0.

A Former Brilliant Member - 1 year ago
×

Problem Loading...

Note Loading...

Set Loading...