Chargement de l'audio en cours
Plus

Plus

8. Raisonnement par récurrence
P.26-27

Mode édition
Ajouter

Ajouter

Terminer

Terminer

Apprendre à démontrer


8
Raisonnement par récurrence





Principe

Le raisonnement par récurrence ne peut s’utiliser que lorsque l’on cherche à démontrer qu’une proposition est vraie pour tout entier naturel nn supérieur ou égal à un entier naturel n0n_0.

Remarque

En terminale, on a généralement n0=0n_0=0 ou n0=1n_0=1.

Théorème

Soit n0Nn_0 \in \N. On considère la proposition Pn\mathcal{P}_n définie pour tout entier naturel nn0n \geqslant n_{0}.
Si les deux conditions suivantes sont vérifiées :
1. Pn\mathcal{P}_n est vraie pour l’entier n0n_0 ;
2. pour tout entier naturel kn0k \geqslant n_{0}, « Pk\mathcal{P}_k est vraie. » implique « Pk+1\mathcal{P}_{k+1} est vraie. » ; alors on peut conclure que, pour tout nn0n \geqslant n_{0}, la proposition Pn\mathcal{P}_n est vraie.

Remarque

Les étapes du raisonnement par récurrence sont :
  • initialisation ;
  • hypothèse de récurrence ;
  • hérédité ;
  • conclusion.

Énoncé

Démontrer que, pour tout entier naturel nn, n3nn^3 - n est un multiple de 33.

Rédaction détaillée

1. Soit nNn \in \N. On note Pn\mathcal{P}_n la proposition « n3nn^3 - n est un multiple de 33. »

2. Pour n=0n = 0, n3n=030=0=3×0n^{3}-n=0^{3}-0=0=3 \times 0, donc n3nn^3 - n est un multiple de 33.
La proposition P0\mathcal{P}_0 est donc vraie.

3. On considère un entier naturel kk pour lequel Pk\mathcal{P}_k est vraie. Autrement dit, on suppose que k3kk^3 - k est un multiple de 33. Il existe donc un entier relatif qq tel que k3k=3qk^3 - k = 3q. On veut démontrer que Pk+1\mathrm{P}_{k+1} est vraie, autrement dit, que (k+1)3(k+1)(k+1)^{3}-(k+1) est un multiple de 33. On cherche donc qZq' \in \Z tel que (k+1)3(k+1)=3q(k+1)^{3}-(k+1)=3 q^{\prime}.

4. (k+1)3(k+1)(k+1)^{3}-(k+1) =(k+1)(k+1)2k1=(k+1)(k+1)^{2}-k-1
=(k+1)(k2+2k+1)k1=(k+1)\left(k^{2}+2 k+1\right)-k-1
=k3+2k2+k+k2+2k+1k1=k^{3}+2 k^{2}+k+k^{2}+2 k+1-k-1
=k3k+3k2+3k=k^{3}-k+3 k^{2}+3 k

Or, par hypothèse de récurrence, k3k=3qk^3 - k = 3q.
Ainsi, (k+1)3(k+1)=3q+3k2+3k=3(q+k2+k)(k+1)^{3}-(k+1)=3 q+3 k^{2}+3 k=3\left(q+k^{2}+k\right).
On note q=q+k2+kq' = q + k^2 + k. qq' est bien un entier en tant que somme d’entiers. On a ainsi trouvé qZq' \in \Z tel que (k+1)3(k+1)=3q(k+1)^{3}-(k+1)=3 q^{\prime} donc Pk+1\mathcal{P}_{k+1} est vraie.

5. Ainsi, P0\mathcal{P}_0 est vraie et, pour tout entier kk tel que Pk\mathcal{P}_k est vraie, alors Pk+1\mathcal{P}_{k+1} est vraie aussi. Par le principe de récurrence, on en déduit que, pour tout nNn \in \N, Pn\mathcal{P}_n est vraie.
Donc, pour tout nNn \in \N, n3nn^3 - n est un multiple de 33.

Explications

1. On nomme la proposition que l’on souhaite démontrer.

2. Cette étape est l’initialisation : on vérifie que P0\mathcal{P}_0 est vraie en remplaçant nn par 00.

3. On énonce l’hypothèse de récurrence dont on se servira dans la démonstration de l’hérédité.

4. On démontre l’hérédité de la proposition. La plupart du temps, c’est la partie la plus technique du raisonnement par récurrence. L’hypothèse de récurrence doit être utilisée dans l’hérédité. Dans cet exemple, la principale difficulté consiste à traduire l’énoncé « multiple de 33 » en une proposition mathématique. Cela permet de savoir qu’une factorisation par 33 est nécessaire.

5. La conclusion est une étape importante du raisonnement mais rarement difficile à rédiger puisqu’elle reprend notamment l’énoncé de départ.


48

Résoudre l’exercice suivant en complétant la rédaction entamée.

Énoncé : Démontrer par récurrence que, pour tout nNn \in \N, 1+2+3++n=n(n+1)21+2+3+\ldots+n=\dfrac{n(n+1)}{2}.

Démonstration :
1. Soit nNn \in \N. On note Pn\mathcal{P}_n la proposition


2. Soit n=0n = 0.
D’une part,

D’autre part,

On a ainsi montré que
est vraie.

3. On considère
tel que
est vraie ;
autrement dit :

On veut démontrer que
 ;
autrement dit :


4. 1+2+3++n+(n+1)=1+2+3+\ldots+n+(n+1)=



Donc
est vraie.

5. Ainsi,
et

Par le principe de récurrence, on en déduit que
Voir les réponses

49

Soit nNn \in \N. On souhaite démontrer la proposition suivante, notée Pn\mathcal{P}_n :
12+22+32++n2=n(n+1)(2n+1)61^{2}+2^{2}+3^{2}+\ldots+n^{2}=\dfrac{n(n+1)(2 n+1)}{6}.

1. Montrer que P0\mathcal{P}_0 est vraie.


2. Supposons qu’il existe un entier kk tel que Pk\mathcal{P}_k est vraie.
a. Écrire Pk+1\mathcal{P}_{k+1}.


b. Montrer que Pk+1\mathcal{P}_{k+1} est vraie.


3. Conclure.
Voir les réponses

50

Soit a[0 ;1]a \in[0~; 1]. On définit la suite (un)(u_n) par u0=au_0=a et, pour tout nNn \in \N, un+1=3un(1un)u_{n+1}=3 u_{n}\left(1-u_{n}\right).

1. Montrer que, pour tout x[0 ;1]x \in[0~; 1], x(1x)14x(1-x) \leqslant \dfrac{1}{4}.


2. Démontrer que, pour tout nNn \in \N, un[0 ;1]u_{n} \in[0~; 1].
Voir les réponses

51

Soit nNn \in \N. On considère la proposition Pn\mathcal{P}_n : « 10n+110^n + 1 est divisible par 99. »

1. Montrer que s’il existe un entier kk tel que Pk\mathcal{P}_k est vraie, alors Pk+1\mathcal{P}_{k+1} est vraie.


2. Peut‑on en conclure que Pn\mathcal{P}_n est vraie pour tout entier naturel nn ? Justifier.


3. Montrer par récurrence que, pour tout entier naturel nn, 10n110^n - 1 est un multiple de 99.


4. À l’aide d’un raisonnement par l’absurde, montrer que Pn\mathcal{P}_n est fausse pour tout entier naturel nn.
Voir les réponses

52

Soient nn un entier naturel non nul et ff une fonction définie et dérivable sur R\R.

1. Montrer par récurrence que la fonction fn:x(f(x))nf^{n}: x \mapsto(f(x))^{n} est dérivable sur R\R et que, pour tout réel xx, (fn)(x)=nf(x)(f(x))n1\left(f^{n}\right)^{\prime}(x)=n f^{\prime}(x)(f(x))^{n-1}.


2. Application : retrouver la dérivée de la fonction xxnx \mapsto x^{n}, définie et dérivable sur R\R.
Voir les réponses

53

Soient aa et rr deux réels. On considère la suite arithmétique (un)(u_n) de terme initial u0=au_0=a et de raison rr.
Montrer que, pour tout entier naturel nn, un=a+rnu_n=a+rn.
Voir les réponses

54

Soit nNn \in \N. On note Pn\mathcal{P}_n la proposition suivante :
« Pour tout réel xx strictement positif, (1+x)n1+nx.(1+x)^{n} \geqslant 1+n x. »

1. Montrer que cette proposition est vraie pour n=0n = 0.


2. Supposons qu’il existe un entier kk tel que Pk\mathcal{P}_k est vraie. Soit x>0x > 0.
a. Développer (1+kx)(1+x)(1+k x)(1+x).


b. En déduire que Pk+1\mathcal{P}_{k+1} est vraie.


3. Conclure.
Voir les réponses
Voir les réponses

55

Pour un polygone convexe — c’est‑à‑dire un polygone dont tous les angles sont inférieurs à 180 degrés —, on souhaite compter le nombre de diagonales, c’est‑à‑dire le nombre de segments joignant deux sommets non consécutifs de ce polygone.

1. Déterminer le nombre de diagonales d’un triangle, d’un quadrilatère et d’un pentagone convexe.


2. Soit nn un entier naturel supérieur ou égal à 33. On considère la proposition Pn\mathcal{P}_n suivante : « Un polygone convexe à nn côtés possède n(n3)2\dfrac{n(n-3)}{2} diagonales. »
Que peut‑on vérifier d’après la question 1. ?


3. On suppose qu’il existe un entier naturel k3k \geqslant 3 pour lequel Pk\mathcal{P}_k est vraie. On considère P\text{P} un polygone convexe à k+1k + 1 sommets et on note A\text{A} l’un de ses sommets.
a. Combien de diagonales comporte le polygone P\mathrm{P}' composé des k+1k + 1 sommets sauf A\text{A} (donc P\mathrm{P}' possède kk sommets) ?


b. Combien y a‑t‑il de diagonales de P\text{P} partant du point A\text{A} ?


c. En remarquant qu’un des côtés de P\mathrm{P}' est une diagonale de P\text{P}, montrer que Pk+1\mathcal{P}_{k+1} est vraie et conclure.
Voir les réponses
Utilisation des cookies
En poursuivant votre navigation sans modifier vos paramètres, vous acceptez l'utilisation des cookies permettant le bon fonctionnement du service.
Pour plus d’informations, cliquez ici.