Sauter au contenu

Mathématiques discrètes Version préliminaire

Section 5.2 Les preuves par récurrence (par induction)

Si on considère la proposition \(P(n):\, 1+2+\cdots + n =\frac{n(n+1)}{2} .\) Comment peut-on montrer que la proposition \(P(n)\) est vraie pour tout \(n\in\, \N^\ast?\) En remplaçant \(n\) par différentes valeurs, on peut remarquer que la proposition est vraie, mais il est difficile (mais pas impossible) de le montrer directement en utilisant les méthodes utilisées jusqu’à maintenant.
🔗
Une méthode efficace permettant de démontrer ce genre de théorème est ce qu’on appelle une preuve par récurrence. Pour illustrer l’idée, considérons l’exemple suivant.
🔗
On s’imagine une échelle infinie (avec une infinité de barreaux). On se demande jusqu’à quel barreau on peut se rendre si on sait les informations suivantes. Premièrement, on suppose qu’on est en mesure d’atteindre le premier barreau. Ensuite, on suppose que si on est en mesure d’atteindre le \(k\) ième barreau, alors on est également capable d’atteindre le \((k+1)\) ième barreau. Jusqu’où peut-on se rendre?
🔗
Par ce qui précède, on peut conclure qu’on peut se rendre à tous les barreaux de l’échelle! En effet, puisqu’on peut se rendre au premier, on peut se rendre au deuxième. Puisqu’on peut se rendre au deuxième, on peut se rendre au troisième. Puisqu’on peut se rendre au troisième, on peut se rendre au quatrième. Puisqu’on peut se rendre au quatrième... et ainsi de suite.
🔗

Sous-section 5.2.1 Les différentes étapes

Si on garde l’exemple de l’échelle infinie en tête, on remarque qu’il y avait deux parties à notre “argument”. Tout d’abord, on a supposé qu’on pouvait se rendre au premier barreau. C’est l’étape de base.
🔗
Par la suite, on a dit que si on pouvait se rendre au \(k\) ième barreau, alors on pouvait se rendre au \((k+1)\) ième barreau. C’est l’étape d’induction.
🔗

Définition 5.2.1. Preuve par récurrence.

Pour démontrer qu’une proposition \(P(n)\) est vraie pour tout \(n \in\, \N^\ast,\) on peut procéder de la façon suivante.
  1. Étape de base: On montre que \(P(1)\) est vraie.
    🔗
  2. Étape d’induction: On montre que l’implication \(P(k)\rightarrow P(k+1)\) est vraie pour \(k\) un entier positif quelconque, c’est-à-dire que si on suppose \(P(k)\) vraie, alors on montre que \(P(k+1)\) sera vraie également.
    🔗
🔗
À l’étape d’induction, lorsqu’on suppose que \(P(k)\) est vraie, on dit qu’on fait une hypothèse d’induction. On notera souvent H.I. pour indiquer qu’on utilise cette hypothèse.
🔗
🔗

Remarque 5.2.2. Une petite généralisation.

En modifiant l’étape de base de la preuve par induction, on peut montrer qu’une proposition est vraie pour tout entier \(n \geq n_0\text{,}\) où \(n_0\) est un entier quelconque. L’étape de base sera alors de montrer que \(P(n_0)\) est vraie. L’étape d’induction sera alors de montrer que \(P(k)\rightarrow P(k+1)\) est vraie pour tout \(k\geq n_0\text{.}\)
🔗
🔗

Sous-section 5.2.2 Exemples de preuves par récurrence

Regardons maintenant quelques exemples pour illustrer la méthode, en commençant par la formule de la somme des entiers positifs.
🔗

Exemple 5.2.3. La somme des \(n\) premiers entiers positifs.

Montrer par récurrence que, pour \(n\in\,\N^\ast,\) on a \(1+2+\cdots + n = \frac{n(n+1)}{2}.\)
Solution.
On pose \(P(n):\, 1+ 2 + \cdots + n = \frac{n(n+1)}{2}.\)
🔗
Étape de base: On veut montrer que \(P(1)\) est vraie. Tout d’abord on remarque que \(P(1)\) est la proposition \(1=\frac{1(1+1)}{2}\text{.}\) Ceci est clairement vraie, car \(\frac{2}{2}=1.\)
🔗
Étape d’induction: On suppose maintenant que \(P(k)\) est vraie, c’est-à-dire que \(1+2+\cdots + k = \frac{k(k+1)}{2},\) où \(k \geq 1\) est un entier. On veut montrer que \(P(k+1)\) est vraie.
🔗
On remarque que \(P(k+1)\) est la proposition
\begin{equation*} 1+2+\cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}. \end{equation*}
En partant de l’égalité à gauche, on a
\begin{align*} 1+2+\dots + k+(k+1) \amp = \frac{k(k+1)}{2} +(k+1) \text{, par H.I.}\\ \amp= \frac{k(k+1)}{2}+\frac{2(k+1)}{2} = \frac{k(k+1)+2(k+1)}{2}\\ \amp= \frac{(k+1)(k+2)}{2} \end{align*}
🔗
Ainsi, puisqu’on a montré que la proposition est vraie pour \(n=1\text{,}\) et qu’on a montré que si elle est vraie pour \(n=k\text{,}\) alors elle est également vraie pour \(n=k+1\text{,}\) on a montré que la proposition est vraie pour tout \(n\geq 1\text{.}\)
🔗
🔗
🔗

Exemple 5.2.4. Une preuve de divisibilité.

Montrer par récurrence que \(n^3-n\) est divisible par \(3\) pour tout entier naturel \(n\in \N\text{.}\)
Solution.
Étape de base: On montre que la proposition est vraie pour \(n=0\text{.}\) Pour \(n=0\text{,}\) on a \(n^3-n=0^3-0=0.\) Puisque \(3\mid 0\text{,}\) la proposition est bien vraie en \(n=0\text{.}\)
🔗
Étape d’induction: On suppose que \(k^3 -k\) est divisible par \(3\) pour \(k\) un entier naturel quelconque. Ainsi, on peut écrire \(k^3-k=3q,\) pour \(q\in\,\Z.\) On veut montrer que \((k+1)^3-(k+1)\) est divisible par \(3\text{.}\) Or, on a que
🔗
\begin{align*} (k+1)^3 - (k+1) \amp = k^3+ 3k^2 + 3k + 1 - (k+1)\\ \amp= k^3 - k +3(k^2 + k) + 1-1 \\ \amp = (k^3 - k) +3(k^2 + k)\\ \amp = 3q +3(k^2+k) \text{, par H.I.}\\ \amp = 3(q+k^2+k) \end{align*}
Par la fermeture de la somme dans \(\Z,\) on a que \((q+k^2+k)\in\,\Z\text{,}\) et donc \((k+1)^3-(k+1)\) est divisible par \(3\text{.}\)
🔗
Puisque la proposition est vraie pour \(n=0\text{,}\) et que si la proposition est vraie pour \(n=k\text{,}\) elle est aussi vraie pour \(n=k+1,\) alors la proposition est vraie pour tout \(n\in\, \N\text{.}\)
🔗
🔗
🔗

Exemple 5.2.5. Démonstration d’une inégalité.

Montrer par récurrence que pour tout entier naturel \(n\in \N\text{,}\) on a que \(n\lt 2^n\text{.}\)
Solution.
Étape de base: On veut montrer que la proposition est vraie pour \(n=0.\) En \(n=0,\) la proposition devient \(0\lt 2^0=1,\) ce qui est vrai.
🔗
Étape d’induction: On suppose que la proposition est vraie pour \(n=k\) un entier naturel quelconque. Ainsi, on suppose que \(k\lt 2^k.\) On veut montrer qu’elle est vraie pour \(n=k+1\text{,}\) c’est-à-dire que \((k+1)\lt 2^{k+1}\text{.}\)
🔗
On a que
\begin{align*} k+1 \amp \lt 2^k +1 \amp\text{, par H.I.}\\ \amp \leq 2^k+2^k \amp\text{, car } 1\leq 2^k,\\ \amp= 2\cdot 2^k \amp \text{, par mise en évidence} \\ \amp= 2^{k+1}\amp \text{, par les propriétés des exposants} \end{align*}
Ainsi, sous l’H.I., la proposition est également vraie pour \(n=k+1\text{.}\)
🔗
Puisque la proposition est vraie pour \(n=0\text{,}\) et que si la proposition est vraie pour \(n=k\text{,}\) elle est aussi vraie pour \(n=k+1,\) alors la proposition est vraie pour tout \(n\in\, \N\text{.}\)
🔗
🔗
🔗
Lorsqu’on utilise une preuve par récurrence, il faut s’assurer que l’argument utilisé pour l’étape d’induction fonctionne pour toutes les valeurs de \(k\text{.}\) Voici un exemple d’une mauvaise utilisation d’une preuve par récurrence pour “montrer” une proposition qui est fausse.
🔗

Exemple 5.2.6. Erreur commune d’une “preuve” par récurrence.

Trouver l’erreur dans le raisonnement suivant permettant de “montrer” que pour tout ensemble de \(n\geq 2\) droites dans le plan, si aucune n’est parallèle à une autre, alors il existe un point commun à toutes ces droites:
🔗
Étape de base : On doit montrer que la proposition est vraie pour \(n=2.\) Or, si on a deux droites qui ne sont pas parallèles dans le plan, elles ont nécessairement un point en commun.
🔗
Étape d’induction : On suppose que la proposition est vraie pour \(n=k\text{,}\) et on veut montrer qu’elle est vraie pour \(n=k+1,\) pour \(k\) un entier tel que \(k\geq 2\text{.}\)
🔗
On considère un ensemble de \(k+1\) droites dans le plan qui sont deux à deux non-parallèles. Si on regarde les \(k\) premières droites, alors par l’H.I., il existe un point \(p_1\) qui est en commun aux \(k\) premières droites.
🔗
Par le même argument, il existe un point \(p_2\) qui est en commun au \(k\) dernières droites. On veut montrer que \(p_1=p_2\text{.}\)
🔗
Supposons que ces points soient distincts. Alors toutes les \(k-1\) droites contenant ces deux points seront les mêmes droites (car il y a une seule droite passant par deux points dans le plan). Ceci est une contradiction, car ces droites sont distinctes. On doit donc avoir \(p_1=p_2\text{,}\) et donc toutes les \(k+1\) droites possèdent un point en commun.
🔗
Solution.
À l’étape d’induction, l’argument démontrant que \(p_1=p_2\) ne fonctionne pas en \(k=2.\) En effet, si \(k=2,\) alors \(k+1=3,\) et \(p_1\) est un point de la première et de la deuxième droite, alors que \(p_2\) est un point de la deuxième et la troisième droite. Ainsi, seule la deuxième droite contient les points \(p_1\) et \(p_2,\) ce qui n’est pas une contradiction!
🔗
🔗
🔗

Exemple 5.2.7. Une autre “preuve” par récurrence.

Trouver l’erreur dans le raisonnement suivant permettant de “montrer” que toutes les voitures sont de la même couleur:
🔗
On considère \(E_n=\{v_1, v_2, \dots, v_n\}\) un ensemble de \(n\) voitures \(v_i\text{.}\) On pose \(P(n)\) la proposition: Toutes les voitures de l’ensemble \(E_n\) sont de la même couleur.
🔗
Étape de base : On doit montrer que la proposition est vraie pour \(n=1\text{.}\) Or, si \(n=1\text{,}\) \(E_1=\{v_1\}\text{,}\) et on a bien que toutes les voitures sont de la même couleur (celle de \(v_1\)).
🔗
Étape d’induction : On suppose que la proposition est vraie pour tous les ensembles de \(n=k\) voitures, et on veut montrer qu’elle est vraie pour tous les ensembles de \(n=k+1\) voitures, pour \(k\) un entier tel que \(k\geq 1\text{.}\)
🔗
On considère l’ensemble \(E_{k+1}=\{v_1, v_2, \dots, v_{k}, v_{k+1}\}\) formé de \(k+1\) voiture. On a alors que
\begin{equation*} E_{k+1}=\{v_1, v_2, \dots, v_{k}\}\cup \{v_2, \dots, v_{k},v_{k+1}\}. \end{equation*}
Par l’H.I., toutes les voitures de \(\{v_1, v_2, \dots, v_{k}\}\) sont de la même couleur que la voiture \(v_2\text{.}\) De même, toutes les voitures de \(\{v_2, \dots, v_{k}, v_{k+1}\}\) sont de la même couleur que la voiture \(v_2\text{.}\)
🔗
Ainsi, toutes les voitures de \(E_{k+1}\) sont de la même couleur que la voiture \(v_2\text{.}\)
🔗
Solution.
À l’étape d’induction, l’argument démontrant que toutes les voitures sont de la même couleur ne fonctionne pas pour \(k=1\text{.}\) En effet, dans ce cas, \(E_{k+1}=E_2=\{v_1, v_2\}\text{.}\)
🔗
On a encore \(E_2=\{v_1\}\cup \{v_2\}\text{,}\) mais il n’y a pas d’élément en commun dans ces deux ensembles (car \(v_2\notin \{v_1\}\)). L’argument ne fonctionne donc pas à cet étape! La proposition n’est donc pas vraie pour \(n\gt 1\text{.}\)
🔗
🔗
🔗

Exemple 5.2.8. La somme des entiers positifs impairs.

Montrer par récurrence que, pour \(n\in\,\N,\) la somme des \(n\) premiers entiers positifs impairs est \(n^2\)
Solution.
Tout d’abord, on remarque qu’on peut écrire le \(n\)-ième entier positif impair comme \(2n-1\text{.}\) Ainsi, on peut écrire la proposition comme \(P(n):\ 1+3+\cdots + (2n-1) = n^2\text{.}\)
🔗
Étape de base : On veut montrer que la proposition est vraie pour \(n=1\text{.}\) Or, en \(n=1,\) la proposition est \(1=1^2,\) ce qui est vrai.
🔗
Étape d’induction : On suppose que la proposition est vraie pour \(n=k,\) où \(k\) est un entier positif. On veut montrer qu’elle sera alors vraie pour \(n=k+1\text{.}\)
🔗
\begin{align*} 1+3+\cdots +(2k-1) + (2k+1)\amp=k^2 + (2k+1)\text{, par H.I.}\\ \amp = (k+1)^2 \end{align*}
Ainsi, la proposition est vraie pour \(n=k+1\)
🔗
Puisque la proposition est vraie pour \(n=1\text{,}\) et que si la proposition est vraie pour \(n=k\text{,}\) elle est aussi vraie pour \(n=k+1,\) alors la proposition est vraie pour tout \(n\in\, \N^\ast\text{.}\)
🔗
🔗
🔗

Exemple 5.2.9. Une autre preuve de divisibilité.

Montrer par récurrence que pour \(n\) un entier naturel, alors \(7^{n+2}+8^{2n+1}\) est divisible par \(57\text{.}\)
🔗
Solution.
Étape de base: On montre que la proposition est vraie pour \(n=0\text{.}\) Pour \(n=0\text{,}\) on a \(7^{n+2}+8^{2n+1}=49+8=57\text{.}\) Puisque \(57\mid 57\text{,}\) la proposition est bien vraie en \(n=0\text{.}\)
🔗
Étape d’induction: On suppose que \(7^{k+2}+8^{2k+1}\) est divisible par \(57\) pour \(k\) un entier naturel quelconque. Ainsi, on peut écrire \(7^{k+2}+8^{2k+1}=57q,\) pour \(q\in\,\Z.\) On veut montrer que \(7^{k+1+2}+8^{2(k+1)+1}\) est divisible par \(57\text{.}\) Or, on a que
🔗
\begin{align*} 7^{k+1+2}+8^{2(k+1)+1} \amp = 7\cdot 7^{k+2} + 8^2\cdot 8^{2k+1}\\ \amp= 7\cdot 7^{k+2} + 64\cdot 8^{2k+1} \\ \amp= 7\cdot 7^{k+2} + (7+57)\cdot 8^{2k+1} \\ \amp = 7\cdot 7^{k+2} + 7\cdot 8^{2k+1}+57\cdot 8^{2k+1}\\ \amp = 7\cdot (7^{k+2} + \cdot 8^{2k+1} )+57\cdot 8^{2k+1}\\ \amp = 7\cdot (57q )+57\cdot 8^{2k+1} \text{, par H.I.}\\ \amp = 57(7q+8^{2k+1}) \end{align*}
Puisque \(7q+8^{2k+1}\in\,\Z\text{,}\) on a que \(7^{k+1+2}+8^{2(k+1)+1}\) est divisible par \(57\text{.}\)
🔗
Puisque la proposition est vraie pour \(n=0\text{,}\) et que si la proposition est vraie pour \(n=k\text{,}\) elle est aussi vraie pour \(n=k+1,\) alors la proposition est vraie pour tout \(n\in\, \N\text{.}\)
🔗
🔗
🔗
🔗
Les points importants de cette section sont:
🔗

Questions de compréhension de la lecture 5.2.3 Questions de compréhension de la lecture

Ces questions sont à faire avant de venir en classe et à remettre au début du cours.
🔗

1.

Expliquer le principe d’une preuve par récurrence.
🔗
🔗

2.

Soit \(n\in \N\text{,}\) \(n\geq 2\text{,}\) et soit \(A_i\) des ensembles quelconques pour \(i\) allant de \(1\) à \(n\text{.}\) On considère la proposition \(P(n): \left(\bigcup_{i=1}^n A_i \right)^c = \bigcap_{i=1}^n \left(A_i\right)^c\text{.}\)
🔗
Rappel: On a
\begin{equation*} \bigcup_{i=1}^n A_i= A_1\cup A_2\cup \cdots \cup A_n \end{equation*}
et
\begin{equation*} \bigcap_{i=1}^n A_i = A_1\cap A_2\cap \cdots \cap A_n \end{equation*}
🔗
(a)
Faire l’étape de base d’une preuve par récurrence.
🔗
Indice.
L’étape de base est lorsque \(n=2\text{.}\)
🔗
🔗
🔗
(b)
Énoncer l’étape d’induction, sans la faire.
🔗
🔗
🔗

3.

Montrer par récurrence que
\begin{equation*} 1+2+2^2+\cdots + 2^n = 2^{n+1}-1 \end{equation*}
pour \(n\in \N\text{.}\)
🔗
🔗

4.

Noter toute question qui demeure suite à la lecture de la section et la résolution des exercices ci-dessus ou toute précision/clarification à apporter. Note: cette question est facultative.
🔗
🔗
🔗

Exercices 5.2.4 Exercices

À faire en classe.

Ces exercices sont faits pour travailler en classe. Ils servent à approfondir les notions de la section et à atteindre les objectifs d’apprentissage plus avancés.
🔗
1.
(a)
\(9^n-1\) est divisible par \(8\) pour \(n \in \N\text{,}\) c’est-à-dire que \((9^n-1) = 8q\) pour un entier \(q\in \N\text{.}\)
🔗
Solution.
On pose \(P(n)\) la proposition \(9^n-1\) est divisible par \(8\) pour \(n\in\,\N\text{.}\)
🔗
Étape de base: On Doit montrer que \(P(0)\) est vraie. Or, on a que \(9^0-1 =1-1=0\text{,}\) et donc, en \(n=0\text{,}\) la proposition est \(P(0): 0\) est divisible par \(8\text{.}\) Cette proposition est vraie, puisque \(0=8\cdot 0\text{.}\)
🔗
Étape d’induction: On suppose que \(k\) est un entier quelconque \(k\geq 0,\) et que \(P(k)\) est vraie (c’est-à-dire que \(8\cdot q = (9^k-1)\) pour un entier \(q\in \N\) est notre H.I.), on veut alors montrer que \(P(k+1)\) est vraie.
🔗
Ainsi, on veut montrer que
\begin{equation*} 8\cdot q_1 = (9^{k+1}-1), \end{equation*}
pour un entier \(q_1\in \N\text{,}\) à l’aide de l’H.I.
🔗
On part de l’expression \(9^{k+1}-1\text{,}\) et on veut y faire apparaître \(9^{k}-1\text{.}\) On a:
\begin{align*} 9^{k+1}-1 \amp= 9\cdot 9^k - 1 \amp\amp \text{ par les propriétés des exposants.}\\ \amp= (8+1)\cdot 9^k - 1 \amp\amp \\ \amp= 8\cdot 9^k + (9^k -1) \amp\amp \text{ par la distributivité du produit sur la somme.}\\ \amp= 8\cdot 9^k + 8\cdot q \amp\amp\text{ par l'H.I.}\\ \amp= 8\cdot (9^k + q) \amp\amp \text{ mise en évidence du } 8. \\ \amp=8\cdot (q_1) \amp\amp \text{ en posant } q_1 = 9^k+q \in \N. \end{align*}
Ainsi, \(9^{k+1}-1\) est bien divisible par \(8\text{.}\)
🔗
On a montré que \(P(0)\) est vraie, et que si \(P(k)\) est vraie pour un entier \(k\geq 0\text{,}\) alors \(P(k+1)\) est vraie. Ainsi, par le principe d’induction, on a montré que la proposition est vraie pour tout \(n\geq 0\text{.}\)
🔗
🔗
🔗
(b)
\(15^n-1\) est divisible par \(14\) pour \(n \in \N\text{,}\) c’est-à-dire que \((15^n-1) = 14q\) pour un entier \(q\in \N\text{.}\)
🔗
Solution.
On pose \(P(n)\) la proposition \(15^n-1\) est divisible par \(14\) pour \(n\in\,\N\text{.}\)
🔗
Étape de base: On Doit montrer que \(P(0)\) est vraie. Or, on a que \(15^0-1 =1-1=0\text{,}\) et donc, en \(n=0\text{,}\) la proposition est \(P(0): 0\) est divisible par \(14\text{.}\) Cette proposition est vraie, puisque \(0=14\cdot 0\text{.}\)
🔗
Étape d’induction: On suppose que \(k\) est un entier quelconque \(k\geq 0,\) et que \(P(k)\) est vraie (c’est-à-dire que \(14\cdot q = (15^k-1)\) pour un entier \(q\in \N\) est notre H.I.), on veut alors montrer que \(P(k+1)\) est vraie.
🔗
Ainsi, on veut montrer que
\begin{equation*} 14\cdot q_1 = (15^{k+1}-1), \end{equation*}
pour un entier \(q_1\in \N\text{,}\) à l’aide de l’H.I.
🔗
On part de l’expression \(15^{k+1}-1\text{,}\) et on veut y faire apparaître \(15^{k}-1\text{.}\) On a:
\begin{align*} 15^{k+1}-1 \amp= 15\cdot 15^k - 1 \amp\amp \text{ par les propriétés des exposants.}\\ \amp= (14+1)\cdot 15^k - 1 \amp\amp \\ \amp= 14\cdot 15^k + (15^k -1) \amp\amp \text{ par la distributivité du produit sur la somme.}\\ \amp= 14\cdot 15^k + 14\cdot q \amp\amp\text{ par l'H.I.}\\ \amp= 14\cdot (15^k + q) \amp\amp \text{ mise en évidence du } 14. \\ \amp=14\cdot (q_1) \amp\amp \text{ en posant } q_1 = 15^k+q \in \N. \end{align*}
Ainsi, \(15^{k+1}-1\) est bien divisible par \(14\text{.}\)
🔗
On a montré que \(P(0)\) est vraie, et que si \(P(k)\) est vraie pour un entier \(k\geq 0\text{,}\) alors \(P(k+1)\) est vraie. Ainsi, par le principe d’induction, on a montré que la proposition est vraie pour tout \(n\geq 0\text{.}\)
🔗
🔗
🔗
(c)
\(p^n-1\) est divisible par \(p-1\) pour \(n \in \N\text{,}\) c’est-à-dire que \((p^n-1) = (p-1)q\) pour un entier \(q\in \N\text{.}\)
🔗
Solution.
On pose \(P(n)\) la proposition \(p^n-1\) est divisible par \(p-1\) pour \(n\in\,\N\text{.}\)
🔗
Étape de base: On Doit montrer que \(P(0)\) est vraie. Or, on a que \(p^0-1 =1-1=0\text{,}\) et donc, en \(n=0\text{,}\) la proposition est \(P(0): 0\) est divisible par \(p-1\text{.}\) Cette proposition est vraie, puisque \(0=(p-1)\cdot 0\text{.}\)
🔗
Étape d’induction: On suppose que \(k\) est un entier quelconque \(k\geq 0,\) et que \(P(k)\) est vraie (c’est-à-dire que \((p-1)\cdot q = (p^k-1)\) pour un entier \(q\in \N\) est notre H.I.), on veut alors montrer que \(P(k+1)\) est vraie.
🔗
Ainsi, on veut montrer que
\begin{equation*} (p-1)\cdot q_1 = (p^{k+1}-1), \end{equation*}
pour un entier \(q_1\in \N\text{,}\) à l’aide de l’H.I.
🔗
On part de l’expression \(p^{k+1}-1\text{,}\) et on veut y faire apparaître \(p^{k}-1\text{.}\) On a:
\begin{align*} p^{k+1}-1 \amp= p\cdot p^k - 1 \amp\amp \text{ par les propriétés des exposants.}\\ \amp= (p-1+1)\cdot p^k - 1 \amp\amp \\ \amp= (p-1)\cdot p^k + (p^k -1) \amp\amp \text{ par la distributivité du produit sur la somme.}\\ \amp= (p-1)\cdot p^k + (p-1)\cdot q \amp\amp\text{ par l'H.I.}\\ \amp= (p-1)\cdot (p^k + q) \amp\amp \text{ mise en évidence du } (p-1). \\ \amp=(p-1)\cdot (q_1) \amp\amp \text{ en posant } q_1 = p^k+q \in \N. \end{align*}
Ainsi, \(p^{k+1}-1\) est bien divisible par \(p-1\text{.}\)
🔗
On a montré que \(P(0)\) est vraie, et que si \(P(k)\) est vraie pour un entier \(k\geq 0\text{,}\) alors \(P(k+1)\) est vraie. Ainsi, par le principe d’induction, on a montré que la proposition est vraie pour tout \(n\geq 0\text{.}\)
🔗
🔗
🔗
🔗
2.
Montrer par récurrence que pour \(n \geq 1\) un entier, alors \(1^2+2^2+\cdot + n^2=\frac{n(n+1)(2n+1)}{6}\text{.}\)
Solution.
On pose \(P(n)\) la proposition \(1^2+2^2+\cdots + n^2=\frac{n(n+1)(2n+1)}{6}\) pour \(n\in\,\N^\ast\text{.}\)
🔗
Étape de base: On montre que \(P(1)\) est vraie. Or, on a que \(P(1): 1^2 = \frac{(1)(1+1)(2(1)+1)}{6},\) ce qui est vrai, puisque \(1^2=1\) et
\begin{equation*} \frac{(1)(1+1)(2(1)+1)}{6}=\frac{(1)(2)(3)}{6}=1\text{.} \end{equation*}
🔗
Étape d’induction: On suppose que \(k\) est un entier quelconque \(k\geq 1,\) et on veut montrer que \(P(k)\rightarrow P(k+1)\) est vraie. On suppose donc que \(P(k)\) est vraie (c’est-à-dire que \(1^2+2^2+\cdots + k^2=\frac{k(k+1)(2k+1)}{6}\) est notre H.I.), et on veut montrer que \(P(k+1)\) est alors vraie.
🔗
Ainsi, on veut montrer que
\begin{equation*} 1^2+2^2+\cdots + k^2+ (k+1)^2=\frac{(k+1)(k+2)(2k+3)}{6} \end{equation*}
à l’aide de l’H.I. En partant du membre de gauche de l’égalité, on a
\begin{align*} \amp1^2+2^2+\cdot + k^2+ (k+1)^2\\ \amp= \left(1^2+2^2+\cdots + k^2\right) + \left(k+1\right)^2 \\ \amp= \left( \frac{k(k+1)(2k+1)}{6} \right) + \left(k+1\right)^2 \text{ par H.I.}\\ \amp= \left( \frac{k(k+1)(2k+1)}{6} \right) + \frac{6(k+1)(k+1)}{6} \text{ même dénominateur.}\\ \amp= \frac{k(k+1)(2k+1)+6(k+1)(k+1)}{6}\\ \amp=\frac{(k+1)(2k^2+k)+(k+1)(6k+6)}{6} \text{ en distribuant le }k \text{ et le }6.\\ \amp= \frac{(k+1)(2k^2+k+6k+6)}{6}=\frac{(k+1)(2k^2+7k+6)}{6} \\ \amp=\frac{(k+1)(k+2)(2k+3)}{6}\text{ en factorisant.} \end{align*}
🔗
On a montré que \(P(1)\) est vraie, et que si \(P(k)\) est vraie pour un entier \(k\geq 1\text{,}\) alors \(P(k+1)\) est vraie. Ainsi, par le principe d’induction, on a montré que la proposition est vraie pour tout \(n\geq 1\text{.}\)
🔗
🔗
🔗
3.
Montrer par récurrence que si \(n\) est un entier naturel, alors \(1^2+3^2+5^2+\cdots +(2n+1)^2=\frac{(n+1)(2n+1)(2n+3)}{3}\text{.}\)
Solution.
On pose \(P(n)\) la proposition \(1^2+3^2+5^2+\cdots +(2n+1)^2=\frac{(n+1)(2n+1)(2n+3)}{3}\) pour \(n\in\,\N\text{.}\)
🔗
Étape de base: On montre que \(P(0)\) est vraie. Or, on a que \(P(0): 1^2 = \frac{(0+1)(2 (0)+1)(2(1)+3)}{3},\) ce qui est vrai, puisque \(1^2=1\) et
\begin{equation*} \frac{(0+1)(2(0)+1)(2(0)+3)}{3}=\frac{(1)(1)(3)}{3}=1\text{.} \end{equation*}
🔗
Étape d’induction: On suppose que \(k\) est un entier quelconque \(k\geq 0,\) et on suppose que \(P(k)\) est vraie (c’est-à-dire que \(1^2+3^2+\cdots + (2k+1)^2=\frac{(k+1)(2k+1)(2k+3)}{3}\) est notre H.I.), et on veut montrer que \(P(k+1)\) est alors vraie.
🔗
Ainsi, on veut montrer que
\begin{equation*} 1^2+3^2+5^2+\cdots +(2k+1)^2+(2k+3)^2=\frac{(k+2)(2k+3)(2k+5)}{3} \end{equation*}
à l’aide de l’H.I. Tout d’abord, remarquons que \(\frac{(k+2)(2k+3)(2k+5)}{3}=\frac{(2k+3)(2k^2+9k+10)}{3}\text{.}\) Ensuite, en partant du membre de gauche de l’égalité, on a
\begin{align*} \amp1^2+3^2+5^2+\cdots +(2k+1)^2+(2k+3)^2\\ \amp= \left(1^2+3^2+5^2+\cdots +(2k+1)^2\right) + \left(2k+3\right)^2 \\ \amp= \left( \frac{(k+1)(2k+1)(2k+3)}{3}\right) + \left(2k+3\right)^2 \text{ par H.I.}\\ \amp= \left( \frac{(k+1)(2k+1)(2k+3)}{3}\right) + \frac{3(2k+3)(2k+3)}{3} \text{ même dénominateur.}\\ \amp= \frac{(k+1)(2k+1)(2k+3)+3(2k+3)(2k+3)}{3}\\ \amp=\frac{(2k^2+3k+1)(2k+3)+(6k+9)(2k+3)}{3} \text{ en développant le }(k+1)(2k+1) \text{ et en distribuant le }3.\\ \amp= \frac{(2k^2+3k+1+6k+9)(2k+3)}{3}=\frac{(2k^2+9k+10)(2k+3)}{3} \\ \amp=\frac{(k+2)(2k+3)(2k+5)}{3}\text{ par la remarque.} \end{align*}
🔗
On a montré que \(P(0)\) est vraie, et que si \(P(k)\) est vraie pour un entier \(k\geq 0\text{,}\) alors \(P(k+1)\) est vraie. Ainsi, par le principe d’induction, on a montré que la proposition est vraie pour tout \(n\geq 0\text{.}\)
🔗
🔗
🔗
4.
Montrer par récurrence que si \(n\geq 1\) est un entier, alors \(1\cdot 1! +2\cdot 2!+3\cdot 3!+\cdots +n\cdot n!=(n+1)!-1\text{.}\)
Solution.
On pose \(P(n)\) la proposition \(1\cdot 1! +2\cdot 2!+3\cdot 3!+\cdots +n\cdot n!=(n+1)!-1\) pour \(n\in\,\N^\ast\text{.}\)
🔗
Étape de base: On montre que \(P(1)\) est vraie. Or, on a que \(P(1): 1\cdot 1! = (1+1)!-1,\) ce qui est vrai, puisque \(1\cdot 1!=1\) et
\begin{equation*} (1+1)!-1=2!-1=1\text{.} \end{equation*}
🔗
Étape d’induction: On suppose que \(k\) est un entier quelconque \(k\geq 1,\) et on suppose que \(P(k)\) est vraie (c’est-à-dire que \(1\cdot 1! +2\cdot 2!+3\cdot 3!+\cdots +n\cdot k!=(k+1)!-1\) est notre H.I.), et on veut montrer que \(P(k+1)\) est alors vraie.
🔗
Ainsi, on veut montrer que
\begin{equation*} 1\cdot 1! +2\cdot 2!+3\cdot 3!+\cdots +k\cdot k!+(k+1)(k+1)!=(k+2)!-1 \end{equation*}
à l’aide de l’H.I. En partant du membre de gauche de l’égalité, on a
\begin{align*} \amp 1\cdot 1! +2\cdot 2!+3\cdot 3!+\cdots +k\cdot k!+(k+1)(k+1)!\\ \amp= \left(1\cdot 1! +2\cdot 2!+3\cdot 3!+\cdots +k\cdot k!\right) +(k+1)(k+1)! \\ \amp= \left( (k+1)!-1\right) + (k+1)(k+1)! \text{ par H.I.}\\ \amp=(k+1)! + (k+1)(k+1)! -1\\ \amp=(1+k+1)(k+1)! -1\text{ (mise en évidence)}\\ \amp=(k+2)(k+1)! -1\\ \amp=(k+2)! -1\text{ (par la définition de la factorielle.)} \end{align*}
🔗
On a montré que \(P(1)\) est vraie, et que si \(P(k)\) est vraie pour un entier \(k\geq 1\text{,}\) alors \(P(k+1)\) est vraie. Ainsi, par le principe d’induction, on a montré que la proposition est vraie pour tout \(n\geq 1\text{.}\)
🔗
🔗
🔗
5.
Montrer par récurrence que si \(n\geq 1\) est un entier, alors \(\frac{1}{2} +\frac{1}{4}+\frac{1}{8}+\cdots +\frac{1}{2^n}=1-\frac{1}{2^n}\)
Solution.
On pose \(P(n)\) la proposition \(\frac{1}{2} +\frac{1}{4}+\frac{1}{8}+\cdots +\frac{1}{2^n}=1-\frac{1}{2^n}\) pour \(n\in\,\N^\ast\text{.}\)
🔗
Étape de base: On montre que \(P(1)\) est vraie. Or, on a que \(P(1): \frac{1}{2} = 1-\frac{1}{2},\) ce qui est vrai, puisque
\begin{equation*} 1-\frac{1}{2}=\frac{1}{2}\text{.} \end{equation*}
🔗
Étape d’induction: On suppose que \(k\) est un entier quelconque \(k\geq 1,\) et on suppose que \(P(k)\) est vraie (c’est-à-dire que \(\frac{1}{2} +\frac{1}{4}+\frac{1}{8}+\cdots +\frac{1}{2^k}=1-\frac{1}{2^k}\) est notre H.I.), et on veut montrer que \(P(k+1)\) est alors vraie.
🔗
Ainsi, on veut montrer que
\begin{equation*} \frac{1}{2} +\frac{1}{4}+\frac{1}{8}+\cdots +\frac{1}{2^k}+\frac{1}{2^{k+1}}=1-\frac{1}{2^{k+1}} \end{equation*}
à l’aide de l’H.I. En partant du membre de gauche de l’égalité, on a
\begin{align*} \amp\frac{1}{2} +\frac{1}{4}+\frac{1}{8}+\cdots +\frac{1}{2^k}+\frac{1}{2^{k+1}}\\ \amp= \left(\frac{1}{2} +\frac{1}{4}+\frac{1}{8}+\cdots +\frac{1}{2^k}\right) +\frac{1}{2^{k+1}}\\ \amp= \left(1-\frac{1}{2^k}\right)+ \frac{1}{2^{k+1}} \text{ par H.I.}\\ \amp=1-\frac{2}{2^{k+1}}+ \frac{1}{2^{k+1}}\text{ (même dénominateur)}\\ \amp=1-\frac{1}{2^{k+1}} \end{align*}
🔗
On a montré que \(P(1)\) est vraie, et que si \(P(k)\) est vraie pour un entier \(k\geq 1\text{,}\) alors \(P(k+1)\) est vraie. Ainsi, par le principe d’induction, on a montré que la proposition est vraie pour tout \(n\geq 1\text{.}\)
🔗
🔗
🔗
6.
Soit \(A\) un ensemble de cardinalité \(n\in \N\text{,}\) c’est-à-dire que \(|A|=n\text{.}\) Montrer par récurrence que le nombre de sous-ensembles de \(A\) est \(2^n\text{.}\)
🔗
Solution.
On pose \(P(n)\) la proposition si \(|A|=n\text{,}\) alors \(|\mathscr{P}(A)|= 2^n\text{.}\)
🔗
Étape de base: On montre que \(P(0)\) est vraie. Or, si \(|A|=n=0\text{,}\) alors \(\mathscr{P}(A)=\{\emptyset\}\) et \(|\{\emptyset\}|=1=2^0\text{.}\)
🔗
Étape d’induction: On suppose que \(k\) est un entier quelconque \(k\geq 0,\) et on suppose que \(P(k)\) est vraie (c’est-à-dire que notre H.I. est que pour tout ensemble \(E\) tel que \(|E|=k\text{,}\) alors \(|\mathscr{P}(E)|=2^k\)), et on veut montrer que \(P(k+1)\) est alors vraie.
🔗
Ainsi, on veut montrer que si \(|A|=k+1\text{,}\) alors \(|\mathscr{P}(A)|=2^{k+1}\)
🔗
On note \(A=\{a_1,a_2,\dots , a_k, a_{k+1}\}\) et \(E=\{a_1,a_2,\dots , a_k\}\text{.}\) Ansi, on a que \(A=E\cup \{a_{k+1}\}\text{.}\)
🔗
On sépare la tâche de choisir un sous-ensemble \(X\) de \(A\) en deux étapes. Premièrement, on choisit un sous-ensemble de \(E\) et ensuite on choisit si \(a_{k+1}\in X\) ou si \(a_{k+1}\notin X\text{.}\) Par l’H.I., il y a \(2^k\) sous-ensemble de \(E\text{,}\) et il y a \(2\) choix pour décider si \(a_{k+1}\in X\text{.}\)
🔗
Par le principe du produit, on a \(2^k\cdot 2=2^{k+1}\) façons de choisir \(X\text{.}\) On a donc bien que \(|\mathscr{P}(A)|=2^{k+1}\text{.}\)
🔗
On a montré que \(P(0)\) est vraie, et que si \(P(k)\) est vraie pour un entier \(k\geq 0\text{,}\) alors \(P(k+1)\) est vraie. Ainsi, par le principe d’induction, on a montré que la proposition est vraie pour tout \(n\geq 0\text{.}\)
🔗
🔗
🔗
7.
Montrer par récurrence que \(3^n\lt n!\) si \(n\) est un entier plus grand que \(6\text{.}\)
Solution.
On pose \(P(n)\) la proposition \(3^n\lt n!\) pour \(n\in\,\N\) et \(n\geq 7\text{.}\)
🔗
Étape de base: On montre que \(P(7)\) est vraie. Or, on a que \(P(7): 3^7 \lt 7!,\) ce qui est vrai, puisque
\begin{equation*} 3^7=2187\lt 5040=7!\text{.} \end{equation*}
🔗
Étape d’induction: On suppose que \(k\) est un entier quelconque \(k\geq 7,\) et on suppose que \(P(k)\) est vraie (c’est-à-dire que \(3^k \lt k!,\) est notre H.I.), et on veut montrer que \(P(k+1)\) est alors vraie.
🔗
Ainsi, on veut montrer que
\begin{equation*} 3^{k+1}\lt (k+1)! \end{equation*}
à l’aide de l’H.I. En partant du membre de gauche de l’inégalité, on a
\begin{align*} \amp3^{k+1}= 3\left(3^k\right)\\ \amp\lt 3\left(k!\right) \text{ par H.I.}\\ \amp\lt (k+1)k!\text{ car } k+1 \geq 8\gt 3.\\ \amp=(k+1)! \end{align*}
c’est-à-dire que \(3^{k+1}\lt (k+1)! \text{.}\)
🔗
On a montré que \(P(7)\) est vraie, et que si \(P(k)\) est vraie pour un entier \(k\geq 7\text{,}\) alors \(P(k+1)\) est vraie. Ainsi, par le principe d’induction, on a montré que la proposition est vraie pour tout \(n\geq 7\text{.}\)
🔗
🔗
🔗
8.
Montrer par récurrence que \(2^n\gt n^2\) si \(n\) est un entier plus grand que \(4\text{.}\)
Solution.
On pose \(P(n)\) la proposition \(2^n\gt n^2\) pour \(n\in\,\N\) et \(n\geq 5\text{.}\)
🔗
Étape de base: On montre que \(P(5)\) est vraie. Or, on a que \(P(7): 2^5\gt 5^2,\) ce qui est vrai, puisque
\begin{equation*} 2^5=32\gt 25=5^2\text{.} \end{equation*}
🔗
Étape d’induction: On suppose que \(k\) est un entier quelconque \(k\geq 5,\) et on suppose que \(P(k)\) est vraie (c’est-à-dire que \(2^k \gt k^2,\) est notre H.I.), et on veut montrer que \(P(k+1)\) est alors vraie.
🔗
Ainsi, on veut montrer que
\begin{equation*} 2^{k+1}\gt (k+1)^2 \end{equation*}
à l’aide de l’H.I. En partant du membre de gauche de l’inégalité, on a
\begin{align*} \amp2^{k+1}= 2\left(2^k\right)\\ \amp\gt 2\left(k^2\right) \text{ par H.I.}\\ \amp= k^2+k^2=k^2+k\cdot k\\ \amp\gt k^2 + 3k \text{ car } k\geq 5\gt 3\\ \amp= k^2 + 2k +k \\ \amp\gt k^2 + 2k +1 \text{ car } k\geq 5\gt 1 \\ \amp= (k+1)^2 \text{(factorisation)} \end{align*}
c’est-à-dire que \(2^{k+1}\gt (k+1)^2 \text{.}\)
🔗
On a montré que \(P(5)\) est vraie, et que si \(P(k)\) est vraie pour un entier \(k\geq 5\text{,}\) alors \(P(k+1)\) est vraie. Ainsi, par le principe d’induction, on a montré que la proposition est vraie pour tout \(n\geq 5\text{.}\)
🔗
🔗
🔗
9.
\begin{equation*} S(n)=\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\cdots + \frac{1}{n\cdot (n+1)}\text{.} \end{equation*}
(a)
En remplaçant \(n\) par certaines valeurs, trouver une formule pour l’expression de \(S(n)\text{.}\)
🔗
Indice.
Remarquer que \(S(1)=\frac{1}{2},\) \(S(2)=\frac{2}{3},\) \(S(3)=\frac{3}{4}\) et \(S(4)=\frac{4}{5}.\)
🔗
🔗
Réponse.
\(S(n)=\frac{n}{n+1}\)
🔗
🔗
(b)
Montrer par récurrence que votre formule est bonne.
🔗
Solution.
On pose \(P(n)\) la proposition \(S(n)=\frac{n}{n+1}\) pour \(n\in\,\N^\ast\text{.}\)
🔗
Étape de base: On montre que \(P(1)\) est vraie. Or, on a que \(P(1): S(1)= \frac{1}{1+1},\) ce qui est vrai, puisque
\begin{equation*} S(1)= \frac{1}{1\cdot 2}=\frac{1}{2}=\frac{1}{1+1}\text{.} \end{equation*}
🔗
Étape d’induction: On suppose que \(k\) est un entier quelconque \(k\geq 1,\) et on suppose que \(P(k)\) est vraie (c’est-à-dire que \(S(k)=\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\cdots + \frac{1}{k\cdot (k+1)}=\frac{k}{k+1}\) est notre H.I.), et on veut montrer que \(P(k+1)\) est alors vraie.
🔗
Ainsi, on veut montrer que
\begin{equation*} S(k+1)=\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\cdots + \frac{1}{k\cdot (k+1)} +\frac{1}{(k+1)\cdot (k+2)}=\frac{k+1}{k+2} \end{equation*}
à l’aide de l’H.I. En partant du membre de gauche de l’égalité, on a
\begin{align*} \amp S(k+1)=\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\cdots + \frac{1}{k\cdot (k+1)} +\frac{1}{(k+1)(k+2)}\\ \amp= \left(\frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\cdots + \frac{1}{k\cdot (k+1)} \right) +\frac{1}{(k+1)\cdot (k+2)}\\ \amp= \frac{k}{k+1} +\frac{1}{(k+1)(k+2)} \text{ par H.I.}\\ \amp=\frac{k(k+2)}{(k+1)(k+2)} + \frac{1}{(k+1)(k+2)}\text{ (même dénominateur)}\\ \amp=\frac{k(k+2)+1}{(k+1)(k+2)}=\frac{k^2+2k+1}{(k+1)(k+2)}\\ \amp=\frac{(k+1)^2}{(k+1)(k+2)}=\frac{k+1}{k+2} \end{align*}
🔗
On a montré que \(P(1)\) est vraie, et que si \(P(k)\) est vraie pour un entier \(k\geq 1\text{,}\) alors \(P(k+1)\) est vraie. Ainsi, par le principe d’induction, on a montré que la proposition est vraie pour tout \(n\geq 1\text{.}\)
🔗
🔗
🔗
🔗
10.
On considère l’expression
\begin{equation*} H(n)=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots + \frac{1}{2^n}. \end{equation*}
pour \(n\) un entier naturel.
🔗
Montrer par récurrence que \(H(n)\geq 1+\frac{n}{2}\)
🔗
Solution.
On pose \(P(n)\) la proposition \(H(n) \geq 1+\frac{n}{2}\) pour \(n\in\,\N\text{.}\)
🔗
Étape de base: On montre que \(P(0)\) est vraie. Or, on a que \(P(0): 1\geq 1+\frac{0}{2},\) ce qui est vrai, puisque
\begin{equation*} 1\geq 1 =1+\frac{0}{2}\text{.} \end{equation*}
🔗
Étape d’induction: On suppose que \(k\) est un entier quelconque \(k\geq 0,\) et on suppose que \(P(k)\) est vraie (c’est-à-dire que \(H(k) \geq 1+\frac{k}{2},\) est notre H.I.), et on veut montrer que \(P(k+1)\) est alors vraie.
🔗
Ainsi, on veut montrer que
\begin{equation*} H(k+1) =1+\frac{1}{2}+\frac{1}{3}+\cdots + \frac{1}{2^k}+\frac{1}{2^k+1}+\frac{1}{2^k+2}+\cdots +\frac{1}{2^{k+1}}\geq 1+\frac{k+1}{2} \end{equation*}
à l’aide de l’H.I. En partant du membre de gauche de l’inégalité, on a
\begin{align*} \amp H(k+1) =1+\frac{1}{2}+\frac{1}{3}+\cdots + \frac{1}{2^k}+\frac{1}{2^k+1}+\frac{1}{2^k+2}+\cdots+\frac{1}{2^{k+1}}\\ \amp= \left(1+\frac{1}{2}+\frac{1}{3}+\cdots + \frac{1}{2^k}\right)+ \frac{1}{2^k+1}+\frac{1}{2^k+2}+\cdots+\frac{1}{2^{k+1}}\\ \amp\geq \left(1+\frac{k}{2}\right)+ \frac{1}{2^k+1}+\frac{1}{2^k+2}+\cdots+\frac{1}{2^{k+1}}\text{ par H.I.}\\ \amp\geq \left(1+\frac{k}{2}\right)+ \frac{1}{2^{k+1}}+\frac{1}{2^{k+1}}+\cdots+\frac{1}{2^{k+1}} \text{ car } \frac{1}{2^k + i} \geq \frac{1}{2^{k+1}} \text{ pour } 1\leq i \leq 2^k\\ \amp= 1+\frac{k2^{k}}{2^{k+1}}+ \frac{2^k}{2^{k+1}} \text{ en mettant sur le même dénominateur, et car il y a } 2^k \text{ termes dans la somme à droite.}\\ \amp= 1+\frac{k2^{k}+2^k}{2^{k+1}}\\ \amp= 1+\frac{(k+1)2^{k}}{2^{k+1}} \\ \amp= 1+\frac{k+1}{2} \end{align*}
c’est-à-dire que \(H({k+1})\geq 1+\frac{k+1}{2}\text{.}\)
🔗
On a montré que \(P(0)\) est vraie, et que si \(P(k)\) est vraie pour un entier \(k\geq 0\text{,}\) alors \(P(k+1)\) est vraie. Ainsi, par le principe d’induction, on a montré que la proposition est vraie pour tout \(n\geq 0\text{.}\)
🔗
🔗
🔗
🔗
🔗
🔗
PrécédentTopSuivant