Le raisonnement par récurrence

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é.