Raisonnement par récurrence : corrigé des exercices de maths en terminale à télécharger en PDF

Exercice 1 :
Soit \((U_n) \,\) la suite définie par

\(\begin{cases}U_0=2\\ \forall n \in\,\mathbb{N}\,,\,U_{n+1}=\sqrt{U_n+2}\end{cases}\)

Démontrer par récurrence que :

\(\boxed{\forall n \in\,\mathbb{N}\,,\,U_n\le2 }\,\)

soit la propriété de récurrence \(P(n)\) : « \(0\le U_n\le2\) » pour \(n \in\,\mathbb{N}\).

Initialisation : P(0)

\(0\le U_0=2\le 2\) donc P(0) vraie.

Supposons qu’il existe \(n \in\,\mathbb{N}\) tel que P(n) soit vraie, Montrons P(n+1) reste vraie.

\(0\le U_n\le 2\Rightarrow 2\le U_n+2\le 4 \Rightarrow 0\le\sqrt{U_n+2}\le \sqrt{4}\Rightarrow 0\le U_{n+1}\le 2\) (la fonction racine carrée est croissante sur \([0\,;+\infty[\)).

donc P(n+1) reste vraie

\((P(0); \forall n \in\,\mathbb{N}\,,\,P(n)\Rightarrow P(n+1))\)

\(\Rightarrow \forall n \in\,\mathbb{N}\,,U_n\le2\)

Exercice 2 :

Soit \((U_n) \,.\) la suite définie par

\(\begin{cases}U_0=2\\ \forall n \in\,\mathbb{N}\,,\,U_{n+1}=2U_n-3\end{cases}\)

Démontrer par récurrence que :

\(\boxed{\forall n \in\,\mathbb{N}\,,\,U_n=3-2^n }\,.\)

soit la propriété de récurrence \(P(n)\) : « \(U_n=3-2^n\) » pour \(n \in\,\mathbb{N}\).

Initialisation : P(0)

\(U_0=2=3-2^0\) donc P(0) vraie.

Supposons qu’il existe \(n \in\,\mathbb{N}\) tel que P(n) soit vraie, Montrons P(n+1) reste vraie.

\(U_n=3-2^n\Rightarrow 2U_n=6-2^{n+1} \Rightarrow 2U_n-3=3-2^{n+1} \Rightarrow U_{n+1}=3-2^{n+1}\)

donc P(n+1) reste vraie

\((P(0); \forall n \in\,\mathbb{N}\,,\,P(n)\Rightarrow P(n+1))\)

\(\Rightarrow \forall n \in\,\mathbb{N}\,,U_n=3-2^n\)

Exercice 3 :

On pose :

\(\forall n \in\,\mathbb{N^*}\,,\,S_n=1^2+2^2+3^2+….+n^2=\sum_{k=1}^n k^2 \,.\)

a. Calculer \(S_1\,,S_2\,,S_3\,,S_4 \,.\)

\(S_1=1^2=1\,;\,S_2=1^2+2^2=1+4=5\,;\,S_3=1^2+2^2+3^2=1+4+9=14\,;\,S_4=1^2+2^2+3^2+4^2=14+16=30 \,.\)

b. Exprimer \(S_{n+1}\) en fonction de \(S_n\) .

\(\forall n \in\,\mathbb{N^*}\,,\, S_{n+1}=S_n+(n+1)^2\)

c. Démontrer par récurrence que :

\(\boxed{ \forall n \in\,\mathbb{N^*}\,\,S_n=\frac{n(n+1)(2n+1)}{6} }\,.\)

soit la propriété de récurrence :

\(P(n)\) : « \(S_n=\frac{n(n+1)(2n+1)}{6}\) » pour \(n \in\,\mathbb{N^*}\).

Initialisation : P(1)

\(S_1=1=\frac{1(1+1)(2\times 1+1)}{6}\) donc P(1) vraie.

Supposons qu’il existe \(n \in\,\mathbb{N^*}\) tel que P(n) soit vraie, Montrons P(n+1) reste vraie.

\(S_{n+1}=S_n+(n+1)^2\Leftrightarrow S_{n+1}=\frac{n(n+1)(2n+1)}{6}+(n+1)^2 \Leftrightarrow S_{n+1}=\frac{n(n+1)(2n+1)+6(n+1)^2}{6} \Leftrightarrow S_{n+1}=\frac{(n+1)[n(2n+1)+6(n+1)]}{6}\)

\(\Leftrightarrow S_{n+1}=\frac{(n+1)(2n^2+7n+6)}{6}=\frac{(n+1)(n+2)(2(n+1)+1)}{6}\)

donc P(n+1) reste vraie

\((P(1); \forall n \in\,\mathbb{N^*}\,,\,P(n)\Rightarrow P(n+1))\)

\(\Rightarrow \forall n \in\,\mathbb{N^*}\,,S_n=\frac{n(n+1)(2n+1)}{6}\)

Exercice 4 :

1. Pour tout \(n\in\mathbb{N}\), on développe le membre de droite :

\(y(x^n\,-\,y^n)\,+\,(x\,-\,y)x^n\,=\,yx^n\,-\,y^{n+1}\,+\,x^{n+1}\,-\,yx^n\,=\,x^{n+1}\,-\,y^{n+1}\)

Les termes \(yx^n\) et \(-yx^n\) s’éliminent : on retrouve bien \(x^{n+1}-y^{n+1}\).

Donc, pour tout entier naturel n, \(x^{n+1}-y^{n+1}=y(x^n-y^n)+(x-y)x^n\).

2. Quand k = n, on a :

\(x^ky^{n-k}\,=\,x^n\,y^{n-n}\,=\,x^n\,y^0\,=\,x^n\)

3. Soit \(P(n)\) la propriété : « \(x^n-y^n=(x-y)\sum_{k=0}^{n-1}x^ky^{n-1-k}\) ».

Initialisation : la propriété est vraie pour n = 1 car :

\(x^1\,-\,y^1\,=\,x\,-\,y\,=\,(x\,-\,y)\,\sum_{k=0}^{0}\,x^ky^{0-k}\,=\,(x-y)\times x^0y^0\)

Hérédité : supposons que P(n) soit vraie pour un certain entier naturel non nul n. On a :

\(x^{n+1}\,-\,y^{n+1}\,=\,y(x^n\,-\,y^n)\,+\,(x\,-\,y)x^{n}\) par la formule obtenue à la question 1,
et donc, avec l’hypothèse de récurrence :

\(x^{n+1}\,-\,y^{n+1}\,=\,y(x-y)\,\sum_{k=0}^{n-1}\,x^ky^{n-1-k}\,+\,(x-y)x^{n}\,=\,(x-y)\,(\,\sum_{k=0}^{n-1}\,x^ky^{n-k}\,+\,x^{n}\,)\)

D’après la question 2, \(x^n\) est le terme \(x^ky^{n-k}\) pour k = n, donc :

\(x^{n+1}\,-\,y^{n+1}\,=\,(x-y)\sum_{k=0}^{n}x^ky^{n-k}\), ce qui est P(n+1).

Donc, pour tout \(n\in\mathbb{N}^*\), \(x^n-y^n=(x-y)\sum_{k=0}^{n-1}x^ky^{n-1-k}\).

Exercice 5 :

1. Soient a et x deux nombres tels que \(a\in\,\mathbb{Q}\) et \(x\notin\,\mathbb{Q}\).

On suppose par l’absurde que \(a+x\in\,\mathbb{Q}\).

Alors il existe deux entiers relatifs p et q avec \(q\neq\,0\) tels que \(a+x=\frac{p}{q}\).

On peut réarranger cette équation pour obtenir \(x=\frac{p}{q}-a\), qui est donc un nombre rationnel puisque p, q et a sont des nombres rationnels, ce qui contredit l’hypothèse que \(x\notin\,\mathbb{Q}\).

Donc, \(a+x\notin\,\mathbb{Q}\).

2. Soient a et x deux nombres tels que \(a\in\,\mathbb{Q}^*\) et \(x\notin\,\mathbb{Q}\).

On suppose par l’absurde que \(a\times \,x\in\,\mathbb{Q}\).

Alors il existe deux entiers relatifs p et q avec \(q\neq\,0\) tels que \(a\times \,x=\,\frac{p}{q}\).

On peut réarranger cette équation pour obtenir \(x=\frac{p}{aq}\), qui est donc un nombre rationnel puisque p, q et a sont des nombres rationnels, ce qui contredit l’hypothèse que \(x\notin\,\mathbb{Q}\).

Donc, \(a\times \,x\notin\,\mathbb{Q}\).

Exercice 6 :

Pour n = 0, on a :

\(\sum_{k=0}^{0}x^k\,=\,x^0\,=\,1\)

et

\(\frac{1-x^{0+1}}{1-x}\,=\,\frac{1-x}{1-x}\,=\,1\)

Donc la formule est vraie pour n = 0.

Supposons maintenant que la formule soit vraie pour un certain entier naturel n quelconque. Nous allons démontrer qu’elle est vraie pour n+1. On a :

\(\sum_{k=0}^{n+1}x^k\,=\,\sum_{k=0}^{n}x^k\,+\,x^{n+1}\)

Par hypothèse de récurrence, on a :

\(\sum_{k=0}^{n}x^k\,=\,\frac{1-x^{n+1}}{1-x}\)

Ainsi,

\(\sum_{k=0}^{n+1}x^k\,=\,\frac{1-x^{n+1}}{1-x}\,+\,x^{n+1}\)

En réduisant au même dénominateur (1-x), on a :

\(\sum_{k=0}^{n+1}x^k\,=\,\frac{1-x^{n+1}+x^{n+1}(1-x)}{1-x}\)

Et donc :

\(\sum_{k=0}^{n+1}x^k\,=\,\frac{1-x^{n+2}}{1-x}\)

Donc la formule est vraie pour tout entier naturel n.

Exercice 7 :

Pour n = 1, on a :

\(\sum_{k=1}^{1}(-1)^kk\,=\,(-1)^1\,\times \,1\,=\,-1\)

et

\(\frac{(-1)^1(2\,\times \,1+1)-1}{4}\,=\,\frac{-3-1}{4}\,=\,-1\)

La formule est donc vraie pour n = 1.

Supposons maintenant que la formule soit vraie pour un certain entier naturel n quelconque. Nous allons démontrer qu’elle est vraie pour n+1. On a :

\(\sum_{k=1}^{n+1}(-1)^kk\,=\,\sum_{k=1}^{n}(-1)^kk\,+\,(-1)^{n+1}(n+1)\)

Par hypothèse de récurrence, on a :

\(\sum_{k=1}^{n}(-1)^kk\,=\,\frac{(-1)^n(2n+1)-1}{4}\)

Donc,

\(\sum_{k=1}^{n+1}(-1)^kk\,=\,\frac{(-1)^n(2n+1)-1}{4}\,+\,(-1)^{n+1}(n+1)\)

En réduisant au même dénominateur 4, on a :

\(\sum_{k=1}^{n+1}(-1)^kk\,=\,\frac{(-1)^n(2n+1)-1+4(-1)^{n+1}(n+1)}{4}\)

Comme \((-1)^n=-(-1)^{n+1}\), le numérateur vaut \((-1)^{n+1}(-2n-1+4n+4)-1=(-1)^{n+1}(2n+3)-1\). On obtient :

\(\sum_{k=1}^{n+1}(-1)^kk\,=\,\frac{(-1)^{n+1}(2(n+1)+1)-1}{4}\)

Donc la formule est vraie pour tout entier naturel n.

Exercice 8 :

Pour n = 0, on a :

\((1+x)^0\,=\,1\,\geq\,\,\,1+0\times \,\,x\,=\,1\)

Donc la formule est vraie pour n = 0.

Supposons maintenant que la formule soit vraie pour un certain entier naturel n quelconque. Nous allons démontrer qu’elle est vraie pour n+1.

On a :

\((1+x)^{n+1}\,=\,(1+x)^n\,\times \,(1+x)\)

Par hypothèse de récurrence, on a :

\((1+x)^n\,\geq\,\,\,1\,+\,nx\)

Donc, en multipliant par \(1+x\), qui est positif :

\((1+x)^{n+1}\,\geq\,\,\,(1+nx)(1+x)\)

En développant le membre de droite, on obtient :

\((1+x)^{n+1}\,\geq\,\,\,1\,+\,(n+1)x\,+\,nx^2\)

Comme x est positif, \(nx^2\) est positif ou nul. On peut donc écrire :

\((1+x)^{n+1}\,\geq\,\,\,1\,+\,(n+1)x\)

La formule est donc vraie pour tout entier naturel n.

Remarque : cette inégalité est appelée inégalité de Bernoulli.

Exercice 9 :

1. La contraposée de la proposition précédente est :

Si l’entier n est impair, alors \(n^2-1\) est divisible par 8.

2. Supposons que n soit impair, c’est-à-dire n = 2k+1 pour un certain entier naturel k.

Alors :

\(n^2-1\,=\,(2k+1)^2-1\,=\,4k^2\,+\,4k\,+\,1\,-\,1\,=\,4(k^2+k)\)

Donc \(n^2-1\) est divisible par 4.

Pour montrer qu’il est divisible par 8, il suffit de remarquer que \(k^2+k\) est pair pour tout entier k.

En effet, pour k pair, on a \(k^2\) pair et k pair donc \(k^2+k\) pair.

Pour k impair, on a \(k^2\) impair et k impair donc \(k^2+k\) pair.

Donc \(k^2+k\) est pair dans tous les cas et \(n^2-1\) est divisible par 8.

Donc la contraposée est vraie.

3. On peut en déduire que si \(n^2-1\) n’est pas divisible par 8, alors n est pair.

En effet, si n était impair, alors d’après la contraposée, \(n^2-1\) serait divisible par 8, ce qui est contraire à l’hypothèse de départ.

Donc si \(n^2-1\) n’est pas divisible par 8, alors n est pair.

Exercice 10 :

1. Nous allons utiliser une démonstration par récurrence.

Vérifions la propriété pour n = 1 :

\(\sum_{k=1}^{1}\,k^3\,=\,1^3\,=\,1\) et \(\frac{1^2\,\times \,(1+1)^2}{4}\,=\,\frac{1\,\times \,4}{4}\,=\,1\)

La propriété est vérifiée au rang 1.

Supposons maintenant que la propriété soit vraie pour un certain entier naturel k, c’est-à-dire :

\(\sum_{i=1}^{k}\,i^3\,=\,\frac{k^2\,(k+1)^2}{4}\)

Prouvons que la propriété est vraie pour k+1 :

\(\sum_{i=1}^{k+1}\,i^3\,=\,\sum_{i=1}^{k}\,i^3\,+\,(k+1)^3\,=\,\frac{k^2\,(k+1)^2}{4}\,+\,(k+1)^3\,=\,\frac{(k+1)^2}{4}\,(k^2\,+\,4k\,+\,4)\,=\,\frac{(k+1)^2\,(k+2)^2}{4}\)

Donc la propriété est vraie pour tout entier naturel n.

2. En utilisant la formule obtenue à la question 1, on peut calculer :

\(A\,=\,1^3\,+\,2^3\,+\,3^3\,+\,…\,+\,10^3\,=\,\sum_{k=1}^{10}\,k^3\,=\,\frac{10^2\,\times \,11^2}{4}\,=\,3025\)

Donc A vaut 3025.

Multiples :

Pour tout entier n, on a :

\(n^3\,-\,n\,=\,n(n^2\,-\,1)\,=\,n(n-1)(n+1)\)

Un produit de trois entiers consécutifs est toujours divisible par 3, car il contient un multiple de 3.

Par conséquent, \(n(n-1)(n+1)\) est toujours divisible par 3, et donc \(n^3\,-\,n\) est un multiple de 3 pour tout entier n.

Exercice 11 :

1. Nous allons utiliser la formule du binôme de Newton (ou le triangle de Pascal : 1, 5, 10, 10, 5, 1) pour développer \((n+1)^5\) :

\((n+1)^5\,=\,n^5\,+\,5n^4\,+\,10n^3\,+\,10n^2\,+\,5n\,+\,1\)

On peut ordonner les termes en partant du terme de plus haut degré (\(n^5\)) et en descendant jusqu’au terme constant (1), ce qui donne :

\((n+1)^5\,=\,n^5\,+\,5n^4\,+\,10n^3\,+\,10n^2\,+\,5n\,+\,1\)

2. Démontrons par récurrence la propriété \(P(n)\) : « \(n^5-n\) est un multiple de 5 ».

Initialisation : pour n = 0, \(0^5-0=0=5\times 0\) est un multiple de 5, donc P(0) est vraie.

Hérédité : supposons que P(n) soit vraie pour un certain entier naturel n, c’est-à-dire qu’il existe un entier p tel que \(n^5-n=5p\). D’après la question 1 :

\((n+1)^5\,-\,(n+1)\,=\,n^5\,+\,5n^4\,+\,10n^3\,+\,10n^2\,+\,5n\,+\,1\,-\,n\,-\,1\,=\,(n^5-n)\,+\,5(n^4+2n^3+2n^2+n)\)

Avec l’hypothèse de récurrence :

\((n+1)^5\,-\,(n+1)\,=\,5p\,+\,5(n^4+2n^3+2n^2+n)\,=\,5(p+n^4+2n^3+2n^2+n)\)

Comme \(p+n^4+2n^3+2n^2+n\) est un entier, \((n+1)^5-(n+1)\) est un multiple de 5 : P(n+1) est vraie.

Conclusion : la propriété est vraie au rang 0 et héréditaire, donc pour tout entier \(n\geq\, 0\), \(n^5-n\) est un multiple de 5.

Exercice 12 :

Nous allons procéder par récurrence.

Vérifions la propriété pour n = 1 :

\(\sum_{k=1}^{1}\,k^3\,=\,1^3\,=\,1\)
\((\sum_{k=1}^{1}\,k)^2\,=\,1^2\,=\,1\)

La propriété est vérifiée au rang 1.

Supposons maintenant que la propriété soit vraie pour un certain entier naturel k, c’est-à-dire :

\(\sum_{i=1}^{k}\,i^3\,=\,(\sum_{i=1}^{k}\,i)^2\)

Prouvons que la propriété est vraie pour k+1 :

\(\sum_{i=1}^{k+1}\,i^3\,=\,\sum_{i=1}^{k}\,i^3\,+\,(k+1)^3\,=\,(\sum_{i=1}^{k}\,i)^2\,+\,(k+1)^3\,=\,(\frac{k(k+1)}{2})^2\,+\,(k+1)^3\,=\,\frac{(k+1)^2(k^2+4k+4)}{4}\,=\,(\frac{(k+1)(k+2)}{2})^2\)

Or \(\frac{(k+1)(k+2)}{2}=\sum_{i=1}^{k+1}i\), donc \(\sum_{i=1}^{k+1}i^3=(\sum_{i=1}^{k+1}i)^2\).

Donc la propriété est vraie pour tout entier naturel n.

Exercice 13 :

1. On ajoute à chaque fois une ligne comportant un point de plus que la ligne la plus longue : \(T_5\) s’obtient en ajoutant une ligne de 5 points à \(T_4\), et \(T_6\) en ajoutant une ligne de 6 points à \(T_5\).

On obtient \(T_5=10+5=15\) et \(T_6=15+6=21\).

2.a) Pour passer de \(T_n\) à \(T_{n+1}\), on ajoute une nouvelle ligne de \(n+1\) points. Donc, pour tout entier \(n\geq\, 1\) : \(T_{n+1}=T_n+n+1\).

b) On calcule les premières valeurs de \(2T_n\) :

\(n\)	1	2	3	4	5	6
\(T_n\)	1	3	6	10	15	21
\(2T_n\)	2	6	12	20	30	42
\(n(n+1)\)	\(1\times 2\)	\(2\times 3\)	\(3\times 4\)	\(4\times 5\)	\(5\times 6\)	\(6\times 7\)

On conjecture que \(2T_n=n(n+1)\), c’est-à-dire \(T_n=\dfrac{n(n+1)}{2}\) pour tout entier \(n\geq\, 1\).

c) Soit \(P(n)\) la propriété : « \(T_n=\dfrac{n(n+1)}{2}\) ».

• Initialisation : \(\dfrac{1\times 2}{2}=1=T_1\), donc \(P(1)\) est vraie.
• Hérédité : supposons \(P(n)\) vraie pour un entier \(n\geq\, 1\). Alors \(T_{n+1}=T_n+n+1=\dfrac{n(n+1)}{2}+\dfrac{2(n+1)}{2}=\dfrac{(n+1)(n+2)}{2}\), ce qui est exactement \(P(n+1)\).
• Conclusion : \(P(1)\) est vraie et la propriété est héréditaire, donc pour tout entier \(n\geq\, 1\), \(T_n=\dfrac{n(n+1)}{2}\).

Exercice 14 :

Soit \(P(n)\) la propriété : « \(OA_n=\sqrt{4n+1}\) ».

Initialisation : \(OA_0=1\) et \(\sqrt{4\times 0+1}=\sqrt{1}=1\), donc \(P(0)\) est vraie.

Hérédité : supposons \(P(n)\) vraie pour un entier naturel n, c’est-à-dire \(OA_n=\sqrt{4n+1}\). D’après la figure, le triangle \(OA_nA_{n+1}\) est rectangle en \(A_n\), d’hypoténuse \([OA_{n+1}]\). D’après le théorème de Pythagore :

\(OA_{n+1}^2=OA_n^2+A_nA_{n+1}^2=(4n+1)+2^2=4n+5=4(n+1)+1\)

Comme une longueur est positive, \(OA_{n+1}=\sqrt{4(n+1)+1}\) : \(P(n+1)\) est vraie.

Conclusion : \(P(0)\) est vraie et la propriété est héréditaire, donc pour tout entier naturel n, \(OA_n=\sqrt{4n+1}\). Par exemple \(OA_1=\sqrt{5}\), \(OA_2=3\) et \(OA_4=\sqrt{17}\).

Exercice 15 :

a) La fonction de Paul part de \(u=7\) puis répète n fois l’instruction \(u arrow 10u-18\) : elle calcule le terme \(u_n\) de la suite définie par \(u_0=7\) et, pour tout entier naturel n, \(u_{n+1}=10u_n-18\) (suite définie par récurrence).

La fonction de Pauline calcule directement \(v_n=5\times 10^n+2\) (suite définie de façon explicite).

Premiers termes : \(u_0=7\), \(u_1=52\), \(u_2=502\), \(u_3=5002\) et \(v_0=7\), \(v_1=52\), \(v_2=502\), \(v_3=5002\).

b) Conjecture : pour tout entier naturel n, \(u_n=v_n\), c’est-à-dire \(u_n=5\times 10^n+2\).

Démonstration par récurrence de \(P(n)\) : « \(u_n=5\times 10^n+2\) ».

• Initialisation : \(u_0=7\) et \(5\times 10^0+2=5+2=7\), donc \(P(0)\) est vraie.
• Hérédité : supposons \(P(n)\) vraie pour un entier naturel n. Alors \(u_{n+1}=10u_n-18=10(5\times 10^n+2)-18=5\times 10^{n+1}+20-18=5\times 10^{n+1}+2\), donc \(P(n+1)\) est vraie.
• Conclusion : pour tout entier naturel n, \(u_n=5\times 10^n+2=v_n\) : les deux programmes affichent toujours la même valeur.

Exercice 16 :

a) Au premier passage dans la boucle (i = 1), u est multiplié par \(\dfrac{2}{2}=1\) : il vaut toujours \(\dfrac{1}{2}\). Ensuite, au passage numéro i, on multiplie la valeur précédente par \(\dfrac{i+1}{2i}\). La suite \((u_n)\) est donc définie par \(u_1=\dfrac{1}{2}\) et, pour tout entier \(n\geq\, 1\), \(u_{n+1}=\dfrac{n+2}{2(n+1)}\,u_n\).

La suite \((v_n)\) est définie de façon explicite par \(v_n=\dfrac{n+1}{2^{n+1}}\) pour tout entier \(n\geq\, 1\).

Le programme affiche « Vrai » ou « Faux » selon que \(u_i=v_i\) ou non, pour i allant de 1 à n.

b) Pour n = 15, le programme affiche 15 fois « Vrai » : les quinze premiers termes des deux suites sont égaux (par exemple \(u_2=v_2=\dfrac{3}{8}\) et \(u_3=v_3=\dfrac{1}{4}\)).

c) Conjecture : pour tout entier \(n\geq\, 1\), \(u_n=v_n=\dfrac{n+1}{2^{n+1}}\).

• Initialisation : \(u_1=\dfrac{1}{2}\) et \(v_1=\dfrac{2}{2^2}=\dfrac{1}{2}\), donc la propriété est vraie au rang 1.
• Hérédité : supposons \(u_n=\dfrac{n+1}{2^{n+1}}\) pour un entier \(n\geq\, 1\). Alors \(u_{n+1}=\dfrac{n+2}{2(n+1)}\times \dfrac{n+1}{2^{n+1}}=\dfrac{n+2}{2^{n+2}}=v_{n+1}\).
• Conclusion : pour tout entier \(n\geq\, 1\), \(u_n=v_n\).

d) Pour n = 30, le programme affiche « Vrai » pour i = 1 à 25, puis « Faux » pour i = 26 à 30, alors que l’on vient de démontrer l’égalité. Cela ne contredit pas la démonstration : l’ordinateur calcule avec des nombres à virgule flottante, en arrondissant chaque résultat. La valeur de u est obtenue par 30 multiplications successives, et les petites erreurs d’arrondi s’accumulent, tandis que v est calculé directement. Les deux valeurs diffèrent alors d’environ \(10^{-23}\) seulement, mais le test u==v exige une égalité exacte : il renvoie donc « Faux ». Un programme ne peut pas remplacer une démonstration.

Exercice 17 :

a) Dans la colonne C, on lit 1, 5, 25, 125, 625, 3125, c’est-à-dire \(5^0\), \(5^1\), \(5^2\), \(5^3\), \(5^4\), \(5^5\). On conjecture que \(u_n+1=5^n\), soit \(u_n=5^n-1\) pour tout entier naturel n.

b) Soit \(P(n)\) la propriété : « \(u_n=5^n-1\) ».

• Initialisation : \(5^0-1=1-1=0=u_0\), donc \(P(0)\) est vraie.
• Hérédité : supposons \(P(n)\) vraie pour un entier naturel n. Alors \(u_{n+1}=4+5u_n=4+5(5^n-1)=4+5^{n+1}-5=5^{n+1}-1\), donc \(P(n+1)\) est vraie.
• Conclusion : \(P(0)\) est vraie et la propriété est héréditaire, donc pour tout entier naturel n, \(u_n=5^n-1\).

Exercice 18 :

1. On calcule les puissances et les carrés :

\(n\)	1	2	3	4	5	6
\(2^n\)	2	4	8	16	32	64
\(n^2\)	1	4	9	16	25	36

2. On a \(2^n>n^2\) pour \(n=1\), puis égalité pour \(n=2\) et \(n=4\), et \(2^n<n^2\) pour \(n=3\). À partir de \(n=5\), l’inégalité est vraie à chaque ligne du tableau. On conjecture : pour tout entier \(n\geq\, 5\), \(2^n>n^2\).

3. Soit \(P(n)\) la propriété : « \(2^n>n^2\) ».

• Initialisation : \(2^5=32>25=5^2\), donc \(P(5)\) est vraie.
• Hérédité : supposons \(P(n)\) vraie pour un entier \(n\geq\, 5\), c’est-à-dire \(2^n>n^2\). En multipliant par 2, \(2^{n+1}>2n^2\). Or \(2n^2-(n+1)^2=n^2-2n-1=(n-1)^2-2\), qui est positif dès que \(n\geq\, 3\) (car \((n-1)^2\geq\, 4\)). Donc, pour \(n\geq\, 5\), \(2n^2\geq\,(n+1)^2\) et \(2^{n+1}>2n^2\geq\,(n+1)^2\) : \(P(n+1)\) est vraie.
• Conclusion : \(P(5)\) est vraie et la propriété est héréditaire, donc pour tout entier \(n\geq\, 5\), \(2^n>n^2\).

4. Soit \(Q(n)\) : « \(2^n>n^3\) ». Initialisation : \(2^{10}=1024>1000=10^3\), donc \(Q(10)\) est vraie.

Hérédité : supposons \(Q(n)\) vraie pour un entier \(n\geq\, 10\). Alors \(2^{n+1}>2n^3\). Or \(2n^3-(n+1)^3=n^3-3n^2-3n-1\). Pour \(n\geq\, 10\), \(n^3\geq\, 10n^2=3n^2+7n^2\geq\, 3n^2+70n\geq\, 3n^2+3n+1\), donc \(2n^3\geq\,(n+1)^3\) et \(2^{n+1}>(n+1)^3\) : \(Q(n+1)\) est vraie.

Conclusion : pour tout entier \(n\geq\, 10\), \(2^n>n^3\).

Exercice 19 :

1. Avec un seul disque, on le déplace directement : \(u_1=1\). Avec deux disques, on déplace le petit sur le piquet intermédiaire, le grand sur le piquet d’arrivée, puis le petit sur le grand : \(u_2=3\).

2. Pour une pile de \(n+1\) disques, la stratégie comporte trois étapes : déplacer les \(n\) disques du haut vers le piquet intermédiaire (\(u_n\) déplacements), déplacer le plus grand disque (1 déplacement), puis replacer les \(n\) disques sur lui (\(u_n\) déplacements). Donc \(u_{n+1}=u_n+1+u_n=2u_n+1\).

3. \(u_3=2\times 3+1=7\) et \(u_4=2\times 7+1=15\). Les valeurs 1, 3, 7, 15 sont les nombres \(2^1-1\), \(2^2-1\), \(2^3-1\), \(2^4-1\). On conjecture : \(u_n=2^n-1\) pour tout entier \(n\geq\, 1\).

4. Soit \(P(n)\) : « \(u_n=2^n-1\) ».

• Initialisation : \(u_1=1=2^1-1\), donc \(P(1)\) est vraie.
• Hérédité : supposons \(P(n)\) vraie pour un entier \(n\geq\, 1\). Alors \(u_{n+1}=2u_n+1=2(2^n-1)+1=2^{n+1}-2+1=2^{n+1}-1\), donc \(P(n+1)\) est vraie.
• Conclusion : pour tout entier \(n\geq\, 1\), \(u_n=2^n-1\).

5. Pour \(n=64\), il faut \(2^{64}-1\approx 1{,}8\times 10^{19}\) déplacements, donc environ \(1{,}8\times 10^{19}\) secondes. Une année contient environ \(3{,}15\times 10^{7}\) secondes, d’où une durée d’environ \(\dfrac{1{,}8\times 10^{19}}{3{,}15\times 10^{7}}\approx 5{,}8\times 10^{11}\) années, soit près de 580 milliards d’années. C’est bien plus que l’âge de l’Univers (environ 14 milliards d’années).

Exercice 20 :

1. D’après la dérivée d’un produit, \(f^{\prime}(x)=1\times e^x+x\,e^x=(x+1)e^x\). Ensuite \(f^{\prime\prime}(x)=e^x+(x+1)e^x=(x+2)e^x\) et \(f^{(3)}(x)=e^x+(x+2)e^x=(x+3)e^x\).

2. On conjecture que \(f^{(n)}(x)=(x+n)e^x\) pour tout entier naturel n et tout réel x.

3. Soit \(P(n)\) la propriété : « pour tout réel x, \(f^{(n)}(x)=(x+n)e^x\) ».

• Initialisation : \(f^{(0)}(x)=f(x)=x\,e^x=(x+0)e^x\), donc \(P(0)\) est vraie.
• Hérédité : supposons \(P(n)\) vraie pour un entier naturel n. En dérivant \(f^{(n)}(x)=(x+n)e^x\), on obtient \(f^{(n+1)}(x)=1\times e^x+(x+n)e^x=(x+n+1)e^x\), donc \(P(n+1)\) est vraie.
• Conclusion : pour tout entier naturel n, \(f^{(n)}(x)=(x+n)e^x\).

4. Avec \(n=10\) et \(x=0\) : \(f^{(10)}(0)=(0+10)e^0=\) 10.