Math + You = 1

# Corrected exercise: Fibonacci sequence and golden number

Here is the statement of an exercise on the Fibonacci sequence, it is a follow-up exercise relating to the golden ratio. It is feasible in MPSI, MPII, PCSI and PTSI and generally in the first year in higher education.

## Question 1

Let's first calculate the value of the first two terms:

\begin{array}{l} u_0 = \displaystyle \sum_{p=0}^0 \binom{p}{0-p} = \binom{0}{0} = 1\\ u_1 = \displaystyle \sum_ {p=0}^1 \binom{p}{1-p} = \binom{0}{1} +\binom{1}{0}=1\\ \end{array}

Which are the expected results.

Now let's show the second part of the question:

\begin{array}{l} u_{n+2} = \displaystyle \sum_{p=0}^{n+2} \binom{p}{n+2-p} \\ u_{n+2} = \displaystyle \sum_{p=0}^{n+2} \binom{p-1}{n+2-p-1} + \binom{p-1}{n+2-p} \\ \ end{array}

We used the Pascal's formula
Let's continue the calculation:

\begin{array}{l} u_{n+2} = \displaystyle \sum_{p=0}^{n+2} \binom{p-1}{n+2-p-1} + \sum_{ p=0}^{n+2} \binom{p-1}{n+2-p} \\ u_{n+2}=\displaystyle \sum_{p=0}^{n+2} \binom {p-1}{n+1-p} + \sum_{p=0}^{n+2} \binom{p-1}{n+2-p} \\ \text{The term p = 0 is null}\\ u_{n+2} = \displaystyle \sum_{p=1}^{n+2} \binom{p-1}{n+1-p}+\sum_{p=1}^ {n+2} \binom{p-1}{n+2-p} \\ \text{We make a change of index}\\ u_{n+2} = \displaystyle \sum_{p=0} ^{n+1} \binom{p}{n+1-(p+1)} + \sum_{p=0}^{n+1} \binom{p}{n+2-(p+1 )} \\ u_{n+2} = \displaystyle \sum_{p=0}^{n+1} \binom{p}{np} + \sum_{p=0}^{n+1} \binom {p}{n+1-p} \\ \text{The term n+1 is zero in the first sum}\\ u_{n+2} = \displaystyle \sum_{p=0}^{n} \ binom{p}{np} + \sum_{p=0}^{n+1} \binom{p}{n+1-p} \\ u_{n+2} = u_n+u_{n+1} \end{array}

Which is the expected result.

## Question 2: Classic expression of the Fibonacci sequence

We have a recurrent sequence of order 2 of which we know the first two terms. It is therefore well defined.
Let’s calculate its characteristic polynomial, which is therefore a quadratic equation:

r^2 = r+1 \Leftrightarrow r^2 -r-1 = 0

We calculate the discriminant.

\Delta = 1^2 + 4 \times 1 \times1 =5

Which gives us the following two roots

\begin{array}{l} r_1 = \dfrac{1+\sqrt{5}}{2}\\ r_2 = \dfrac{1-\sqrt{5}}{2} \end{array}

We then use the initial conditions:

\begin{array}{l} r_1 = \dfrac{1+\sqrt{5}}{2}\\ r_2 = \dfrac{1-\sqrt{5}}{2} \end{array}

According to the theory of recurrent sequences of order 2, the solution is of the form:

u_n = a r_1^n +br_2^n

We will therefore find a and b thanks to u0 and you1 :

\begin{array}{l} u_0 = ar_1^0 +br_2^0 = a+b = 1 \\ u_1= ar_1^1 +br_2^1 = ar_1+br_2 = 1 \\ \end{array}

Substitute a in the second equation to find b:

\begin{array}{l} (1-b) r_1 +br_2 = 1 \\ \Leftrightarrow r_1-1 = b(r_1-r_2) \\ \Leftrightarrow b = \dfrac{r_1-1}{r_1-r_2} \\ \Leftrightarrow b = \dfrac{\sqrt{5}-1}{2\sqrt{5}} \end{array}

And we substitute in the first equation to find a:

a = 1 -b = 1 - \dfrac{\sqrt{5}-1}{2\sqrt{5}} = \dfrac{\sqrt{5}+1}{2\sqrt{5}}

The solution is therefore:

\begin{array}{l} u_n = \dfrac{\sqrt{5}+1}{2\sqrt{5}} r_1^n + \dfrac{\sqrt{5}-1}{2\sqrt{5 }} r_2 ^n\\ u_n = \dfrac{1}{\sqrt{5}} \left(\left( \dfrac{\sqrt{5}+1}{2}\right)^{n+1} -\left(\dfrac{1-\sqrt{5}}{2}\right)^{n+1}\right) \end{array}

Which is an expression of the Fibonacci sequence as a function of n better known than the first.

## Question 3: ratio of the Fibonacci sequence

Let's do the math straight away

\begin{array}{ll} \dfrac{u_{n+1}}{u_n}& = \dfrac{ \frac{1}{\sqrt{5}} \left(\left( \frac{\sqrt{ 5}+1}{2}\right)^{n+2} -\left(\frac{1-\sqrt{5}}{2}\right)^{n+2}\right)}{ \ frac{1}{\sqrt{5}} \left(\left( \frac{\sqrt{5}+1}{2}\right)^{n+1} -\left(\frac{1-\ sqrt{5}}{2}\right)^{n+1}\right)}\\ &= \dfrac{ \left( \sqrt{5}+1\right)^{n+2} -\left (1-\sqrt{5}\right)^{n+2}}{2\left(\left( \sqrt{5}+1\right)^{n+1} -\left(1-\sqrt {5}\right)^{n+1}\right)}\\ &\sim \dfrac{ \left( \sqrt{5}+1\right)^{n+2} }{2\left( \ sqrt{5}+1\right)^{n+1}} = \dfrac{1+\sqrt{5}}{2} \end{array}

So we have:

\lim_{n \to +\infty} \dfrac{u_{n+1}}{u_n} = \dfrac{1+\sqrt{5}}{2}

Which answers the question quite well. A good approximation of the golden ratio is φ ≃ 1,618 033 988 749 894 848 204 586 834 365 638 117 720 309 179 805 762 862 135 448 622 705 260 462 818 902 449 707 207 204.

## Question 4

We have :

u_n = \dfrac{1}{\sqrt{5}} \left(\left( \dfrac{\sqrt{5}+1}{2}\right)^{n+1} -\left(\dfrac{ 1-\sqrt{5}}{2}\right)^{n+1}\right)

Which can be written using the golden ratio by:

u_n = \dfrac{1}{\sqrt{5}} \left( \varphi^{n+1} -\left(-\dfrac{1}{\varphi}\right)^{n+1}\right )

We therefore have the equivalent:

u_n \sim \dfrac{\varphi^{n+1}}{\sqrt{5}}

## Bonus: Other formulas with the golden ratio

Here are other formulas for writing the golden ratio. Here is one with fractions

\varphi = 1+ \dfrac{1}{1 + \dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{1+\ldots}}}}}

And here's one with roots

\varphi = \sqrt{1+\sqrt{1+\sqrt{1+\sqrt{1+\sqrt{1+\ldots}}}}}