Suites et récurrence/Exercices/Démonstration par récurrence

Récurrence simple

Montrer par récurrence les propriétés suivantes :

1. $\forall n\in \mathbb {N} ^{*}\quad \sum _{1\leq j\leq n}{(j\times j!)}=(n+1)!-1$ ;
2. $\forall n\in \mathbb {N} \quad {\frac {1}{n!}}\leq {\frac {1}{2^{n-1}}}$ ;
3. $\forall n\in \mathbb {N} \quad 5^{n}-2^{n}$ est multiple de 3 ;
4. $\forall n\geq 2\quad 3^{n}\geq 2^{n}+{\frac {5n}{2}}$.

Solution

1. Notons ${\mathcal {P}}_{n}$ la propriété « $\sum _{1\leq j\leq n}{(j\times j!)}=(n+1)!-1$ ».
   • Intitialisation : $\sum _{1\leq j\leq 1}{(j\times j!)}=1\times 1!=1$ et $(1+1)!-1=2!-1=1$, donc ${\mathcal {P}}_{1}$ est vraie.
   • Hérédité : soit $n\in \mathbb {N} ^{*}$ tel que ${\mathcal {P}}_{n}$ soit vraie, montrons que ${\mathcal {P}}_{n+1}$ est vraie.
     Par définition, $\sum _{1\leq j\leq n+1}{(j\times j!)}$ est égal à $(n+1)\times (n+1)!+\sum _{1\leq j\leq n}{(j\times j!)}$ donc (par hypothèse de récurrence) à $(n+1)\times (n+1)!+(n+1)!-1=(n+2)\times (n+1)!-1=(n+2)!-1$, donc ${\mathcal {P}}_{n+1}$ est vraie.
   • Conclusion : le principe de récurrence permet de conclure : $\forall n\in \mathbb {N} ^{*}\quad {\mathcal {P}}_{n}$.
   • Remarque : $(0+1)!-1=0$ et par convention sur les sommes vides $\sum _{1\leq j\leq 0}{(j\times j!)}=0$ donc ${\mathcal {P}}_{0}$ est vraie. Cette convention est cohérente avec la définition par récurrence des sommes indexées utilisée dans la preuve d'hérédité ci-dessus, qui reste valide pour $n\in \mathbb {N}$. On aurait donc pu initialiser la récurrence à $n=0$ et démontrer ainsi : $\forall n\in \mathbb {N} \quad {\mathcal {P}}_{n}$.
2. Notons ${\mathcal {Q}}_{n}$ la propriété « ${\frac {1}{n!}}\leq {\frac {1}{2^{n-1}}}$ ».
   • Hérédité : soit $n\in \mathbb {N}$ tel que ${\mathcal {Q}}_{n}$ soit vraie, essayons de montrer que ${\mathcal {Q}}_{n+1}$ est vraie.
     ${\frac {1}{(n+1)!}}={\frac {1}{(n+1)\times n!}}={\frac {1}{n+1}}\times {\frac {1}{n!}}$ est inférieur ou égal (par hypothèse de récurrence) à ${\frac {1}{n+1}}\times {\frac {1}{2^{n-1}}}$ qui, à condition que $n\geq 1$, est lui-même majoré par ${\frac {1}{2}}\times {\frac {1}{2^{n-1}}}={\frac {1}{2^{(n+1)-1}}}$. On a donc bien ${\mathcal {Q}}_{n}\Rightarrow {\mathcal {Q}}_{n+1}$, mais seulement pour tout entier $n\in \mathbb {N} ^{*}$. Ceci oblige à initialiser la récurrence à $n=1$, et à étudier séparément le cas $n=0$.
   • Intitialisation : ${\frac {1}{1!}}={\frac {1}{1}}=1$ et ${\frac {1}{2^{1-1}}}=1$, donc ${\mathcal {Q}}_{1}$ est vraie.
   • Conclusion : le principe de récurrence permet de conclure : $\forall n\in \mathbb {N} ^{*}\quad {\mathcal {Q}}_{n}$.
   • Cas $n=0$ : ${\frac {1}{0!}}={\frac {1}{1}}=1$ et ${\frac {1}{2^{0-1}}}=2$. Puisque $1\leq 2$, ${\mathcal {Q}}_{0}$ est vraie.
   • Synthèse : de $\forall n\in \mathbb {N} ^{*}\quad {\mathcal {Q}}_{n}$ et ${\mathcal {Q}}_{0}$, on déduit : $\forall n\in \mathbb {N} \quad {\mathcal {Q}}_{n}$.
3. Notons ${\mathcal {R}}_{n}$ la propriété « $5^{n}-2^{n}$ est multiple de 3 ».
   • Intitialisation : $5^{0}-2^{0}=1-1=0=3\times 0$, donc ${\mathcal {R}}_{0}$ est vraie.
   • Hérédité : soit $n\in \mathbb {N}$ tel que ${\mathcal {R}}_{n}$ soit vraie, montrons que ${\mathcal {R}}_{n+1}$ est vraie.
     Par hypothèse de récurrence, il existe un entier $k$ tel que $5^{n}-2^{n}=3k$. Alors, $5^{n+1}-2^{n+1}=5\times 5^{n}-2^{n+1}=5(3k+2^{n})-2^{n+1}=15k+(5-2)2^{n}=3(5k+2^{n})$ donc ${\mathcal {R}}_{n+1}$ est vraie.
   • Conclusion : le principe de récurrence permet de conclure : $\forall n\in \mathbb {N} \quad {\mathcal {R}}_{n}$.
4. Notons ${\mathcal {S}}_{n}$ la propriété « $3^{n}\geq 2^{n}+{\frac {5n}{2}}$ » (vraie pour $n=0$ mais fausse pour $n=1$).
   • Intitialisation : $2^{2}+5{\frac {2}{2}}=4+5=9=3^{2}$, donc l'inégalité large ${\mathcal {S}}_{2}$ est vraie.
   • Hérédité : soit $n\geq 2$ tel que ${\mathcal {S}}_{n}$ soit vraie, montrons que ${\mathcal {S}}_{n+1}$ est vraie.
     Par hypothèse de récurrence, $3^{n+1}\geq 3\left(2^{n}+{\frac {5n}{2}}\right)$. Or $3\times 2^{n}>2^{n+1}$ et $3n>n+1$, donc $3\left(2^{n}+{\frac {5n}{2}}\right)>2^{n+1}+{\frac {5(n+1)}{2}}$, donc ${\mathcal {S}}_{n+1}$ est vraie.
     Variante : puisque $3.2^{n}-2^{n+1}=(3-2).2^{n}=2^{n}$ et $3.{5n \over 2}-{5(n+1) \over 2}=5n-{5 \over 2}$, il suffit de montrer que $2^{n}+5n\geq {\frac {5}{2}}$. Or on a $n>1$ donc $2^{n}+5n>2+5=7>{\frac {5}{2}}$, cqfd.
   • Conclusion : le principe de récurrence permet de conclure : $\forall n\geq 2\quad 3^{n}\geq 2^{n}+{\frac {5n}{2}}$.

   Autre méthode (sans récurrence) : d'après l'inégalité de Bernoulli, $(3/2)^{n}=(1+1/2)^{n}>1+n/2$ donc $3^{n}>2^{n}+n.2^{n-1}$, or $2^{n-1}\geq 5/2$ dès que $n\geq 3$.

 

Chercher l'erreur

Voici un raisonnement (par récurrence) dont la conclusion est que toutes les vaches sont de la même couleur. Comme le nombre de vaches dans le monde est assurément fini, on va en fait montrer la propriété ${\mathcal {P}}_{n}\quad (n\geq 1)$ : « pour tout entier $n>0$ et pour tout groupe de $n$ vaches, toutes les vaches de ce groupe sont de la même couleur ». Voici cette « preuve » :

• Initialisation : pour $n=1$, toutes les vaches d'un groupe composé d'une seule vache ont certainement la même couleur puisqu'une vache a la même couleur qu'elle-même.
• Hérédité : hypothèse de récurrence : on suppose que ${\mathcal {P}}_{n}$ est vraie pour un entier $n\geq 1$ fixé et l'on considère un groupe de $n+1$ vaches. On les range l'une derrière l'autre. Par hypothèse de récurrence, les $n$ premières sont toutes de la même couleur et la dernière est aussi de cette couleur (par exemple en tant que membre des $n$ dernières), ce qui montre bien que les $n+1$ vaches sont de la même couleur.

Quelle erreur a-t-on commise dans ce raisonnement ?

Solution

. Dans la preuve d'hérédité, pour $n=1$, l'erreur est dans la parenthèse qui prétend justifier que la dernière vache est de la même couleur que les $n$ premières.