Le raisonnement par récurrence — exercices types corrigés

1. 1.
   Initialisation ($n=1$n = 1) : membre de gauche $=1$= 1, membre de droite $=\frac{1\times 2}{2}=1$= (1× 2)/2 = 1. Donc $P(1)$P(1) est vraie.

   → Principe de récurrence
2. 2.
   Hérédité : on suppose $1+\cdots +n=\frac{n(n+1)}{2}$1 + … + n = (n(n+1))/2. Alors $1+\cdots +n+(n+1)=\frac{n(n+1)}{2}+(n+1)=\frac{(n+1)(n+2)}{2}$1 + … + n + (n+1) = (n(n+1))/2 + (n+1) = ((n+1)(n+2))/2.

   → Hypothèse de récurrence
3. 3.
   C'est $P(n+1)$P(n+1). Par récurrence, la propriété est vraie pour tout $n\ge 1$n ≥ 1.

Méthode utilisée : Récurrence : initialisation au rang $1$1, puis hérédité.

Erreur fréquente : Sauter l'initialisation et ne faire que l'hérédité.

1. 1.
   Initialisation ($n=0$n = 0) : $2^0=1$2⁰ = 1 et $0+1=1$0 + 1 = 1, donc $2^0\ge 0+1$2⁰ ≥ 0 + 1. $P(0)$P(0) est vraie.

   → Principe de récurrence
2. 2.
   Hérédité : on suppose $2^n\ge n+1$2ⁿ ≥ n + 1. Alors $2^{n+1}=2\times 2^n\ge 2(n+1)=2n+2$2ⁿ⁺¹ = 2× 2ⁿ ≥ 2(n+1) = 2n + 2.

   → Hypothèse de récurrence
3. 3.
   Or $2n+2\ge n+2=(n+1)+1$2n + 2 ≥ n + 2 = (n+1) + 1 (car $n\ge 0$n ≥ 0). Donc $2^{n+1}\ge (n+1)+1$2ⁿ⁺¹ ≥ (n+1) + 1 : c'est $P(n+1)$P(n+1).
4. 4.
   Par récurrence, $2^n\ge n+1$2ⁿ ≥ n + 1 pour tout $n\ge 0$n ≥ 0.

Méthode utilisée : Hérédité : on majore en partant de l'hypothèse de récurrence.

Erreur fréquente : Ne pas utiliser l'hypothèse de récurrence dans l'hérédité.

1. 1.
   Initialisation ($n=0$n = 0) : $4^0-1=0$4⁰ - 1 = 0, divisible par $3$3. $P(0)$P(0) est vraie.

   → Principe de récurrence
2. 2.
   Hérédité : on suppose $4^n-1=3k$4ⁿ - 1 = 3k pour un entier $k$k. Alors $4^{n+1}-1=4\times 4^n-1=4(3k+1)-1=12k+3=3(4k+1)$4ⁿ⁺¹ - 1 = 4× 4ⁿ - 1 = 4(3k + 1) - 1 = 12k + 3 = 3(4k + 1).

   → Hypothèse de récurrence
3. 3.
   $4^{n+1}-1$4ⁿ⁺¹ - 1 est donc divisible par $3$3 : c'est $P(n+1)$P(n+1). Par récurrence, vrai pour tout $n\ge 0$n ≥ 0.

Méthode utilisée : Hérédité : faire apparaître un multiple de $3$3 ($4^{n+1}-1=4(4^n-1)+3$4ⁿ⁺¹-1=4(4ⁿ-1)+3).

Erreur fréquente : Oublier d'isoler le multiple de $3$3.

1. 1.
   Initialisation ($n=0$n = 0) : $u_0=0\le 3$u₀ = 0 ≤ 3. $P(0)$P(0) est vraie.

   → Principe de récurrence
2. 2.
   Hérédité : on suppose $u_n\le 3$uₙ ≤ 3. Alors $u_{n+1}=\frac{u_n+3}{2}\le \frac{3+3}{2}=3$uₙ₊₁ = (uₙ + 3)/2 ≤ (3 + 3)/2 = 3.

   → Hypothèse de récurrence
3. 3.
   Donc $u_{n+1}\le 3$uₙ₊₁ ≤ 3 : c'est $P(n+1)$P(n+1). Par récurrence, $u_n\le 3$uₙ ≤ 3 pour tout $n\ge 0$n ≥ 0.

Méthode utilisée : Hérédité : si $u_n\le 3$uₙ≤ 3, alors $u_{n+1}=\frac{u_n+3}{2}\le 3$uₙ₊₁=(uₙ+3)/2≤ 3.

Erreur fréquente : Oublier l'initialisation $u_0\le 3$u₀≤ 3.

1. 1.
   Au rang $1$1 : membre de gauche $=1$=1.

   → Principe de récurrence
2. 2.
   Membre de droite $=\frac{1\times 2}{2}=1$=(1× 2)/2=1 : égalité vraie.

Méthode utilisée : On vérifie la propriété au premier rang.

Erreur fréquente : Sauter l'initialisation et n'écrire que l'hérédité.

1. 1.
   $u_1=1,u_2=3,u_3=7$u₁=1, u₂=3, u₃=7 : on conjecture $u_n=2^n-1$uₙ=2ⁿ-1.
2. 2.
   Rang $0$0 : $2^0-1=0=u_0$2⁰-1=0=u₀ : initialisation vérifiée.

   → Principe de récurrence

Méthode utilisée : On calcule des termes, on conjecture, on initialise.

Erreur fréquente : Conjecturer sans vérifier le premier terme.

1. 1.
   $2^{n+1}=2\times 2^n\ge 2(n+1)=2n+2$2ⁿ⁺¹=2× 2ⁿ≥ 2(n+1)=2n+2.

   → Hypothèse de récurrence
2. 2.
   $2n+2\ge n+2$2n+2≥ n+2 car $n\ge 0$n≥ 0. Donc $2^{n+1}\ge n+2$2ⁿ⁺¹≥ n+2.

Méthode utilisée : On part de l'hypothèse de récurrence et on majore.

Erreur fréquente : Ne pas utiliser l'hypothèse de récurrence dans l'hérédité.

1. 1.
   Rang $1$1 : $7-1=6$7-1=6, divisible par $6$6.

   → Principe de récurrence
2. 2.
   Hérédité : $7^{n+1}-1=7\times 7^n-1=7(7^n-1)+6$7ⁿ⁺¹-1=7× 7ⁿ-1=7(7ⁿ-1)+6.

   → Hypothèse de récurrence
3. 3.
   $7^n-1$7ⁿ-1 divisible par $6$6 (hypothèse) et $6$6 aussi : la somme l'est.

Méthode utilisée : Récurrence : initialisation, puis hérédité par mise en facteur.

Erreur fréquente : Oublier d'isoler un multiple de $6$6 dans l'hérédité.

1. 1.
   Rang $1$1 : gauche $=1$=1, droite $=1^2=1$=1²=1.

   → Principe de récurrence

Méthode utilisée : On vérifie au premier rang.

Erreur fréquente : Oublier l'initialisation.

1. 1.
   $4^{n+1}-1=4\times 4^n-1=4(4^n-1)+3$4ⁿ⁺¹-1=4× 4ⁿ-1=4(4ⁿ-1)+3.

   → Hypothèse de récurrence
2. 2.
   $4^n-1$4ⁿ-1 divisible par $3$3 (hypothèse) et $3$3 aussi.

Méthode utilisée : Mise en facteur d'un multiple de $3$3.

Erreur fréquente : Ne pas utiliser l'hypothèse de récurrence.