Exercice 1: Démontrer par récurrence que pour tout entier naturel $n \ge 1$, la somme des $n$ premiers entiers est donnée par $1 + 2 + ... + n = \frac{n(n+1)}{2}$. (Répondre par 'oui' après avoir compris la démarche)
1. Initialisation (n=1): Pour $n=1$, la somme est $1$. La formule donne $\frac{1(1+1)}{2} = \frac{2}{2} = 1$. La propriété est vraie pour $n=1$. 2. Hérédité: Supposons que la propriété soit vraie pour un entier $k \ge 1$, c'est-à-dire $1 + 2 + ... + k = \frac{k(k+1)}{2}$ (Hypothèse de récurrence). Montrons que la propriété est vraie pour $k+1$, c'est-à-dire $1 + 2 + ... + (k+1) = \frac{(k+1)(k+2)}{2}$. $1 + 2 + ... + k + (k+1) = (1 + 2 + ... + k) + (k+1)$ D'après l'hypothèse de récurrence : $= \frac{k(k+1)}{2} + (k+1)$ $= (k+1) (\frac{k}{2} + 1)$ $= (k+1) (\frac{k+2}{2})$ $= \frac{(k+1)(k+2)}{2}$. La propriété est donc héréditaire. 3. Conclusion: Puisque la propriété est vraie pour $n=1$ et qu'elle est héréditaire, elle est vraie pour tout entier naturel $n \ge 1$ par le principe de récurrence.
Exercice 2: Démontrer par récurrence que pour tout entier naturel $n \ge 1$, la somme des $n$ premiers nombres impairs est donnée par $1 + 3 + 5 + ... + (2n-1) = n^2$. (Répondre par 'oui' après avoir compris la démarche)
1. Initialisation (n=1): Pour $n=1$, le premier nombre impair est $1$. La formule donne $1^2 = 1$. La propriété est vraie pour $n=1$. 2. Hérédité: Supposons que la propriété soit vraie pour un entier $k \ge 1$, c'est-à-dire $1 + 3 + ... + (2k-1) = k^2$ (Hypothèse de récurrence). Montrons que la propriété est vraie pour $k+1$, c'est-à-dire $1 + 3 + ... + (2(k+1)-1) = (k+1)^2$. $1 + 3 + ... + (2k-1) + (2(k+1)-1) = (1 + 3 + ... + (2k-1)) + (2k+2-1)$ $= (1 + 3 + ... + (2k-1)) + (2k+1)$ D'après l'hypothèse de récurrence : $= k^2 + (2k+1)$ $= k^2 + 2k + 1$ $= (k+1)^2$. La propriété est donc héréditaire. 3. Conclusion: Puisque la propriété est vraie pour $n=1$ et qu'elle est héréditaire, elle est vraie pour tout entier naturel $n \ge 1$ par le principe de récurrence.
Exercice 3: Démontrer par récurrence que pour tout entier naturel $n \ge 2$, l'inégalité $2^n > n+1$ est vraie. (Répondre par 'oui' après avoir compris la démarche)
1. Initialisation (n=2): Pour $n=2$, $2^2 = 4$ et $n+1 = 2+1 = 3$. On a $4 > 3$, donc la propriété est vraie pour $n=2$. 2. Hérédité: Supposons que la propriété soit vraie pour un entier $k \ge 2$, c'est-à-dire $2^k > k+1$ (Hypothèse de récurrence). Montrons que la propriété est vraie pour $k+1$, c'est-à-dire $2^{k+1} > (k+1)+1 = k+2$. D'après l'hypothèse de récurrence, $2^k > k+1$. Multiplions les deux côtés par 2 : $2 \cdot 2^k > 2(k+1)$ $2^{k+1} > 2k+2$. Nous voulons montrer $2^{k+1} > k+2$. Il suffit de montrer que $2k+2 \ge k+2$, ce qui est équivalent à $k \ge 0$. Puisque $k \ge 2$, l'inégalité $k \ge 0$ est vraie. Donc $2^{k+1} > 2k+2 \ge k+2$, ce qui implique $2^{k+1} > k+2$. La propriété est donc héréditaire. 3. Conclusion: Puisque la propriété est vraie pour $n=2$ et qu'elle est héréditaire, elle est vraie pour tout entier naturel $n \ge 2$ par le principe de récurrence.
Exercice 4: Démontrer par récurrence que pour tout entier naturel $n \ge 0$, le nombre $3^{2n} - 1$ est divisible par 8. (Répondre par 'oui' après avoir compris la démarche)
1. Initialisation (n=0): Pour $n=0$, $3^{2 \cdot 0} - 1 = 3^0 - 1 = 1 - 1 = 0$. $0$ est divisible par 8 ($0 = 8 \cdot 0$). La propriété est vraie pour $n=0$. 2. Hérédité: Supposons que la propriété soit vraie pour un entier $k \ge 0$, c'est-à-dire $3^{2k} - 1$ est divisible par 8. Cela signifie que $3^{2k} - 1 = 8m$ pour un certain entier $m$ (Hypothèse de récurrence). Montrons que la propriété est vraie pour $k+1$, c'est-à-dire $3^{2(k+1)} - 1$ est divisible par 8. $3^{2(k+1)} - 1 = 3^{2k+2} - 1 = 3^{2k} \cdot 3^2 - 1 = 9 \cdot 3^{2k} - 1$. D'après l'hypothèse de récurrence, $3^{2k} = 8m + 1$. $9 \cdot (8m + 1) - 1 = 72m + 9 - 1 = 72m + 8 = 8(9m + 1)$. Puisque $9m+1$ est un entier, $3^{2(k+1)} - 1$ est divisible par 8. La propriété est donc héréditaire. 3. Conclusion: Puisque la propriété est vraie pour $n=0$ et qu'elle est héréditaire, elle est vraie pour tout entier naturel $n \ge 0$ par le principe de récurrence.
Exercice 5: Démontrer par récurrence que pour tout entier naturel $n \ge 1$, la somme $1 + 2 + ... + n = n^2$ est vraie. (Répondre par 'oui' ou 'non')
1. Initialisation (n=1): Pour $n=1$, la somme est $1$. La formule donne $1^2 = 1$. La propriété est vraie pour $n=1$. 2. Test pour n=2: Pour $n=2$, la somme est $1 + 2 = 3$. La formule donne $2^2 = 4$. Puisque $3 \ne 4$, la propriété est fausse pour $n=2$. Il n'est donc pas possible de démontrer cette propriété par récurrence, car elle n'est pas toujours vraie. L'initialisation peut être correcte par hasard, mais l'hérédité ou un autre terme la rendra fausse.
Exercice 6: Démontrer par récurrence que pour tout entier naturel $n \ge 1$, l'inégalité $n^2 + 1 \le 2n$ est vraie. (Répondre par 'oui' ou 'non')
1. Initialisation (n=1): Pour $n=1$, $1^2 + 1 = 2$ et $2n = 2(1) = 2$. On a $2 \le 2$, donc la propriété est vraie pour $n=1$. 2. Test pour n=2: Pour $n=2$, $2^2 + 1 = 5$ et $2n = 2(2) = 4$. On a $5 \not\le 4$. Puisque la propriété est fausse pour $n=2$, elle ne peut pas être démontrée par récurrence pour tout $n \ge 1$. L'initialisation est correcte, mais l'hérédité ne tiendrait pas, ou la propriété est fausse dès $n=2$.
Exercice 7: Démontrer par récurrence que pour tout entier naturel $n \ge 1$, le produit $\prod_{k=1}^{n} (1 + \frac{1}{k}) = n+1$ est vrai. (Répondre par 'oui' après avoir compris la démarche)
1. Initialisation (n=1): Pour $n=1$, le produit est $(1 + \frac{1}{1}) = 2$. La formule donne $1+1 = 2$. La propriété est vraie pour $n=1$. 2. Hérédité: Supposons que la propriété soit vraie pour un entier $k \ge 1$, c'est-à-dire $\prod_{i=1}^{k} (1 + \frac{1}{i}) = k+1$ (Hypothèse de récurrence). Montrons que la propriété est vraie pour $k+1$, c'est-à-dire $\prod_{i=1}^{k+1} (1 + \frac{1}{i}) = (k+1)+1 = k+2$. $\prod_{i=1}^{k+1} (1 + \frac{1}{i}) = \left( \prod_{i=1}^{k} (1 + \frac{1}{i}) \right) \cdot (1 + \frac{1}{k+1})$ D'après l'hypothèse de récurrence : $= (k+1) \cdot (1 + \frac{1}{k+1})$ $= (k+1) \cdot (\frac{k+1+1}{k+1})$ $= (k+1) \cdot (\frac{k+2}{k+1})$ $= k+2$. La propriété est donc héréditaire. 3. Conclusion: Puisque la propriété est vraie pour $n=1$ et qu'elle est héréditaire, elle est vraie pour tout entier naturel $n \ge 1$ par le principe de récurrence.