{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
"\n",
"*(C) Copyright Franck CHEVRIER 2019-2021 http://www.python-lycee.com/*\n",
"\n",
" Pour exécuter une saisie Python, sélectionner la cellule et valider avec SHIFT+Entrée.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# La suite de Fibonacci (Corrigé)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Sommaire\n",
"\n",
"1. Définition par récurrence de la suite de Fibonacci.
\n",
"2. Formule de Binet : calculs directs des termes de la suite.
\n",
"3. Complément sur la suite de Fibonacci : Quotients de termes successifs. (Tale Spé Math)
\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 1. Définition par récurrence de la suite de Fibonacci."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"On considère l'évolution d'une population (fictive) de lapins, régie par les règles suivantes :\n",
"\n",
" - Initialement, il y a un couple de jeunes lapins ;
\n",
" - Un nouveau couple de lapins doit attendre 1 mois avant d'être adulte et de pouvoir se reproduire ;
\n",
" - Chaque mois, chaque couple de lapins adulte donne naissance à un nouveau couple de jeunes lapins ;
\n",
" - Les couples de lapins ne meurent jamais.
\n",
"
\n",
"
\n",
"Activer la cellule ci-dessous pour obtenir une illustration dynamique des premiers mois d'observation.
\n",
"Pour faire apparaître et activer l'animation, sélectionner la cellule ci-dessous et valider avec SHIFT+Entrée.
\n",
"Vous pouvez ensuite utiliser les menus cinématiques :\n",
"\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\t\n",
"\t\t\n",
"\t\t\n",
"\t\t\n",
"\t\t\n",
"\t\n",
"\t\n",
"\t\t\n",
"\t\t\t\t\t\t\n",
"\t\t\t\n",
"\t\t\t\t
\n",
"\t\t\t\t\t\t\t\t\n",
"\t\t\t\t\t\t\t\t\n",
"\t\t\t\t\n",
"\t\t\t
\n",
"On note $F_n$ le nombre de couples de lapins à l'étape $n$, où $n \\in \\mathbb{N}$ est le rang du mois de l'observation (en considérant que $n=0$ correspond à l'étape initiale).\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__1.1. Soit $n \\in \\mathbb{N}$. Exprimer $F_{n+2}$ en fonction de $F_{n+1}$ et $F_n$.__\n",
"
\n",
"$F_{n+2}=F_{n+1}+F_{n}$ où $F_{n+1}$ correspond aux couples déjà présents le mois précédent (ils ne meurent pas) et où $F_n$ correspond au nombre de naissance de nouveaux couples de lapin, égal au nombre de couples de lapins adultes le mois précédent, c'est à dire au nombre total de lapins il y a deux mois."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__1.2. Exécuter les cellules Python suivantes. Pour chacune, expliquer ce que permet d'obtenir la syntaxe proposée.__\n",
"
\n",
"\n",
"Les cellules permettent :\n",
"\n",
" - de créer une liste de 5 termes ;
\n",
" - d'accéder au dernier terme de la liste ;
\n",
" - d'accéder à l'avant dernier terme de la liste ;
\n",
" - d'ajouter à la liste une nouvelle valeur, somme de la dernière et de l'avant dernière valeur ;
\n",
"
\n",
""
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1, 1, 2, 3, 5]"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Fibo = [1,1,2,3,5]\n",
"Fibo "
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Fibo[-1]"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Fibo[-2]"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1, 1, 2, 3, 5, 8]"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a = Fibo[-1]+Fibo[-2]\n",
"Fibo.append(a)\n",
"\n",
"Fibo"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__1.3. Écrire une fonction Python Fibonacci qui reçoit N non nul en argument et qui renvoie la liste des termes $F_n$ pour $0 \\leq n \\leq N$.__\n",
"
\n",
"$\\quad\\;$Aide : On pourra initialiser une suite [1,1] que l'on complètera ensuite progressivement à l'aide d'une boucle."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"# Écrire ici la fonction Fibonacci\n",
"\n",
"def Fibonacci(N):\n",
" \"fonction qui renvoie la liste des premiers termes de la suite de Fibonacci\"\n",
" L = [1,1]\n",
" for k in range(N-2):\n",
" L.append(L[-1]+L[-2])\n",
" return L\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__1.4. À l'aide la fonction Fibonacci, obtenir la liste des 30 premiers termes de la suite de Fibonacci $(F_n)_{n \\geq 0}$.__"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1,\n",
" 1,\n",
" 2,\n",
" 3,\n",
" 5,\n",
" 8,\n",
" 13,\n",
" 21,\n",
" 34,\n",
" 55,\n",
" 89,\n",
" 144,\n",
" 233,\n",
" 377,\n",
" 610,\n",
" 987,\n",
" 1597,\n",
" 2584,\n",
" 4181,\n",
" 6765,\n",
" 10946,\n",
" 17711,\n",
" 28657,\n",
" 46368,\n",
" 75025,\n",
" 121393,\n",
" 196418,\n",
" 317811,\n",
" 514229,\n",
" 832040]"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Écrire ici un appel à la fonction Fibonacci\n",
"Fibonacci(30)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2. Formule de Binet : calculs directs des termes de la suite."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
" Notations :\n",
" \n",
" - $\\displaystyle \\phi$ est une lettre grecque qui se lit \"phi\" ;
\n",
" - $\\displaystyle \\psi$ est une lettre grecque qui se lit \"psi\".
\n",
"
\n",
" Remarque :
\n",
" Le nombre $\\phi$ ainsi défini s'appelle le nombre d'or.\n",
"
\n",
"\n",
"\n",
"\n",
"On pose $\\displaystyle \\phi=\\frac{1+\\sqrt{5}}{2}$ et $\\displaystyle \\psi=\\frac{1-\\sqrt{5}}{2}$, et on considère :\n",
"\n",
" - la suite $(u_n)_{n \\geq 0}$ géométrique de premier terme $u_0=\\phi$ et de raison $\\displaystyle \\phi$.
\n",
" - la suite $(v_n)_{n \\geq 0}$ géométrique de premier terme $v_0=\\psi$ et de raison $\\displaystyle \\psi$.
\n",
"
\n",
"
"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__2.0 Valider la cellule suivante.__
\n",
"$\\;\\;\\;$__Les fonctionnalités importées de sympy permettront d'effectuer des calculs avec racines carrées en valeurs exactes.__"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\displaystyle \\sqrt{5}$"
],
"text/plain": [
"sqrt(5)"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from sympy import sqrt,simplify\n",
"\n",
"sqrt(5) # syntaxe pour la racine carrée de 5"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__2.1. Créer des variables Python phi et psi correspondant respectivement à $\\phi$ et $\\psi$.
\n",
"$\\quad\\;\\;$Écrire ensuite des fonctions Python u et v d'argument n permettant le calcul de $u_n$ et $v_n$.__"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\displaystyle \\frac{1}{2} + \\frac{\\sqrt{5}}{2}$"
],
"text/plain": [
"1/2 + sqrt(5)/2"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"#Utiliser ces zones de saisies pour créer phi et psi, puis pour définir u et v\n",
"phi = (1+sqrt(5))/2\n",
"phi "
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\displaystyle \\frac{1}{2} - \\frac{\\sqrt{5}}{2}$"
],
"text/plain": [
"1/2 - sqrt(5)/2"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"psi = (1-sqrt(5))/2\n",
"psi"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"def u(n):\n",
" return phi**(n+1)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [],
"source": [
"def v(n):\n",
" return psi**(n+1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__2.2. Exécuter les cellules suivantes. Qu'observe-t-on ?__\n",
"
\n",
"On observe que $\\displaystyle \\frac{u_3-v_3}{\\sqrt{5}}=3=F_3$ et $\\displaystyle \\frac{u_4-v_4}{\\sqrt{5}}=5=F_4$ ."
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\displaystyle 3$"
],
"text/plain": [
"3"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"simplify( (u(3)-v(3))/sqrt(5) )"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\displaystyle 5$"
],
"text/plain": [
"5"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"simplify( (u(4)-v(4))/sqrt(5) )"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"La formule de Binet affirme que pour tout $n \\in \\mathbb{N}$ ; $\\displaystyle F_{n} = \\frac{u_{n}-v_{n}}{\\sqrt{5}} $. \n",
"
\n",
"\n",
"2.3. Question différenciée suivant le niveau :\n",
"\n",
"\n",
"\n",
" Version 1ère Spé Math
\n",
" À l'aide de saisies Python, calculer $\\displaystyle \\frac{u_{n}-v_{n}}{\\sqrt{5}}$ pour tous les entiers $n$ de 0 jusqu'à 29.\n",
"
(on appliquera la fonction simplify)\n",
"
Comparer les résultats avec ceux de la question 1.4.\n",
"
Pour la suite, on admettra que la formule de Binet est vraie pour tout $n \\in \\mathbb{N}$.\n",
"
\n",
"\n",
" Version Tale Spé Math
\n",
" a. Démontrer que $\\phi$ et $\\psi$ sont les racines du polynôme $x²-x-1$.
\n",
" $\\quad$ ($\\phi$ et $\\psi$ vérifient donc $1+\\phi=\\phi^2$ et $1+\\psi=\\psi^2$).
\n",
" b. À l'aide d'un raisonnement par récurrence, démontrer que la formule de Binet est vraie pour tout $n \\in \\mathbb{N}$.\n",
"
\n",
" \n",
"
\n",
"\n",
"
\n",
"Corrigé :\n",
"\n",
" Version 1ère Spé Math
\n",
" Voir la saisie Python ci-dessous. On retrouve les mêmes valeurs que dans la question 1.4.\n",
"
\n",
"\n",
" Version Tale Spé Math
\n",
" a. $x²-x-1$ a pour discriminant $\\Delta = 5 > 0$ donc ce polynôme a deux racines distinctes $\\displaystyle \\phi=\\frac{1+\\sqrt{5}}{2}$ et $\\displaystyle \\psi=\\frac{1-\\sqrt{5}}{2}$.
\n",
" b. On note $P(n)$ la propriété : \" Pour $0 \\leq k \\leq n$ ; $\\displaystyle F_k=\\frac{u_{k}-v_{k}}{\\sqrt{5}}$ \"
\n",
"\n",
" - $\\displaystyle \\frac{u_{0}-v_{0}}{\\sqrt{5}}=\\frac{\\phi-\\psi}{\\sqrt{5}}=\\frac{1}{\\sqrt{5}} \\times \\left( \\frac{1+\\sqrt{5}}{2}-\\frac{1-\\sqrt{5}}{2} \\right)=\\frac{1}{\\sqrt{5}} \\times \\sqrt{5}=1$
\n",
" $\\displaystyle \\frac{u_{1}-v_{1}}{\\sqrt{5}}=\\frac{\\phi^2-\\psi^2}{\\sqrt{5}}=\\frac{1+\\phi- \\left( 1+\\psi \\right) }{\\sqrt{5}}=\\frac{\\phi-\\psi}{\\sqrt{5}}=1$ donc $P(1)$ est vraie. \n",
" - Supposons que $P(n)$ soit vraie pour un entier $n \\geq 1$ fixé.
\n",
" Alors:
\n",
" $F_{n+1}=F_n+F_{n-1}$
\n",
" $\\displaystyle F_{n+1}=\\frac{\\phi^{n+1}-\\psi^{n+1}}{\\sqrt{5}}+\\frac{\\phi^{n}-\\psi^{n}}{\\sqrt{5}}$
\n",
" $\\displaystyle F_{n+1}=\\frac{\\phi^{n+1}-\\psi^{n+1}+\\phi^{n}-\\psi^{n}}{\\sqrt{5}}$
\n",
" $\\displaystyle F_{n+1}=\\frac{(\\phi+1)\\phi^{n}-(\\psi+1)\\psi^{n}}{\\sqrt{5}}$
\n",
" $\\displaystyle F_{n+1}=\\frac{\\phi^2\\phi^{n}-\\psi^2\\psi^{n}}{\\sqrt{5}}$
\n",
" $\\displaystyle F_{n+1}=\\frac{\\phi^{n+2}-\\psi^{n+2}}{\\sqrt{5}}$
\n",
" ce qui prouve que $P(n+1)$ est vraie.\n",
" - On a démontré que $P$ est fondée pour $n=1$ et héréditaire à partir de ce rang, donc $P(n)$ est vraie pour tout $n \\geq 1$.
Ainsi, la formule de Binet est bien démontrée. \n",
"
\n",
"
\n"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1,\n",
" 1,\n",
" 2,\n",
" 3,\n",
" 5,\n",
" 8,\n",
" 13,\n",
" 21,\n",
" 34,\n",
" 55,\n",
" 89,\n",
" 144,\n",
" 233,\n",
" 377,\n",
" 610,\n",
" 987,\n",
" 1597,\n",
" 2584,\n",
" 4181,\n",
" 6765,\n",
" 10946,\n",
" 17711,\n",
" 28657,\n",
" 46368,\n",
" 75025,\n",
" 121393,\n",
" 196418,\n",
" 317811,\n",
" 514229,\n",
" 832040]"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Zone pour les saisies Python (version 1ère Spé Math)\n",
"\n",
"[ simplify( (u(n)-v(n))/sqrt(5) ) for n in range(30) ]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__2.4.a. À l'aide des fonctions Python u et v, écrire une fonction Python F d'argument n qui permet le calcul direct de $F_n$.__"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [],
"source": [
"# Écrire ici la fonction F\n",
"def F(n):\n",
" return simplify( (u(n)-v(n))/sqrt(5) )"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$\\quad$__b. Effectuer une saisie Python pour calculer $F_{10}$, puis pour calculer $F_{50}$.__"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(89, 20365011074)"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Effectuer ici les appels à la fonction F\n",
"F(10),F(50)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3. Complément sur la suite de Fibonacci : Quotients de termes successifs. (Tale Spé Math)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__3.1. Exécuter les cellules Python suivantes.__
\n",
"$\\quad\\;\\;$__Indiquer ce que permet d'obtenir chaque cellule. Quelle conjecture permettent-elles d'énoncer ?__\n",
"
\n",
"Les cellules Python permettent d'évaluer $\\displaystyle \\frac{F_{21}}{F_{20}}$ et $\\displaystyle \\frac{F_{101}}{F_{100}}$.
\n",
"Au vu des résultats, on peut conjecturer que $\\displaystyle \\frac{F_{n+1}}{F_{n}}$ a pour limite $\\phi$ quand $n$ tend vers $+\\infty$"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1.618033985017358"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"float(F(21)/F(20))"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1.618033988749895"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"float(F(101)/F(100))"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1.618033988749895"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"float(phi)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__3.2.a. Vérifier que $\\displaystyle \\left| \\frac{\\psi}{\\phi} \\right|<1$ et en déduire la limite de $\\displaystyle \\left( \\frac{\\psi}{\\phi} \\right)^n$ quand $n$ tend vers $+\\infty$.__\n",
"
\n",
"$\\displaystyle \\left| \\frac{\\psi}{\\phi} \\right|= \\left| \\frac{1-\\sqrt{5}}{1+\\sqrt{5}} \\right| \\simeq 0,38$ donc $\\displaystyle \\left| \\frac{\\psi}{\\phi} \\right|<1$, donc (résultat sur les suites géométriques) :$\\displaystyle\\lim\\limits_{n \\to +\\infty}{ \\left( \\frac{\\psi}{\\phi} \\right)^n }=0$\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$\\quad\\;$__b. Démontrer que pour tout $n \\in \\mathbb{N}$ ; $\\displaystyle \\frac{F_{n+1}}{F_n}= \\phi \\times \\frac{1-\\left( \\frac{\\psi}{\\phi} \\right)^{n+2}}{1-\\left( \\frac{\\psi}{\\phi} \\right)^{n+1}}$.__\n",
"
\n",
"\n",
"Pour tout $n \\in \\mathbb{N}$ ;
\n",
"$\\displaystyle \\frac{F_{n+1}}{F_n}=\\frac{\\phi^{n+2}-\\psi^{n+2}}{\\sqrt{5}}\\times\\frac{\\sqrt{5}}{\\phi^{n+1}-\\psi^{n+1}}$
\n",
"$\\displaystyle \\frac{F_{n+1}}{F_n}=\\frac{\\phi^{n+2}-\\psi^{n+2}}{\\phi^{n+1}-\\psi^{n+1}}$
\n",
"$\\displaystyle \\frac{F_{n+1}}{F_n}=\\frac{ \\phi^{n+2} \\left( 1-\\frac{\\psi^{n+2}}{\\phi^{n+2}} \\right) }{\\phi^{n+1} \\left( 1-\\frac{\\psi^{n+1}}{\\phi^{n+1}} \\right)}$
\n",
"$\\displaystyle \\frac{F_{n+1}}{F_n}= \\phi \\times \\frac{1-\\left( \\frac{\\psi}{\\phi} \\right)^{n+2}}{1-\\left( \\frac{\\psi}{\\phi} \\right)^{n+1}}$ \n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$\\quad\\;$__c. Conclure : Quelle est la limite de $\\displaystyle \\frac{F_{n+1}}{F_n}$ quand $n$ tend vers $+\\infty$ ?__\n",
"
\n",
"\n",
"$\\displaystyle\\lim\\limits_{n \\to +\\infty}{ \\left( \\frac{\\psi}{\\phi} \\right)^{n+2} }=0 \\;$ et $\\displaystyle\\lim\\limits_{n \\to +\\infty}{ \\left( \\frac{\\psi}{\\phi} \\right)^{n+1} }=0\\;$ donc $\\displaystyle \\lim \\limits_{n \\to +\\infty}{ \\frac{1-\\left( \\frac{\\psi}{\\phi} \\right)^{n+2}}{1-\\left( \\frac{\\psi}{\\phi} \\right)^{n+1}} }=1.$
\n",
"On en déduit que $\\displaystyle\\lim\\limits_{n \\to +\\infty}{\\frac{F_{n+1}}{F_n}}=\\phi$.\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
"\n",
" Leonardo Fibonacci (env. 1175 - env. 1250) est un mathématicien italien qui a donné son nom à la suite de Fibonacci."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"*(C) Copyright Franck CHEVRIER 2019-2021 http://www.python-lycee.com/*\n"
]
}
],
"metadata": {
"celltoolbar": "Raw Cell Format",
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.10"
}
},
"nbformat": 4,
"nbformat_minor": 2
}