Médaille
N°1 pour apprendre & réviser du collège au lycée.
Savoir mener un raisonnement par récurrence
Savoir-faire

Pré-requis

Le raisonnement par récurrence se fait en trois étapes que sont l’initialisation, l’hérédité et la conclusion. Ces trois étapes sont nécessaires pour mener à bien un tel raisonnement que nous allons illustrer à partir d’un exemple.

Etapes

Initialisation

La proposition (P1)(P_1) est vraie car 1=1(1+1)21 = \dfrac{1(1+1)}{2}

On conçoit et on admet que si l’on sait démontrer que «(Pn)(Pn) vraie » entraîne « (Pn+1)(P{n+1}) vraie », alors la proposition est vraie pour tout entier naturel n>0n > 0.

Hérédité

Supposons donc que (Pn)(P_n) est vraie pour un entier naturel nn, c’est-à-dire que pour un entier naturel nn :

1+2+3+4++n1+n=n(n+1)21+2+3+4+… + n-1 + n =\dfrac{n(n+1)}{2}

  • C’est l’hypothèse de récurrence.

Montrons maintenant que la propriété est vraie au rang supérieur (au rang n+1n+1), c’est-à-dire que (Pn+1)(P_{n+1}) est vraie.

Autrement dit, montrons que :

1+2+3+...+n+(n+1)=(n+1)(n+2)21+2+3+…+n+(n+1) =\dfrac{(n+1)(n+2)}{2}

Comme (Pn)(P_n) est vraie, alors dans la somme 1+2+3+...+n+(n+1)1+2+3+…+n+(n+1), on peut remplacer les premiers termes par n(n+1)2\dfrac{n(n+1)}{2}.

On obtient alors :

  • 1+2+3  +  ...n+n+1=n(n+1)2+n+11 + 2 + 3\;+\;… n + n + 1 = {\dfrac{n(n+1)}{2} } + n+1

En factorisant par , on obtient :

  • 1+2+3  +  ...n+n+1=n(n+1)2+n+11 + 2 + 3\;+\;… n + n + 1 = {\dfrac{n(n+1)}{2} } + n+1

En factorisant par n+1n + 1, on obtient :

1+2+3  +  ...+  n+(n+1)=(n+1)n2+(n+1)=(n+1)(n2+1)\begin{aligned}1 + 2 + 3\;+\;… +\;n + (n + 1) &= {(n+1) { \dfrac{n}{2} } } + (n+1) \&= {(n+1)}( \dfrac{n}{2} +1) \end{aligned}

En réduisant le deuxième facteur au même dénominateur 2, on a :

  • 1+2+3  +  ...+  n+n+1=(n+1)(n+2)21 + 2 + 3\;+\;… +\;n + n + 1 = \dfrac{(n+1)(n+2)}{2}

Ainsi (Pn+1)(P_{n+1}) est vraie.

Conclusion

(Pn)(P_n) est vraie pour tout entier naturel n>0n > 0, c’est-à-dire pour tout entier naturel nn 1+2+3  +  +  n=n(n+1)21+2+3\;+\;…+\;n = \dfrac{n(n+1)}{2},