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}}}}}