Le raisonnement par récurrence : des exemples de rédaction

Formules

Sommes de référence (à démontrer par récurrence) :

• 1+2+\dots+n=\dfrac{n(n+1)}{2}.
• 1^2+2^2+\dots+n^2=\dfrac{n(n+1)(2n+1)}{6}.
• 1^3+2^3+\dots+n^3=\left(\dfrac{n(n+1)}{2}\right)^2.

Factorisation clé pour la somme des carrés : 2n^2+7n+6=(n+2)(2n+3).

Méthodes type bac

• Égalité de somme : dans l'hérédité, écrire S_{n+1}=S_n+(\text{terme }n+1), remplacer S_n par l'hypothèse, factoriser par (n+1).
• Divisibilité : poser E_n=a\,k (k entier) dans l'hypothèse, puis transformer E_{n+1} pour faire apparaître un facteur a.
• Inégalité / borne : pour u_{n+1}=f(u_n) avec f croissante, de u_n\le M déduire f(u_n)\le f(M) et vérifier f(M)\le M.

Pièges

• Oublier la phrase « Soit P(n) la propriété... » : le correcteur doit savoir ce qu'on démontre.
• Dans la divisibilité, ne pas introduire l'entier k : sans lui, on ne peut pas factoriser proprement.
• Pour les inégalités, vérifier que la fonction utilisée est bien croissante avant d'appliquer u_n\le M \Rightarrow f(u_n)\le f(M).

Détaillons le modèle « divisibilité ». Pour montrer que 3 divise 4^n-1 : au rang 1, 4^1-1=3 est bien divisible par 3. Hérédité : on suppose 4^n-1=3k avec k entier, donc 4^n=3k+1. Alors 4^{n+1}-1=4\times 4^n-1=4(3k+1)-1=12k+4-1=12k+3=3(4k+1), qui est un multiple de 3 puisque 4k+1 est entier. Le passage clé est la réécriture 4^{n+1}=4\times 4^n pour faire apparaître l'hypothèse.

Modèle « inégalité ». Pour u_0=0, u_{n+1}=\sqrt{2u_n+3} et la propriété u_n\le 3 : si u_n\le 3 alors 2u_n+3\le 9, et la racine étant croissante, u_{n+1}=\sqrt{2u_n+3}\le\sqrt 9=3. On exploite la croissance de la fonction x\mapsto\sqrt{2x+3}.

Pour l'épreuve

La qualité de la rédaction est notée. Nomme P(n), structure en trois blocs, exhibe l'hypothèse de récurrence dans l'hérédité, conclus par la formule consacrée. Les sommes \sum k et \sum k^2 sont des grands classiques : connaître la factorisation 2n^2+7n+6=(n+2)(2n+3) fait gagner un temps précieux. Pour la divisibilité, ne jamais oublier d'introduire l'entier auxiliaire k ; pour les inégalités, toujours nommer la fonction croissante utilisée.