Raisonnement par récurrence

Un élève affirme que pour tout entier $n⩾1$ : $2+4+6+\cdots +2n=n^2+n+2$. On note $𝒫(n)$ cette égalité.

1. Pour $n=1$, le membre de gauche vaut $2$ et le membre de droite vaut
   Le membre de droite vaut $1^2+1+2=4$, et $4\ne 2$ : $𝒫(1)$ est fausse. L’initialisation échoue.
2. Démontrer que la propriété $𝒫$ est héréditaire. Combien d’entiers $n⩾1$ vérifient l’égalité de l’élève ?
   Rédaction attendue.
   Soit $k⩾1$ un entier fixé. On suppose que $𝒫(k)$ est vraie, c’est-à-dire :
   $2+4+\cdots +2k=k^2+k+2$ (hypothèse de récurrence).
   Montrons que $𝒫(k+1)$ est vraie, c’est-à-dire :
   $2+4+\cdots +2k+2(k+1)$
   $=(k+1{)}^2+(k+1)+2$.
   On part du membre de gauche et on remplace la somme par l’hypothèse :
   $2+4+\cdots +2k+2(k+1)$
   $=k^2+k+2+2k+2$
   $=k^2+3k+4$.
   Or $(k+1{)}^2+(k+1)+2$
   $=k^2+2k+1+k+1+2$
   $=k^2+3k+4$. Donc $𝒫(k+1)$ est vraie : la propriété est héréditaire.
   Mais elle n’est vraie pour aucun entier : $2+4+\cdots +2n$
   $=2(1+2+\cdots +n)$
   $=n(n+1)$
   $=n^2+n$ (formule de l’exercice suivant), qui vaut toujours $2$ de moins que $n^2+n+2$. Comme « $n+1⩽n$ » dans le cours : une hérédité sans initialisation ne prouve rien.

Pour tout entier naturel $n$, on pose $S_n={\sum }_{i=0}^{n}i=0+1+2+\cdots +n$.

1. Démontrer par récurrence que pour tout entier naturel $n$, $S_n={\displaystyle \frac{n(n+1)}{2}}$. En déduire $S_{200}=$
   Rédaction attendue.
   Pour tout entier naturel $n$, on note $𝒫(n)$ la propriété : « $0+1+2+\cdots +n={\displaystyle \frac{n(n+1)}{2}}$ ».
   Initialisation. Pour $n=0$ : le membre de gauche vaut $0$ et le membre de droite vaut ${\displaystyle \frac{0\times 1}{2}}=0$. Donc $𝒫(0)$ est vraie.
   Hérédité. Soit $k\in \mathbb{N}$ un entier fixé. On suppose que $𝒫(k)$ est vraie, c'est-à-dire :
   $0+1+\cdots +k={\displaystyle \frac{k(k+1)}{2}}$ (hypothèse de récurrence)
   Montrons que $𝒫(k+1)$ est vraie, c'est-à-dire :
   $0+1+\cdots +k+(k+1)$
   $={\displaystyle \frac{(k+1)(k+2)}{2}}$
   On part du membre de gauche et on fait apparaître la somme de l'hypothèse :
   $\underset{=\frac{k(k+1)}{2}\text{ par hypothèse}}{\underbrace{0+1+\cdots +k}}+(k+1)$
   $={\displaystyle \frac{k(k+1)}{2}}+(k+1)$
   $=(k+1)({\displaystyle \frac{k}{2}}+1)$
   $={\displaystyle \frac{(k+1)(k+2)}{2}}.$
   Donc $𝒫(k+1)$ est vraie : la propriété est héréditaire.
   Conclusion. La propriété est vraie au rang $0$ et elle est héréditaire, donc, par récurrence, pour tout entier naturel $n$ :
   $S_n={\displaystyle \frac{n(n+1)}{2}}.$
   Application : $S_{200}={\displaystyle \frac{200\times 201}{2}}=20100$.

Pour tout entier $n⩾1$, on pose $S_n={\sum }_{i=1}^n{i}^2=1^2+2^2+\cdots +n^2$.

1. Démontrer par récurrence que pour tout entier $n⩾1$, $S_n={\displaystyle \frac{n(n+1)(2n+1)}{6}}$. En déduire $1^2+2^2+\cdots +{10}^2=$
   Rédaction attendue.
   Pour tout entier $n⩾1$, on note $𝒫(n)$ la propriété : « $1^2+2^2+\cdots +n^2$
   $={\displaystyle \frac{n(n+1)(2n+1)}{6}}$ ».
   Initialisation. Pour $n=1$ : le membre de gauche vaut $1^2=1$ et le membre de droite vaut ${\displaystyle \frac{1\times 2\times 3}{6}}=1$. Donc $𝒫(1)$ est vraie.
   Hérédité. Soit $k⩾1$ un entier fixé. On suppose que $𝒫(k)$ est vraie, c'est-à-dire :
   $1^2+2^2+\cdots +k^2$
   $={\displaystyle \frac{k(k+1)(2k+1)}{6}}$ (hypothèse de récurrence)
   Montrons que $𝒫(k+1)$ est vraie, c'est-à-dire :
   $1^2+\cdots +k^2+(k+1{)}^2$
   $={\displaystyle \frac{(k+1)(k+2)(2k+3)}{6}}$
   On part du membre de gauche et on fait apparaître la somme de l'hypothèse :
   $\underset{=\frac{k(k+1)(2k+1)}{6}}{\underbrace{1^2+\cdots +k^2}}+(k+1{)}^2$
   $={\displaystyle \frac{k(k+1)(2k+1)}{6}}+{\displaystyle \frac{6(k+1{)}^2}{6}}$
   $={\displaystyle \frac{(k+1)[k(2k+1)+6(k+1)]}{6}}$
   $={\displaystyle \frac{(k+1)(2k^2+7k+6)}{6}}.$
   Or $(k+2)(2k+3)$
   $=2k^2+3k+4k+6$
   $=2k^2+7k+6$, donc
   $1^2+\cdots +(k+1{)}^2$
   $={\displaystyle \frac{(k+1)(k+2)(2k+3)}{6}}.$
   Donc $𝒫(k+1)$ est vraie : la propriété est héréditaire.
   Conclusion. La propriété est vraie au rang $1$ et elle est héréditaire, donc, par récurrence, pour tout entier $n⩾1$ :
   $S_n={\displaystyle \frac{n(n+1)(2n+1)}{6}}.$
   Le point clé — Factoriser par $(k+1)$ tout de suite, au lieu de tout développer : on sait que ce facteur doit apparaître dans le résultat. Pour reconnaître $2k^2+7k+6$, on développe la forme attendue $(k+2)(2k+3)$.
   Application : pour $n=10$, ${\displaystyle \frac{10\times 11\times 21}{6}}={\displaystyle \frac{2310}{6}}=385$.

Pour tout entier $n⩾1$, on pose
$S_n={\displaystyle \frac{1}{1\times 2}}+{\displaystyle \frac{1}{2\times 3}}+\cdots +{\displaystyle \frac{1}{n(n+1)}}.$

1. $S_2=$ (fraction irréductible)
   $S_1={\displaystyle \frac{1}{1\times 2}}={\displaystyle \frac{1}{2}}$, puis $S_2={\displaystyle \frac{1}{2}}+{\displaystyle \frac{1}{2\times 3}}={\displaystyle \frac{3}{6}}+{\displaystyle \frac{1}{6}}={\displaystyle \frac{4}{6}}={\displaystyle \frac{2}{3}}$.
2. $S_3=$ (fraction irréductible)
   $S_3=S_2+{\displaystyle \frac{1}{3\times 4}}={\displaystyle \frac{8}{12}}+{\displaystyle \frac{1}{12}}={\displaystyle \frac{9}{12}}={\displaystyle \frac{3}{4}}$.
3. Démontrer par récurrence que pour tout entier $n⩾1$, $S_n=1-{\displaystyle \frac{1}{n+1}}$. En déduire $S_{99}=$
   Rédaction attendue.
   Pour tout entier $n⩾1$, on note $𝒫(n)$ la propriété : « $S_n=1-{\displaystyle \frac{1}{n+1}}$ ».
   Initialisation. Pour $n=1$ : $S_1={\displaystyle \frac{1}{2}}$ et $1-{\displaystyle \frac{1}{1+1}}={\displaystyle \frac{1}{2}}$. Donc $𝒫(1)$ est vraie.
   Hérédité. Soit $k⩾1$ un entier fixé. On suppose que $𝒫(k)$ est vraie, c'est-à-dire :
   $S_k={\displaystyle \frac{1}{1\times 2}}+\cdots +{\displaystyle \frac{1}{k(k+1)}}=1-{\displaystyle \frac{1}{k+1}}$ (hypothèse de récurrence)
   Montrons que $𝒫(k+1)$ est vraie, c'est-à-dire :
   $S_{k+1}=1-{\displaystyle \frac{1}{k+2}}$
   La somme $S_{k+1}$ contient les termes de $S_k$ plus le terme ${\displaystyle \frac{1}{(k+1)(k+2)}}$, donc :
   $S_{k+1}=\underset{=1-\frac{1}{k+1}}{\underbrace{S_k}}+{\displaystyle \frac{1}{(k+1)(k+2)}}$
   $=1-{\displaystyle \frac{k+2}{(k+1)(k+2)}}+{\displaystyle \frac{1}{(k+1)(k+2)}}$
   $=1-{\displaystyle \frac{k+1}{(k+1)(k+2)}}$
   $=1-{\displaystyle \frac{1}{k+2}}.$
   Donc $𝒫(k+1)$ est vraie : la propriété est héréditaire.
   Conclusion. La propriété est vraie au rang $1$ et elle est héréditaire, donc, par récurrence, pour tout entier $n⩾1$ :
   $S_n=1-{\displaystyle \frac{1}{n+1}}.$
   Attention — Le terme ajouté au rang $k+1$ est ${\displaystyle \frac{1}{(k+1)(k+2)}}$ : on remplace $n$ par $k+1$ dans ${\displaystyle \frac{1}{n(n+1)}}$, et pas seulement dans le premier facteur.
   Application : $S_{99}=1-{\displaystyle \frac{1}{100}}=0,99$.

Pour tout entier naturel $n$, on s’intéresse à la somme des cubes $0^3+1^3+\cdots +n^3$.

1. Démontrer par récurrence que pour tout entier naturel $n$, ${\sum }_{i=0}^n{i}^3={\displaystyle \frac{n^2(n+1{)}^2}{4}}$. En déduire $1^3+2^3+\cdots +{10}^3=$
   Rédaction attendue.
   Pour tout entier naturel $n$, on note $𝒫(n)$ la propriété : « $0^3+1^3+\cdots +n^3={\displaystyle \frac{n^2(n+1{)}^2}{4}}$ ».
   Initialisation. Pour $n=0$ : le membre de gauche vaut $0^3=0$ et le membre de droite vaut ${\displaystyle \frac{0^2\times 1^2}{4}}=0$. Donc $𝒫(0)$ est vraie.
   Hérédité. Soit $k\in \mathbb{N}$ un entier fixé. On suppose que $𝒫(k)$ est vraie, c'est-à-dire :
   $0^3+1^3+\cdots +k^3={\displaystyle \frac{k^2(k+1{)}^2}{4}}$ (hypothèse de récurrence)
   Montrons que $𝒫(k+1)$ est vraie, c'est-à-dire :
   $0^3+\cdots +k^3+(k+1{)}^3$
   $={\displaystyle \frac{(k+1{)}^2(k+2{)}^2}{4}}$
   On part du membre de gauche et on fait apparaître la somme de l'hypothèse :
   $\underset{=\frac{k^2(k+1{)}^2}{4}}{\underbrace{0^3+\cdots +k^3}}+(k+1{)}^3$
   $={\displaystyle \frac{k^2(k+1{)}^2+4(k+1{)}^3}{4}}$
   $={\displaystyle \frac{(k+1{)}^2[k^2+4(k+1)]}{4}}$
   $={\displaystyle \frac{(k+1{)}^2(k^2+4k+4)}{4}}$
   $={\displaystyle \frac{(k+1{)}^2(k+2{)}^2}{4}}.$
   Donc $𝒫(k+1)$ est vraie : la propriété est héréditaire.
   Conclusion. La propriété est vraie au rang $0$ et elle est héréditaire, donc, par récurrence, pour tout entier naturel $n$ :
   ${\sum }_{i=0}^n{i}^3={\displaystyle \frac{n^2(n+1{)}^2}{4}}.$
   Application : ${\displaystyle \frac{{10}^2\times {11}^2}{4}}={\displaystyle \frac{100\times 121}{4}}=3025$.
   Le point clé — Mettre $(k+1{)}^2$ en facteur, puis reconnaître l'identité remarquable $k^2+4k+4=(k+2{)}^2$.
2. À l’aide de l’exercice 2, en déduire que ${\sum }_{i=0}^n{i}^3={\left({\sum }_{i=0}^{n}i\right)}^2$. Pour $n=20$, ces deux sommes valent
   Rédaction attendue. D'après l'exercice 2, ${\sum }_{i=0}^{n}i={\displaystyle \frac{n(n+1)}{2}}$, donc
   ${\left({\sum }_{i=0}^{n}i\right)}^2$
   $={\left({\displaystyle \frac{n(n+1)}{2}}\right)}^2$
   $={\displaystyle \frac{n^2(n+1{)}^2}{4}}$
   $={\sum }_{i=0}^n{i}^3$
   d'après la question 1.
   Pour $n=20$ : ${\sum }_{i=0}^{20}i={\displaystyle \frac{20\times 21}{2}}=210$ et ${210}^2=44100$.

Soit $(u_n)$ la suite définie par $u_0=1$ et, pour tout entier naturel $n$, $u_{n+1}={\displaystyle \frac{1}{2}}{u}_n+1$.

1. $u_2=$
   $u_1={\displaystyle \frac{1}{2}}\times 1+1={\displaystyle \frac{3}{2}}$ ; $u_2={\displaystyle \frac{1}{2}}\times {\displaystyle \frac{3}{2}}+1={\displaystyle \frac{3}{4}}+1={\displaystyle \frac{7}{4}}$.
2. Démontrer par récurrence que pour tout entier naturel $n$, $0⩽u_n⩽2$. Dans l’hérédité, en multipliant par ${\displaystyle \frac{1}{2}}$ puis en ajoutant $1$, la borne inférieure $0$ devient
   Rédaction attendue.
   Pour tout entier naturel $n$, on note $𝒫(n)$ la propriété : « $0⩽u_n⩽2$ ».
   Initialisation. Pour $n=0$ : $u_0=1$ et on a bien $0⩽1⩽2$. Donc $𝒫(0)$ est vraie.
   Hérédité. Soit $k\in \mathbb{N}$ un entier fixé. On suppose que $𝒫(k)$ est vraie, c'est-à-dire :
   $0⩽u_k⩽2$ (hypothèse de récurrence)
   Montrons que $𝒫(k+1)$ est vraie, c'est-à-dire :
   $0⩽u_{k+1}⩽2$
   On part de l'hypothèse et on reconstruit $u_{k+1}={\displaystyle \frac{1}{2}}{u}_k+1$ étape par étape. On multiplie chaque membre par ${\displaystyle \frac{1}{2}}>0$, ce qui conserve l'ordre :
   $0⩽{\displaystyle \frac{1}{2}}{u}_k⩽1.$
   On ajoute $1$ à chaque membre :
   $1⩽{\displaystyle \frac{1}{2}}{u}_k+1⩽2,\text{soit}1⩽u_{k+1}⩽2.$
   Comme $0⩽1$, on a bien $0⩽u_{k+1}⩽2$.
   Donc $𝒫(k+1)$ est vraie : la propriété est héréditaire.
   Conclusion. La propriété est vraie au rang $0$ et elle est héréditaire, donc, par récurrence, pour tout entier naturel $n$ :
   $0⩽u_n⩽2.$

Soit $(u_n)$ la suite définie par $u_0=2$ et, pour tout entier naturel $n$, $u_{n+1}=\sqrt{3u_n+4}$.

1. Démontrer par récurrence que pour tout entier naturel $n$, $1⩽u_n⩽4$. Dans l’hérédité, après avoir multiplié par $3$ puis ajouté $4$, on obtient $⩽3u_k+4⩽16$
   Rédaction attendue.
   Pour tout entier naturel $n$, on note $𝒫(n)$ la propriété : « $1⩽u_n⩽4$ ».
   Initialisation. Pour $n=0$ : $u_0=2$ et on a bien $1⩽2⩽4$. Donc $𝒫(0)$ est vraie.
   Hérédité. Soit $k\in \mathbb{N}$ un entier fixé. On suppose que $𝒫(k)$ est vraie, c'est-à-dire :
   $1⩽u_k⩽4$ (hypothèse de récurrence)
   Montrons que $𝒫(k+1)$ est vraie, c'est-à-dire :
   $1⩽u_{k+1}⩽4$
   On part de l'hypothèse et on reconstruit $u_{k+1}=\sqrt{3u_k+4}$ étape par étape. On multiplie par $3>0$, puis on ajoute $4$ :
   $3⩽3u_k⩽12,\text{puis}7⩽3u_k+4⩽16.$
   Ces nombres sont positifs et la fonction racine carrée est croissante sur $[0;+\infty [$, donc :
   $\sqrt{7}⩽\sqrt{3u_k+4}⩽\sqrt{16}$
   $\text{soit }\sqrt{7}⩽u_{k+1}⩽4.$
   Comme $\sqrt{7}⩾1$ (car $7⩾1$), on a bien $1⩽u_{k+1}⩽4$. (Au passage, $3u_k+4⩾7>0$ : le terme $u_{k+1}$ est bien défini.)
   Donc $𝒫(k+1)$ est vraie : la propriété est héréditaire.
   Conclusion. La propriété est vraie au rang $0$ et elle est héréditaire, donc, par récurrence, pour tout entier naturel $n$ :
   $1⩽u_n⩽4.$
   Erreur fréquente — Passer directement de $7⩽3u_k+4⩽16$ à $\sqrt{7}⩽u_{k+1}⩽4$ sans justifier : il faut citer la croissance de la fonction racine carrée sur $[0;+\infty [$.

Soit $f$ la fonction définie sur $[0;2]$ par $f(x)={\displaystyle \frac{3x+2}{x+2}}$, et $(u_n)$ la suite définie par $u_0=0$ et, pour tout entier naturel $n$, $u_{n+1}=f(u_n)$.

1. Calculer $f\prime (x)$ et en déduire le sens de variation de $f$ sur $[0;2]$. On trouve $f\prime (x)={\displaystyle \frac{c}{(x+2{)}^2}}$ avec $c=$
   Rédaction attendue. $f={\displaystyle \frac{u}{v}}$ avec $u(x)=3x+2$, $u\prime (x)=3$, et $v(x)=x+2$, $v\prime (x)=1$ ($v$ ne s'annule pas sur $[0;2]$). Donc
   $f\prime (x)$
   $={\displaystyle \frac{u\prime v-uv\prime }{v^2}}$
   $={\displaystyle \frac{3(x+2)-(3x+2)\times 1}{(x+2{)}^2}}$
   $={\displaystyle \frac{4}{(x+2{)}^2}}.$
   Pour tout $x\in [0;2]$, $f\prime (x)>0$ : $f$ est strictement croissante sur $[0;2]$. De plus $f(0)={\displaystyle \frac{2}{2}}=1$ et $f(2)={\displaystyle \frac{8}{4}}=2$.
2. Démontrer par récurrence que pour tout entier naturel $n$, $0⩽u_n⩽2$. Contrôle : $u_2=$ (fraction irréductible)
   Rédaction attendue.
   Pour tout entier naturel $n$, on note $𝒫(n)$ la propriété : « $0⩽u_n⩽2$ ».
   Initialisation. Pour $n=0$ : $u_0=0$ et on a bien $0⩽0⩽2$. Donc $𝒫(0)$ est vraie.
   Hérédité. Soit $k\in \mathbb{N}$ un entier fixé. On suppose que $𝒫(k)$ est vraie, c'est-à-dire :
   $0⩽u_k⩽2$ (hypothèse de récurrence)
   Montrons que $𝒫(k+1)$ est vraie, c'est-à-dire :
   $0⩽u_{k+1}⩽2$
   Les nombres $0$, $u_k$ et $2$ sont dans $[0;2]$, où $f$ est croissante : elle conserve l'ordre, donc
   $0⩽u_k⩽2$
   $⟹f(0)⩽f(u_k)⩽f(2)$
   $⟹1⩽u_{k+1}⩽2.$
   Comme $0⩽1$, on a bien $0⩽u_{k+1}⩽2$.
   Donc $𝒫(k+1)$ est vraie : la propriété est héréditaire.
   Conclusion. La propriété est vraie au rang $0$ et elle est héréditaire, donc, par récurrence, pour tout entier naturel $n$ :
   $0⩽u_n⩽2.$
   Le point clé — Quand $u_{k+1}$ s'écrit $f(u_k)$ avec une expression compliquée, on ne manipule pas les inégalités « à la main » : on applique $f$, croissante, à l'encadrement. L'hypothèse $u_k\in [0;2]$ garantit aussi que $f(u_k)$ est bien défini.
   Contrôle : $u_1=f(0)=1$, puis $u_2=f(1)={\displaystyle \frac{5}{3}}$, qui est bien dans $[0;2]$.

Soit $f$ la fonction définie sur $[0;1]$ par $f(x)=x(2-x)$, et $(u_n)$ la suite définie par $u_0={\displaystyle \frac{1}{2}}$ et, pour tout entier naturel $n$, $u_{n+1}=f(u_n)$.

1. Étudier le sens de variation de $f$ sur $[0;1]$ : $f\prime (x)$ s’annule en $x=$
   $f(x)=2x-x^2$, donc $f\prime (x)=2-2x=2(1-x)$. Pour $x\in [0;1[$, $f\prime (x)>0$ et $f\prime (1)=0$ : $f$ est strictement croissante sur $[0;1]$ (sa dérivée est strictement positive, sauf en un point), avec $f(0)=0$ et $f(1)=1$.
2. Démontrer par récurrence que pour tout entier naturel $n$ : $0<u_n⩽u_{n+1}<1$. Contrôle : $u_2=$ (fraction irréductible)
   Rédaction attendue.
   Pour tout entier naturel $n$, on note $𝒫(n)$ la propriété : « $0<u_n⩽u_{n+1}<1$ ».
   Initialisation. Pour $n=0$ : $u_0={\displaystyle \frac{1}{2}}$ et $u_1=f\left({\displaystyle \frac{1}{2}}\right)={\displaystyle \frac{1}{2}}(2-{\displaystyle \frac{1}{2}})={\displaystyle \frac{3}{4}}$. On a bien $0<{\displaystyle \frac{1}{2}}⩽{\displaystyle \frac{3}{4}}<1$. Donc $𝒫(0)$ est vraie.
   Hérédité. Soit $k\in \mathbb{N}$ un entier fixé. On suppose que $𝒫(k)$ est vraie, c'est-à-dire :
   $0<u_k⩽u_{k+1}<1$ (hypothèse de récurrence)
   Montrons que $𝒫(k+1)$ est vraie, c'est-à-dire :
   $0<u_{k+1}⩽u_{k+2}<1$
   Les nombres $0$, $u_k$, $u_{k+1}$ et $1$ sont dans $[0;1]$, où $f$ est strictement croissante : elle conserve l'ordre (et les inégalités strictes), donc
   $0<u_k⩽u_{k+1}<1$
   $⟹f(0)<f(u_k)⩽f(u_{k+1})<f(1)$
   $⟹0<u_{k+1}⩽u_{k+2}<1.$
   Donc $𝒫(k+1)$ est vraie : la propriété est héréditaire.
   Conclusion. La propriété est vraie au rang $0$ et elle est héréditaire, donc, par récurrence, pour tout entier naturel $n$ :
   $0<u_n⩽u_{n+1}<1.$
   Contrôle : $u_2=f\left({\displaystyle \frac{3}{4}}\right)={\displaystyle \frac{3}{4}}\times {\displaystyle \frac{5}{4}}={\displaystyle \frac{15}{16}}$.
3. En déduire que $(u_n)$ converge. On admet que sa limite $\ell$ vérifie $f(\ell )=\ell$ : $\ell =$
   Rédaction attendue. D'après la question 2, pour tout $n\in \mathbb{N}$, $u_n⩽u_{n+1}$ : la suite $(u_n)$ est croissante. Elle est aussi majorée par $1$. D'après le théorème de convergence monotone (toute suite croissante et majorée converge), la suite $(u_n)$ est donc convergente.
   Le point clé — Mettre $u_n$ et $u_{n+1}$ dans la même propriété permet d'obtenir en une seule récurrence le sens de variation et l'encadrement.
   Limite : $f(\ell )=\ell$
   $⟺2\ell -{\ell }^2=\ell$
   $⟺\ell (1-\ell )=0$
   $⟺\ell =0$ ou $\ell =1$. Or la suite est croissante, donc $u_n⩾u_0={\displaystyle \frac{1}{2}}$ pour tout $n$, et par passage à la limite $\ell ⩾{\displaystyle \frac{1}{2}}$. Donc $\ell =1$.

Soit $(u_n)$ la suite définie par $u_0=3$ et, pour tout entier naturel $n$, $u_{n+1}=2u_n-1$.

1. Démontrer par récurrence que pour tout entier naturel $n$, $u_n=2^{n+1}+1$. En déduire $u_9=$
   Rédaction attendue.
   Pour tout entier naturel $n$, on note $𝒫(n)$ la propriété : « $u_n=2^{n+1}+1$ ».
   Initialisation. Pour $n=0$ : $u_0=3$ et $2^{0+1}+1=2+1=3$. Donc $𝒫(0)$ est vraie.
   Hérédité. Soit $k\in \mathbb{N}$ un entier fixé. On suppose que $𝒫(k)$ est vraie, c'est-à-dire :
   $u_k=2^{k+1}+1$ (hypothèse de récurrence)
   Montrons que $𝒫(k+1)$ est vraie, c'est-à-dire :
   $u_{k+1}=2^{k+2}+1$
   On part de la relation de récurrence et on remplace $u_k$ par l'hypothèse :
   $u_{k+1}=2\underset{=2^{k+1}+1}{\underbrace{u_k}}-1$
   $=2(2^{k+1}+1)-1$
   $=2^{k+2}+2-1$
   $=2^{k+2}+1.$
   Donc $𝒫(k+1)$ est vraie : la propriété est héréditaire.
   Conclusion. La propriété est vraie au rang $0$ et elle est héréditaire, donc, par récurrence, pour tout entier naturel $n$ :
   $u_n=2^{n+1}+1.$
   Erreur fréquente — Écrire la formule au rang $k+1$ et « vérifier qu'elle marche » : il faut partir de $u_{k+1}=2u_k-1$ et remplacer $u_k$ par l'hypothèse, pas l'inverse.
   Application : $u_9=2^{10}+1=1024+1=1025$.

Soit $(u_n)$ la suite définie par $u_0=2$ et, pour tout entier naturel $n$, $u_{n+1}=u_n+2n+3$.

1. Démontrer par récurrence que pour tout entier naturel $n$, $u_n=(n+1{)}^2+1$. En déduire $u_{20}=$
   Rédaction attendue.
   Pour tout entier naturel $n$, on note $𝒫(n)$ la propriété : « $u_n=(n+1{)}^2+1$ ».
   Initialisation. Pour $n=0$ : $u_0=2$ et $(0+1{)}^2+1=1+1=2$. Donc $𝒫(0)$ est vraie.
   Hérédité. Soit $k\in \mathbb{N}$ un entier fixé. On suppose que $𝒫(k)$ est vraie, c'est-à-dire :
   $u_k=(k+1{)}^2+1$ (hypothèse de récurrence)
   Montrons que $𝒫(k+1)$ est vraie, c'est-à-dire :
   $u_{k+1}=(k+2{)}^2+1$
   On part de la relation de récurrence et on remplace $u_k$ par l'hypothèse :
   $u_{k+1}=\underset{=(k+1{)}^2+1}{\underbrace{u_k}}+2k+3$
   $=k^2+2k+1+1+2k+3$
   $=k^2+4k+5$
   $=(k^2+4k+4)+1$
   $=(k+2{)}^2+1.$
   Donc $𝒫(k+1)$ est vraie : la propriété est héréditaire.
   Conclusion. La propriété est vraie au rang $0$ et elle est héréditaire, donc, par récurrence, pour tout entier naturel $n$ :
   $u_n=(n+1{)}^2+1.$
   Le point clé — Pour reconnaître $(k+2{)}^2+1$, on développe la cible : $(k+2{)}^2+1=k^2+4k+5$. Il suffit alors de faire apparaître $k^2+4k+4$.
   Application : $u_{20}={21}^2+1=441+1=442$.

Soit $(u_n)$ la suite définie par $u_0=2$ et, pour tout entier naturel $n$, $u_{n+1}={\displaystyle \frac{u_n}{1+u_n}}$.

1. Démontrer par récurrence que pour tout entier naturel $n$, $u_n={\displaystyle \frac{2}{2n+1}}$. En déduire $u_{10}=$ (fraction irréductible)
   Rédaction attendue.
   Pour tout entier naturel $n$, on note $𝒫(n)$ la propriété : « $u_n={\displaystyle \frac{2}{2n+1}}$ ».
   Initialisation. Pour $n=0$ : $u_0=2$ et ${\displaystyle \frac{2}{2\times 0+1}}={\displaystyle \frac{2}{1}}=2$. Donc $𝒫(0)$ est vraie.
   Hérédité. Soit $k\in \mathbb{N}$ un entier fixé. On suppose que $𝒫(k)$ est vraie, c'est-à-dire :
   $u_k={\displaystyle \frac{2}{2k+1}}$ (hypothèse de récurrence)
   Montrons que $𝒫(k+1)$ est vraie, c'est-à-dire :
   $u_{k+1}={\displaystyle \frac{2}{2(k+1)+1}}={\displaystyle \frac{2}{2k+3}}$
   On part de la relation de récurrence et on remplace $u_k$ par l'hypothèse (le calcul est licite : $u_k>0$, donc $1+u_k\ne 0$) :
   $u_{k+1}={\displaystyle \frac{u_k}{1+u_k}}$
   $={\displaystyle \frac{\frac{2}{2k+1}}{1+\frac{2}{2k+1}}}$
   $={\displaystyle \frac{\frac{2}{2k+1}}{\frac{2k+3}{2k+1}}}$
   $={\displaystyle \frac{2}{2k+1}}\times {\displaystyle \frac{2k+1}{2k+3}}$
   $={\displaystyle \frac{2}{2k+3}}.$
   Donc $𝒫(k+1)$ est vraie : la propriété est héréditaire.
   Conclusion. La propriété est vraie au rang $0$ et elle est héréditaire, donc, par récurrence, pour tout entier naturel $n$ :
   $u_n={\displaystyle \frac{2}{2n+1}}.$
   Le point clé — Mettre $1+u_k$ au même dénominateur, puis multiplier par l'inverse. Et toujours vérifier que le dénominateur ne s'annule pas avant de diviser : ici, c'est l'hypothèse de récurrence qui le garantit.
   Application : $u_{10}={\displaystyle \frac{2}{2\times 10+1}}={\displaystyle \frac{2}{21}}$.

Soit $(u_n)$ la suite définie par $u_0=0$ et, pour tout entier naturel $n$, $u_{n+1}={\displaystyle \frac{1}{2-u_n}}$.

1. Calculer $u_1$, $u_2$ et $u_3$ : $u_3=$ (fraction irréductible)
   $u_1={\displaystyle \frac{1}{2-0}}={\displaystyle \frac{1}{2}}$ ; $u_2={\displaystyle \frac{1}{2-\frac{1}{2}}}={\displaystyle \frac{1}{\frac{3}{2}}}={\displaystyle \frac{2}{3}}$ ; $u_3={\displaystyle \frac{1}{2-\frac{2}{3}}}={\displaystyle \frac{1}{\frac{4}{3}}}={\displaystyle \frac{3}{4}}$.
2. Conjecturer une expression de $u_n$ en fonction de $n$, puis la démontrer par récurrence. Contrôle : $u_{49}=$
   On a $u_0={\displaystyle \frac{0}{1}}$, $u_1={\displaystyle \frac{1}{2}}$, $u_2={\displaystyle \frac{2}{3}}$, $u_3={\displaystyle \frac{3}{4}}$. On conjecture que pour tout $n\in \mathbb{N}$, $u_n={\displaystyle \frac{n}{n+1}}$.
   Rédaction attendue.
   Pour tout entier naturel $n$, on note $𝒫(n)$ la propriété : « $u_n={\displaystyle \frac{n}{n+1}}$ ».
   Initialisation. Pour $n=0$ : $u_0=0$ et ${\displaystyle \frac{0}{0+1}}=0$. Donc $𝒫(0)$ est vraie.
   Hérédité. Soit $k\in \mathbb{N}$ un entier fixé. On suppose que $𝒫(k)$ est vraie, c'est-à-dire :
   $u_k={\displaystyle \frac{k}{k+1}}$ (hypothèse de récurrence)
   Montrons que $𝒫(k+1)$ est vraie, c'est-à-dire :
   $u_{k+1}={\displaystyle \frac{k+1}{k+2}}$
   On part de la relation de récurrence et on remplace $u_k$ par l'hypothèse (le calcul est licite : $u_k={\displaystyle \frac{k}{k+1}}<1$, donc $2-u_k\ne 0$) :
   $u_{k+1}={\displaystyle \frac{1}{2-u_k}}$
   $={\displaystyle \frac{1}{2-\frac{k}{k+1}}}$
   $={\displaystyle \frac{1}{\frac{2(k+1)-k}{k+1}}}$
   $={\displaystyle \frac{1}{\frac{k+2}{k+1}}}$
   $={\displaystyle \frac{k+1}{k+2}}.$
   Donc $𝒫(k+1)$ est vraie : la propriété est héréditaire.
   Conclusion. La propriété est vraie au rang $0$ et elle est héréditaire, donc, par récurrence, pour tout entier naturel $n$ :
   $u_n={\displaystyle \frac{n}{n+1}}.$
   Attention — Calculer $u_1$, $u_2$, $u_3$ ne prouve rien : c'est seulement une conjecture. Seule la récurrence permet de conclure pour tout $n$.
   Contrôle : $u_{49}={\displaystyle \frac{49}{50}}=0,98$.

Divisibilité de $7^n-1$.

1. Démontrer par récurrence que pour tout entier naturel $n$, $7^n-1$ est divisible par $6$. Dans l’hérédité, on obtient $7^{k+1}-1=6(am+1)$, où $m$ est l’entier de l’hypothèse, avec $a=$
   Rédaction attendue.
   Pour tout entier naturel $n$, on note $𝒫(n)$ la propriété : « $7^n-1$ est divisible par $6$ ».
   Initialisation. Pour $n=0$ : $7^0-1=0=6\times 0$, et $0$ est un entier. Donc $𝒫(0)$ est vraie.
   Hérédité. Soit $k\in \mathbb{N}$ un entier fixé. On suppose que $𝒫(k)$ est vraie, c'est-à-dire qu'il existe un entier $m$ tel que $7^k-1=6m$, soit
   $7^k=6m+1$ (hypothèse de récurrence)
   Montrons que $𝒫(k+1)$ est vraie, c'est-à-dire qu'il existe un entier $m\prime$ tel que $7^{k+1}-1=6m\prime$.
   On écrit $7^{k+1}=7\times 7^k$ et on remplace $7^k$ grâce à l'hypothèse :
   $7^{k+1}-1=7\times \underset{=6m+1}{\underbrace{7^k}}-1$
   $=7(6m+1)-1$
   $=42m+6$
   $=6(7m+1).$
   Comme $m$ est un entier, $m\prime =7m+1$ est un entier, et $7^{k+1}-1=6m\prime$.
   Donc $𝒫(k+1)$ est vraie : la propriété est héréditaire.
   Conclusion. La propriété est vraie au rang $0$ et elle est héréditaire, donc, par récurrence, pour tout entier naturel $n$, $7^n-1$ est divisible par $6$.
   Le point clé — Isoler la puissance dans l'hypothèse ($7^k=6m+1$) : il suffit ensuite de remplacer et de factoriser par $6$.

Le produit de trois entiers consécutifs : $n^3-n=(n-1)n(n+1)$.

1. Soit $k$ un entier. On développe : $(k+1{)}^3=k^3+a{k}^2+3k+1$ avec $a=$
   $(k+1{)}^3$
   $=(k+1{)}^2(k+1)$
   $=(k^2+2k+1)(k+1)$
   $=k^3+3k^2+3k+1$.
2. Démontrer par récurrence que pour tout entier naturel $n$, $n^3-n$ est divisible par $3$. Contrôle : ${10}^3-10=3\times$
   Rédaction attendue.
   Pour tout entier naturel $n$, on note $𝒫(n)$ la propriété : « $n^3-n$ est divisible par $3$ ».
   Initialisation. Pour $n=0$ : $0^3-0=0=3\times 0$. Donc $𝒫(0)$ est vraie.
   Hérédité. Soit $k\in \mathbb{N}$ un entier fixé. On suppose que $𝒫(k)$ est vraie, c'est-à-dire qu'il existe un entier $m$ tel que
   $k^3-k=3m$ (hypothèse de récurrence)
   Montrons que $𝒫(k+1)$ est vraie, c'est-à-dire qu'il existe un entier $m\prime$ tel que $(k+1{)}^3-(k+1)=3m\prime$.
   On développe avec la question 1, puis on fait apparaître $k^3-k$ :
   $(k+1{)}^3-(k+1)$
   $=k^3+3k^2+3k+1-k-1$
   $=\underset{=3m}{\underbrace{(k^3-k)}}+3k^2+3k$
   $=3(m+k^2+k).$
   Comme $m$ et $k$ sont des entiers, $m\prime =m+k^2+k$ est un entier, et $(k+1{)}^3-(k+1)=3m\prime$.
   Donc $𝒫(k+1)$ est vraie : la propriété est héréditaire.
   Conclusion. La propriété est vraie au rang $0$ et elle est héréditaire, donc, par récurrence, pour tout entier naturel $n$, $n^3-n$ est divisible par $3$.
   Le point clé — Le titre s'explique : $n^3-n=(n-1)n(n+1)$ est le produit de trois entiers consécutifs. Dans l'hérédité, l'objectif est toujours de faire apparaître l'expression de l'hypothèse.
   Contrôle : ${10}^3-10=990=3\times 330$.

Deux puissances à la fois : on étudie $3^{2n+1}+2^{n+2}$ pour tout entier naturel $n$.

1. Pour $n=1$, $3^{2n+1}+2^{n+2}=$
   Pour $n=0$ : $3^1+2^2=3+4=7=7\times 1$. Pour $n=1$ : $3^3+2^3=27+8=35=7\times 5$.
2. Soit $k$ un entier naturel. Justifier que $3^{2(k+1)+1}=a\times 3^{2k+1}$ et que $2^{(k+1)+2}=2\times 2^{k+2}$ : $a=$
   $3^{2(k+1)+1}=3^{2k+3}=3^2\times 3^{2k+1}=9\times 3^{2k+1}$ et $2^{(k+1)+2}=2^{k+3}=2\times 2^{k+2}$.
3. Démontrer par récurrence que pour tout entier naturel $n$, $3^{2n+1}+2^{n+2}$ est divisible par $7$. Contrôle : pour $n=2$, $3^5+2^4=7\times$
   Rédaction attendue.
   Pour tout entier naturel $n$, on note $𝒫(n)$ la propriété : « $3^{2n+1}+2^{n+2}$ est divisible par $7$ ».
   Initialisation. Pour $n=0$ : $3^1+2^2=7=7\times 1$ (question 1). Donc $𝒫(0)$ est vraie.
   Hérédité. Soit $k\in \mathbb{N}$ un entier fixé. On suppose que $𝒫(k)$ est vraie, c'est-à-dire qu'il existe un entier $m$ tel que $3^{2k+1}+2^{k+2}=7m$, soit
   $3^{2k+1}=7m-2^{k+2}$ (hypothèse de récurrence)
   Montrons que $𝒫(k+1)$ est vraie, c'est-à-dire qu'il existe un entier $m\prime$ tel que $3^{2k+3}+2^{k+3}=7m\prime$.
   D'après la question 2, puis en remplaçant $3^{2k+1}$ grâce à l'hypothèse :
   $3^{2k+3}+2^{k+3}$
   $=9\times \underset{=7m-2^{k+2}}{\underbrace{3^{2k+1}}}+2\times 2^{k+2}$
   $=63m-9\times 2^{k+2}+2\times 2^{k+2}$
   $=63m-7\times 2^{k+2}$
   $=7(9m-2^{k+2}).$
   Comme $m$ est un entier et $2^{k+2}$ aussi ($k⩾0$), $m\prime =9m-2^{k+2}$ est un entier, et $3^{2k+3}+2^{k+3}=7m\prime$.
   Donc $𝒫(k+1)$ est vraie : la propriété est héréditaire.
   Conclusion. La propriété est vraie au rang $0$ et elle est héréditaire, donc, par récurrence, pour tout entier naturel $n$, $3^{2n+1}+2^{n+2}$ est divisible par $7$.
   Le point clé — On isole une seule des deux puissances dans l'hypothèse. Les termes en $2^{k+2}$ se regroupent alors en $-7\times 2^{k+2}$ : c'est le $7$ qui « apparaît tout seul ».
   Contrôle : $3^5+2^4=243+16=259=7\times 37$.

Divisible par $6$.

1. Démontrer que pour tout entier naturel $k$, le produit $k(k+1)$ est pair. Contrôle : $13\times 14$ est le double de
   Rédaction attendue. Parmi les deux entiers consécutifs $k$ et $k+1$, l'un est pair. Si $k$ est pair, $k=2q$ avec $q$ entier et $k(k+1)=2q(k+1)$ ; si $k$ est impair, $k+1=2q$ avec $q$ entier et $k(k+1)=2qk$. Dans les deux cas, $k(k+1)$ est pair.
2. Démontrer par récurrence que pour tout entier naturel $n$, $n^3+5n$ est divisible par $6$. Contrôle : $7^3+5\times 7$ est égal à $6$ fois
   Rédaction attendue.
   Pour tout entier naturel $n$, on note $𝒫(n)$ la propriété : « $n^3+5n$ est divisible par $6$ ».
   Initialisation. Pour $n=0$ : $0^3+5\times 0=0=6\times 0$. Donc $𝒫(0)$ est vraie.
   Hérédité. Soit $k\in \mathbb{N}$ un entier fixé. On suppose que $𝒫(k)$ est vraie, c'est-à-dire qu'il existe un entier $m$ tel que
   $k^3+5k=6m$ (hypothèse de récurrence)
   Montrons que $𝒫(k+1)$ est vraie, c'est-à-dire qu'il existe un entier $m\prime$ tel que $(k+1{)}^3+5(k+1)=6m\prime$.
   On développe, puis on fait apparaître $k^3+5k$ :
   $(k+1{)}^3+5(k+1)$
   $=k^3+3k^2+3k+1+5k+5$
   $=\underset{=6m}{\underbrace{(k^3+5k)}}+3k^2+3k+6$
   $=6m+3k(k+1)+6.$
   D'après la question 1, $k(k+1)$ est pair : il existe un entier $p$ tel que $k(k+1)=2p$, donc $3k(k+1)=6p$. Ainsi
   $(k+1{)}^3+5(k+1)$
   $=6m+6p+6$
   $=6(m+p+1).$
   Comme $m$ et $p$ sont des entiers, $m\prime =m+p+1$ est un entier.
   Donc $𝒫(k+1)$ est vraie : la propriété est héréditaire.
   Conclusion. La propriété est vraie au rang $0$ et elle est héréditaire, donc, par récurrence, pour tout entier naturel $n$, $n^3+5n$ est divisible par $6$.
   Contrôle : $7^3=343$, donc $7^3+5\times 7$ vaut $343+35=378=6\times 63$.
3. En déduire que pour tout entier naturel $n$, $n^3-n$ est divisible par $6$. Contrôle : $9^3-9$ est égal à $6$ fois
   Rédaction attendue. Pour tout entier naturel $n$, $n^3-n=(n^3+5n)-6n$. D'après la question 2, il existe un entier $m$ tel que $n^3+5n=6m$, donc $n^3-n=6m-6n=6(m-n)$, avec $m-n$ entier : $n^3-n$ est divisible par $6$.
   Le point clé — Le terme $3k^2+3k=3k(k+1)$ n'est pas un multiple de $6$ « à vue » : il faut l'argument de parité de la question 1. Une hérédité peut demander un résultat auxiliaire, qu'on démontre à part.
   Contrôle : $9^3=729$, donc $9^3-9$ vaut $729-9=720=6\times 120$.