Послідовність Фібоначчі

The Fibonacci Sequence is a special type of sequence over the positive integers, where the $n$th Fibonacci number is usually denoted $F_n$.

The definition of the Fibonacci sequence is $F_1=F_2=1$ and $$F_{n+2}=F_{n+1}+F_n.$$ This generates the positive integer sequence $$1, 1, 2, 3, 5, 8, 13, 21, \ldots$$ (Note: we can also define $F_0=0$.)

Perhaps the most characteristic image depicting the Fibonacci sequence is the Golden Spiral:

We see that this is constructed by first attaching two squares of side length $F_1=F_2=1$ together. Then, we attach a square with side length $F_3=2$ on our resulting rectangle, then attach a square of side length $F_4=3$, and so on. The biggest rectangle that circumscribes the spiral is called the Golden Rectangle.

But why is this rectangle "golden"?

It turns out that these figures are closely related to the Golden Ratio $\varphi = \dfrac{1+\sqrt{5}}{2}$ (and thus so is the Fibonacci sequence). We can see this relation by solving for the dimensions of the Golden Rectangle:

Here we can see that only the largest two rectangles have been drawn in. Since both these rectangles are similar, it follows that $$\dfrac{a}{b}=\dfrac{a+b}{a},$$ where the first ratio comes from the red rectangle and the second ratio comes from the entire rectangle.

Let's solve for $\dfrac{a}{b}$ now: $$\begin{align*} \dfrac{a}{b}&=\dfrac{a+b}{a}\\ a^2 &= ab+b^2\\ a^2-ab-b^2&=0\\ \left(\dfrac{a}{b}\right)^2-\dfrac{a}{b}-1&=0\\ \dfrac{a}{b}&=\dfrac{1\pm \sqrt{5}}{2} \end{align*}$$ Since $a>b$, we must have $\dfrac{a}{b}=\dfrac{1+ \sqrt{5}}{2}$, so the dimensions of the golden rectangle are in the ratio $1:\dfrac{1+\sqrt{5}}{2}$. This ratio is the link between the Golden Rectangle and the Golden Ratio $\varphi$.

In fact, this gives us information about the Fibonacci sequence itself. Note that $a$ and $b$ represent consecutive numbers in the Fibonacci sequence (due to the construction described above). Thus, we have the interesting relation $$\lim\limits_{n\to \infty}\dfrac{F_{n+1}}{F_n}=\varphi.$$

Now let's try to find a closed form representation of the Fibonacci sequence. Since it is a linear recurrence, we can use the process of solving linear recurrences to solve for $F_n$. In particular, the characteristic polynomial of the linear recurrence $F_{n+2}=F_{n+1}+F_n$ is $$r^2-r-1=0,$$ which has roots $r_1=\dfrac{1+\sqrt{5}}{2}$ and $r_2=\dfrac{1-\sqrt{5}}{2}$ (there's the Golden Ratio again!).

Thus, there are constants $\lambda_1$ and $\lambda_2$ that give $$F_n=\lambda_1 \left(\dfrac{1+\sqrt{5}}{2}\right)^n+\lambda_2 \left(\dfrac{1-\sqrt{5}}{2}\right)^n$$ Plugging in $n=0,1$ and solving the two-variable two-equation system, we obtain $\lambda_1=\dfrac{1}{\sqrt{5}}$ and $\lambda_2=-\dfrac{1}{\sqrt{5}}$, so we finally have our closed form: $$F_n=\dfrac{1}{\sqrt{5}}\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\dfrac{1}{\sqrt{5}}\left(\dfrac{1-\sqrt{5}}{2}\right)^n$$

The Fibonacci numbers, unsurprisingly, satisfy a plethora of identites, including: $$F_1+F_2+\cdots +F_n=F_{n+2}-1$$ $$F_1+F_3+\cdots +F_{2n-1}=F_{2n}$$ $$F_2+F_4+\cdots +F_{2n}=F_{2n+1}-1$$ These can be proven using the closed form of $F_n$, but some can be proven in clever ways. For example, I'll prove the second identity.

First, we note that $F_1=F_2$. Now, we just need to prove that $F_2+F_3+F_5+F_7+\cdots +F_{2n-1}=F_{2n}$ But now note that $F_2+F_3=F_4$ by the definition of the Fibonacci numbers which turns our sum into $F_4+F_5+F_7+\cdots +F_{2n-1}=F_{2n}$. Then $F_4+F_5=F_6$, then $F_6+F_7=F_8$ and so on, and the entire sum eventually collapses to $F_{2n}$.

(Video) Intro to Series and Sequences

by Eddie Woo

Here is a fantastic video by Eddie Woo where he goes over the basics of sequences and series.

In this video he goes over:

$$\\\begin{align} &\circ\text{ Sets}\\ &\circ\text{ Sequences}\\ &\circ\text{ Series}\\ &\circ\text{ Terms}\\ &\circ\text{ How to Define a Sequence or Series}\\ &\quad\cdot\text{ Show the Pattern}\\ &\quad\cdot\text{ Algebraic Expression}\\ &\quad\cdot\text{ Recursive Definition}\\ &\quad\quad-\text{ Fibonacci Sequence} \end{align}$$

Fibonacci Sequence

One of the most famous recursive sequences is the Fibonacci sequence. While it is not impossible to express this as a general algebraic expression, it is very difficult. The first two numbers of this sequence are kind of arbitrary; we just decided to start at one. To get to the next number, we add the previous two numbers. So $1+1=2$. Then, $1+2=3$. $$\{1,1,2,3,5,8,13,\cdot\cdot\cdot\}$$

To write this recursively we start with the first two terms. $$T_1=1\\ T_2=1$$ After we define these, we can state that every term after is: $$T_n=T_{n-1}+T_{n-2}$$

Prove that $F_n=\left\lfloor\dfrac{\varphi^n}{\sqrt5}\right\rfloor$ where $\lfloor x\rfloor$ is the floor of $x$.

Can you design an algorithm to find $n$ when you are given $F_n$?

Hint: Think using $\log$.

Use this exercise along with $\varphi^{m+n}=\varphi^m\varphi^n$ to prove that $F_{m+n}=F_mF_{n+1}+F_{m-1}F_n$.

Prove that $\varphi^n=\varphi F_n+F_{n-1}$ where $\varphi$ is the golden ratio.

Here's a really cool example of the Fibonacci sequence in nature!