Raisonnement par récurrence — Exercices

Somme, inégalité, divisibilité, suite bornée. Corrigé ci-dessous.

⏱ ~35 min✎ Calculatrice inutile

1Somme géométrique/ 4 pts

Démontrer par récurrence que, pour tout entier $n \in \mathbb{N}$ :

$\displaystyle\sum_{k=0}^{n} 2^k = 2^{n+1} - 1$

2Inégalité/ 4 pts

Démontrer par récurrence que, pour tout entier $n \geq 1$ :

$2^n \geq n + 1$

3Divisibilité/ 4 pts

Démontrer par récurrence que, pour tout entier $n \in \mathbb{N}$ :

$7^n - 1$ est divisible par $6$

4Suite bornée/ 5 pts

Soit $(u_n)$ la suite définie par $u_0 = 3$ et $u_{n+1} = \dfrac{u_n + 1}{2}$ pour tout $n \in \mathbb{N}$.

Calculer $u_1$ et $u_2$.
Démontrer par récurrence que, pour tout $n \in \mathbb{N}$, $1 \lt u_n \leq 3$.

Corrigé détaillé

1Somme géométrique

Init. (n = 0) $\sum_{k=0}^{0} 2^k = 2^0 = 1 \quad\text{et}\quad 2^{0+1}-1 = 2-1 = 1$ $P(0) \text{ vraie.}$

HR $\text{Soit } n \in \mathbb{N}\text{. On suppose }\displaystyle\sum_{k=0}^{n} 2^k = 2^{n+1}-1.$ $\text{On montre }\displaystyle\sum_{k=0}^{n+1} 2^k = 2^{n+2}-1.$

P(n+1) $\sum_{k=0}^{n+1} 2^k = \sum_{k=0}^{n} 2^k + 2^{n+1} = (2^{n+1}-1) + 2^{n+1} = 2 \cdot 2^{n+1} - 1 =$ $2^{n+2}-1$

Concl. $P(0) \text{ vraie et hérédité établie} \Rightarrow$ $\forall n \in \mathbb{N},\;\sum_{k=0}^{n} 2^k = 2^{n+1}-1$

2Inégalité

Init. (n = 1) $2^1 = 2 \quad\text{et}\quad 1+1 = 2 \quad\Rightarrow\quad 2 \geq 2$ $P(1) \text{ vraie.}$

HR $\text{Soit } n \geq 1\text{. On suppose } 2^n \geq n+1.$ $\text{On montre } 2^{n+1} \geq n+2.$

P(n+1) $2^{n+1} = 2 \cdot 2^n \geq 2(n+1) = 2n+2$ $\geq n+2 \quad(\text{car } n \geq 0)$

Concl. $\text{Donc }2^{n+1} \geq (n+1)+1 \Rightarrow$ $\forall n \geq 1,\; 2^n \geq n+1$

3Divisibilité

Init. (n = 0) $7^0 - 1 = 1-1 = 0 = 6 \times 0$ $6 \mid 0 \;\Rightarrow\; P(0) \text{ vraie.}$

HR $\text{Soit } n \in \mathbb{N}\text{. On suppose } 6 \mid 7^n-1\text{, i.e. }\exists\, m \in \mathbb{Z},\; 7^n-1 = 6m.$ $\text{On montre } 6 \mid 7^{n+1}-1.$

Décomposition $7^{n+1}-1 = 7 \cdot 7^n - 1 = 7(7^n-1)+6 = 7 \cdot 6m + 6 =$ $6(7m+1)$

Concl. $7m+1 \in \mathbb{Z} \Rightarrow 6 \mid 7^{n+1}-1 \Rightarrow$ $\forall n \in \mathbb{N},\; 6 \mid 7^n-1$

4Suite bornée

a) Calcul $u_1 = \dfrac{3+1}{2} = 2 \qquad u_2 = \dfrac{2+1}{2} =$ $\dfrac{3}{2}$

b) Init. (n = 0) $u_0 = 3 \quad\text{et}\quad 1 \lt 3 \leq 3$ $P(0) \text{ vraie.}$

b) HR $\text{Soit } n \in \mathbb{N}\text{. On suppose } 1 \lt u_n \leq 3.$ $\text{On montre } 1 \lt u_{n+1} \leq 3.$

b) Borne inf. $u_n \gt 1 \Rightarrow u_n+1 \gt 2 \Rightarrow u_{n+1} = \dfrac{u_n+1}{2} \gt$ $1$

b) Borne sup. $u_n \leq 3 \Rightarrow u_n+1 \leq 4 \Rightarrow u_{n+1} = \dfrac{u_n+1}{2} \leq \dfrac{4}{2} =$ $2 \leq 3$

b) Concl. $P(0) \text{ vraie, hérédité établie} \Rightarrow$ $\forall n \in \mathbb{N},\; 1 \lt u_n \leq 3$