Mémoire PP2

Mémoire PP2 : Décimo - Le Gunehec.tex

\documentclass[a4paper,12pt]{report}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[french]{babel}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{fancyhdr}


\author{Antonin Décimo, Pablo Le Gunehec}
\date{Mardi 10 Mars 2015}
\title{Suite de Fibonacci \& Nombre d'Or}

\theoremstyle{plain}
\newtheorem{thm}{Théorème}[chapter]
\newtheorem{cor}[thm]{Corollaire}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}{Proposition}[chapter]



\theoremstyle{definition}
\newtheorem{defn}{Définition}[chapter]
\newtheorem{rmq}{Remarque}[chapter]
\newtheorem{ex}{Exemple}[chapter]



\begin{document}
\maketitle
\tableofcontents

\chapter{Suite de Fibonacci}

\begin{ex}\label{lapin}
    Le problème suivant est issu du \textit{Liber abaci} (ou \textit{Livre du calcul}) de Leonardo Fibonacci.\\
    Il s'agit de dénombrer une population de couples de lapins ayant les caractéristiques suivantes:
        \\-Ils sont immortels.
        \\-Ils sont pubères à partir de leur troisième mois inclus.
        \\-Chaque mois, chaque couple pubère donne naissance à un couple non pubère.
    \\La question est alors de savoir combien il y a de couples de lapins au n-ième mois.
\end{ex}
 
\begin{defn}
Pour cela on définit la suite de Fibonacci $(F_{n})_{n\in\mathbb{N}}$, par la récurrence suivante:
$$(F_{n})_{n\in\mathbb{N}}=\begin{cases}
F_{0}=1 \\
F_{1}=1\\
F_{n}=F_{n-1}+F_{n-2}
 \end{cases}
$$
Cette suite permet de résoudre le problème des lapins \ref{lapin}.
\end{defn}

\begin{defn}
On appelle nombres de Fibonacci les entiers atteints par la suite de Fibonacci.\\
Voici les premiers nombres de Fibonacci:\\
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
	\hline
	$F_{0}$ & $F_{1}$ & $F_{2}$ & $F_{3}$ & $F_{4}$ & $F_{5}$ & $F_{6}$ & $F_{7}$ & $F_{8}$ & $F_{9}$ & $F_{10}$ & $F_{11}$ & 
	$F_{12}$ & $F_{13}$ & $F_{14}$ & $F_{15}$ \\
	\hline
	1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 & 144 & 233 & 377 & 610 & 987 \\
	\hline
\end{tabular}
\end{defn}

\pagebreak

\begin{rmq}
    Voici Un algorithme récursif naïf pour calculer la suite de Fibonacci :
    
    \begin{verbatim}
    fonction fibo(n):
    	si (n $\leq$ 1)
    	    retourner n
        sinon
            retourner fibo(n - 1) + fibo(n - 2)
    fin
    \end{verbatim}
    
    Néanmoins cet algorithme n'est pas très efficace, on calcule de nombreuses fois les mêmes valeurs.
\end{rmq}

\begin{defn}
	La suite de Fibonacci est un cas particulier de trois formes de suites remarquables.\\
	\begin{enumerate}
	\item Les suites de Fibonacci généralisées.\\
	Elles suivent la même récurrence que la suite de Fibonacci mais leur initialisation est différente de 0 et 1.\\ 

	\item Les suites dites de Lucas, du mathématicien français Edouard Lucas, se définissent de la manière suivante:\\
	$$U_{n}=P*U_{n-1}+Q*U_{n-2}$$
	Elles peuvent être initiées de deux manières différentes\\
	$$U_{0}=0 \text{ et } U_{1}=1 \quad \text{ou} \quad U_{0}=2 \text{ et } U_{1}=P$$\\
	
	\item Les suites dites de K-bonacci définies par:
	$$U_{n+k}=\sum_{i=n}^{n+k-1} U_{n}=U_{n}+U_{n+1}+...+U_{n+k-2}+U_{n+k-1}$$
	La suite de Fibonacci est donc la suite de 2-bonacci $U_{n+2}=U_{n}+U_{n+1}$
	\end{enumerate}
\end{defn}



\chapter{Nombre d'or}
Il existe deux manières de définir le nombre d'or.
Une manière géométrique, et une manière algébrique.

\section{Géométrique}
\begin{defn}
Le nombre d'or, noté $\varphi$, est une proportion définie comme l'unique rapport $\frac{a}{b}$ entre deux longueurs $a > b$ telles que le rapport de la somme $a +  b$ des deux longueurs sur la plus grande ($a$) soit égal à celui de la plus grande ($a$) sur la plus petite ($b$). Plus clairement : 
$$\varphi = \frac{a}{b} \quad \text{lorsque} \quad \frac{a+b}{a}=\frac{a}{b}$$
\end{defn}

On appelle cette proportion "proportion d'or", ou "proportion d'extrême et de moyenne raison". Le rapport $\frac{a}{b}$ ne dépend pas des valeurs $a$ et $b$, dès lors que ces deux nombres sont en proportion d'or. $\varphi$ est donc constant, et l'on peut chercher une définition algébrique.

Cherchons une écriture avec des $\frac{a}{b}$ :
$$ \frac {a+b}a =\frac ab \Leftrightarrow 1 + \frac ba = \frac ab \Leftrightarrow \frac ab + 1 = \left(\frac ab\right)^2 \Leftrightarrow  \left(\frac ab\right)^2 - \frac ab - 1 =  0$$

\section{Algébrique}
Le nombre d'or est donc la solution positive de l'équation $x\up{2} - x - 1 = 0$.
Calculons-le :
$$x\up{2}-x-1=0,\quad\Delta=1+4=5,\quad\text{donc}\quad\varphi=\frac{1+\sqrt{5}}{2}$$

\section{Fractions continues}
Le nombre d'or peut également être approché par fraction continue. On peut l'approcher par les valeurs 1 ou 1 + 1/1.
$$\varphi = 1 + \frac{1}{1+\frac{1}{1+\frac{1}{1+\cdots}}}$$
Le fait que la fraction ne s'arrête pas montre bien que $\varphi$ est irrationnel. On peut en déduire plusieurs expressions algébriques de $\varphi$:
$$\varphi = 1 + \frac{1}{\varphi}\quad\text{ou encore}\quad\varphi^2 = \varphi + 1$$

Comment construit-on cette fraction continue ? Dans un premier temps, on dessine un rectangle formé de deux carrés côte à côte et de côté 1. Le rapport entre la longueur et la largeur de la figure est égal à 2, la meilleure approximation en nombre entier du nombre d'or. On ajoute un carré de côté égal à la longueur de la figure précédente, donc de côté 2 (ou 1+1). On obtient un rectangle, composé de trois carrés dont le rapport de la longueur sur la largeur valant $3/2 = 1 + 1/2 = 1 + 1/(1+1)$. En poursuivant, on trouve
$$\frac 53 = 1 + \frac 23 = 1 + \frac 1{\frac 32} \quad\text{or}\quad \frac 32 = 1 + \frac 1{1+1} \quad\text{donc} \quad\frac 53 = 1 + \frac 1{1 + \frac 1{1+1}}$$

\begin{figure}[!h]
\centering
\includegraphics{FibonacciBlocks.png}
\end{figure}

L'approximation se précise, elle vaut 1,66$\cdots$, celle du nombre d'or est 1,62$\cdots$. Si le processus est réitéré à l'infini, on obtient une expression du nombre d'or en fraction continue :
$$\varphi = 1+ \frac 1{1 + \frac 1{1 + \frac 1 {1 + \frac 1{1 + \cdots}}}}$$

Le retrait d'un carré de dimension maximale laisse une surface rectangulaire de même proportion que le rectangle initial; on obtient un rectangle d'or.


\chapter{Relations}
\section{Forme close}
\begin{thm}
    Forme close (sans récurrence) de la suite de Fibonacci.
    $$\forall n >= 0, F_{n} = \frac{\varphi^n-\psi^n}{\varphi-\psi}
    = \frac{\varphi^n-\psi^n}{\sqrt 5}$$
\end{thm}
\begin{proof}
    Rappelons que $\varphi^n = \varphi^{n-1} + \varphi^{n-2}$. Il en va de même pour $\psi$.
    Cherchons $a$ et $b$ tels que la suite $U_n = a\varphi^n+b\psi^n$ soit la suite de Fibonacci.
    On a $U_n=a \varphi^{n-1} + b \psi^{n-1} + a \varphi^{n-2} + b \psi^{n-2} = U_{n-1} + U_{n-2}$.
    Donc $U_n$ vérifie la récurrence de Fibonacci, il suffit d'avoir $U_0 = 0$ et $U_1 = 1$.
    On résoud le système :
    $$\begin{cases}
        a + b = 0 \\
        a \varphi + b \psi = 1
    \end{cases}
    \Leftrightarrow
    \begin{cases}
        b = -a \\
        a (\varphi - \psi) = 1
    \end{cases}
    \Leftrightarrow
    \begin{cases}
        a = \frac{1}{\varphi - \psi} = \frac{1}{\sqrt 5} \\
        b = -a = - \frac{1}{\sqrt 5}
    \end{cases}
    $$
    On a donc :
    $$F_n = U_n = a \varphi^n + b \psi^n = \frac{\varphi^n - \psi^n}{\sqrt 5}$$
\end{proof}

\section{Limite}
    En reprenant les conclusions de la construction par fractions continues, on arrive à une observation intéressante : les longueurs des côtés successifs sont en fait les nombres de Fibonacci. Si l'on considère un rectangle d'or, alors on a l'approximation $\frac{\text{longueur}}{\text{largeur}} = \varphi$, d'où :
\begin{thm}
    $$\lim \frac{F_{n+1}}{F_n} = \varphi$$
\end{thm}


\end{document}