La démonstration par récurrence est un outil très puissant et élégant. Cependant, il n’est pas toujours aussi facile que l’on ne le pense à mettre en place. Dans cet article, vous allez comprendre et apprendre le principe de récurrence.
Principe de la démonstration par récurrence
Dans une démonstration par récurrence, on va vouloir démontrer une propriété P.
Il y a deux étapes clés pour arriver à une conclusion.
Tout d’abord, on réalise l’initialisation on démontre la véracité de la propriété au rang n0
Pour reprendre un exemple bien connu. Imaginons un circuit de domino où on veut montrer que si l’on fait tomber le premier domino tous les dominos vont tomber.
Pour cela, on va montrer que si on fait tomber le premier domino alors le second va tomber cela reviendrait à faire l’initialisation au rang 1 car on regarde le premier domino.
Ensuite, on réalise l’hérédité, on suppose la propriété au rang K vraie et on va montrer que la propriété au rang K + 1 est vraie.
Dans les dominos, l’hérédité revient à prendre un domino au hasard ( rang K ), on suppose qu’il tombe ( propriété rang K supposée vraie ) puis on montre que le domino suivant tombe ( montrer que la propriété au rang K + 1 est vrai ).
Enfin, on peut conclure sur le fait que la propriété est vraie pour tout rang supérieur au rang n0.
On peut donc conclure que si on fait tomber un domino à partir du rang 1 alors tout le circuit de domino qui suit va tomber. ( Cependant on ne peut pas conclure sur la propriété avant le rang n0.
La rédaction avec un exemple
La rédaction dans une démonstration par récurrence est cruciale, souvent, elle va même la rendre beaucoup plus facile si elle est bien faite.
Pour vous montrer un exemple de rédaction attendue voici une récurrence assez facile et classique avec en bleu la rédaction spécifique de l’exemple qui sera à modifier selon l’exemple et en noir la rédaction qui peut apparaître dans toutes les récurrences qui pourras être reprise tel quel.
Une démonstration par récurrence classique est de montrer que $$1+2+…+n-1+n=\frac{n\times(n+1)}2$$
C’est-à-dire que $$\sum_{k=1}^nk\;=\;\frac{n\;\times\;(\;n\;+\;1\;)}2$$
RÉCURENCE :
pour tout n ∈ ℕ$$p_n:\sum_{k=1}^nk\;=\;\frac{n\;\times\;(\;n\;+\;1\;)}2$$
Initialisation:
pour n = 1 on a $$\sum_{k=1}^1k\;=\;1$$
et $$\frac{1\;\times\;(\;1\;+\;1\;)\;}2=\;1$$
donc p1 est vraie.
Hérédité:
Supposons pn vraie, c’est-à-dire qu’il existe n ∈ ℕ* tel que $$\sum_{k\;=\;1}^nk\;=\;\frac{n(\;n\;+\;1\;)\;}2$$
Montrons que pn+1 est vraie.
Tout d’abord, on a: $$\sum_{k=1}^nk=\frac{n\;(n+1)}2$$
donc $$1+…+n=\frac{n\;(n+1)}2$$
$$1+…+(n+1)=\frac{n\;(n+1)}2+(n+1)$$
$$1+…+(n+1)=\frac{n\;(n+1)+2\;(n+1)}2$$
En factorisant, on obtient : $$1+…+(n+1)=\frac{(n+1)\;(n+2)}2$$
$$1+…+(n+1)=\frac{(n+1)\;((n+1)+1)}2$$
$$\sum_{k=0}^{n+1}k=\frac{(n+1)\;((n+1)+1)}2$$
$$P_{n+1}$$
Donc s’il existe n ∈ ℕ tel que pn est vraie alors pn+1 est vraie.
Conclusion:
On a montré que p1 est vraie et que pn est héréditaire alors pour tout n ∈ ℕ* donc Pn est vraie.
Il n’y a pas de secret pour maîtriser la démonstration par récurrence, il faut s’entraîner ! Voici trois exercices avec leurs corrections du plus simple au plus compliqué.
Exercices
1) Soit la suite (un) définie par u0 = 2 et un+1 = un + 2n +5. Montrer par récurrence que pour tout n ∈ ℕ un = n2 + 4n + 2
2) Montrer que pour tout n ∈ ℕ*, $$\sum_{k=1}^nk^3\;=\frac{n^2\times{(\;n+1\;)}^2}4$$
3) Montrer que la fonction f définie par $$f_n:\;x\;\mapsto x^n$$ est dérivable pour tout n supérieur ou égal à 2 et de dérivée $$f’_n:\;x\;\mapsto nx^{n-1}$$
Corrections
1) pour tout n ∈ ℕ
$$p_n:u_n=\;n^{2\;}+4n\;+\;2$$
Initialisation:
pour n = 0 on a $$u_0\;=\;2$$
et $$0^2\;+\;0\;+\;2\;=\;2$$
donc p0 est vraie.
Hérédité:
Supposons pn vraie, c’est-à-dire qu’il existe n ∈ ℕ tel que $$u_n\;=\;n^2\;+\;4n\;+\;2$$
Montrons que pn+1 est vraie.
Tout d’abord, on a: $$u_{n+1}\;=\;u_n\;+\;2n\;+\;5$$
De plus, on a supposé pn vraie donc $$u_{n+1}\;=\;n^2\;+\;4n\;+\;2\;+\;2n\;+\;5$$
$$u_{n+1}\;=\;n^2\;+\;6n\;+\;7$$
$$u_{n+1}\;=\;(\;n^2\;+\;2n\;+\;1\;)\;+\;4n\;+\;6$$
$$u_{n+1}\;=\;{(\;n+1\;)}^2\;+\;4\times(\;n+1\;)\;+\;2$$
Donc, s’il existe n ∈ ℕ tel que pn est vraie alors pn+1 est vraie.
Conclusion:
On a montré que p0 est vraie et que pn est héréditaire alors pour tout n ∈ ℕ Pn est vraie.
2) pour tout n ∈ ℕ*
$$p_{n\;}:\;\sum_{k=1}^nk^3\;=\frac{n^2\times{(\;n+1\;)}^2}4$$
Initialisation:
pour n = 1 on a $$\;\sum_{k=1}^1k^3\;=\;1$$
et $$\frac{1^2\times\left(\;1+1\;\right)^2}4=\;\frac44=\;1$$
donc p1 est vraie.
Hérédité:
Supposons pn vraie, c’est-à-dire qu’il existe n ∈ ℕ* tel que
$$\sum_{k=1}^nk^3\;=\frac{n^2\times{(\;n+1\;)}^2}4$$
Montrons que pn+1 est vraie.
Tout d’abords, on a: $$\sum_{k=1}^{n+1}k^3\;=1^3+2^3+…+n^3+\left(\;n+1\;\right)^3$$
$$\sum_{k=1}^{n+1}k^3\;=\sum_{k=1}^nk^3\;\;+\;\left(\;n+1\;\right)^3$$
On a supposé pn vraie donc,
$$\sum_{k=1}^{n+1}k^3=\frac{n^2\times\left(n+1\right)^2}4+\left(n+1\right)^3$$
$$\sum_{k=1}^{n+1}k^3=\frac{n^2\times\left(n+1\right)^2+4\left(n+1\right)^3}4$$
$$\sum_{k=1}^{n+1}k^3=\frac{n^4+2n^3+n^2+4\left(n^3+3n^2+3n+1\right)}4$$
$$\sum_{k=1}^{n+1}k^3=\frac{n^4+6n^3+13n^2+12n+4}4$$
On remarque donc que l’on a une expression développer que l’on doit factoriser pour avancer, cependant ce n’est pas si simple.
On peut donc partir de ce que l’on veut trouver puis développer l’expression et regarder si c’est la même.
On veut montrer que l’expression ci-dessus est égale à: $$\sum_{k=1}^{n+1}k^3\;=\frac{\left(n+1\right)^2\times\left(\left(n+1\right)+1\right)^2}4$$
$$\sum_{k=1}^{n+1}k^3\;=\frac{\left(n^2+2n+1\right)\left(n^2+4n+4\right)}4$$
On utilise la distributivité, et on obtiens:
$$\sum_{k=1}^{n+1}k^3\;=\frac{n^4+6n^3+13n^2+12n+4}4$$
On remarque que l’on obtiens exactement l’expression du dessus donc on vient de montrer l’égalité.
Donc, si il existe n ∈ ℕ tel que pn est vraie alors pn+1 est vraie.
Conclusion:
On a montré que p1 est vraie et que pn est héréditaire alors pour tout n ∈ ℕ* Pn est vraie.
3) Pour toute la récurrence on prend n un entier naturel.
Pour tout n ≥ 2
Pn: La fonction fn est dérivable sur R de dérivée nx{n-1}
Initialisation:
pour n = 2 on a $$f’_2\;=\lim_{h\;\rightarrow\;0}\;\;\frac{f_2\;(\;x\;+\;h\;)\;-\;f_2\;(\;x\;)\;}h$$
$$=\;\lim_{h\;\rightarrow\;0}\frac{{(x+h)}^2\;-\;x^2}h$$
$$=\;\lim_{h\;\rightarrow\;0}\frac{x^2\;+\;2xh\;+\;h^2\;-\;x^2}h$$
$$=\;\lim_{h\;\rightarrow\;0}2x\;+\;h$$
$$=\;2x$$
Donc p2 est vrai
Hérédité:
Soit n ≥ 2, supposons pn vraie. Montrons que pn+1 l’est aussi.
$$f_{n+1}\;=\;x^{n+1}=\;x\;\times\;x^n\;=\;f_{1\;}\times\;f_n$$
Montrons d’abords que f1 est dérivable sur ℝ:
$$f’_1\;=\lim_{h\;->\;0}\;\frac{f_1(\;x\;+\;h\;)\;-\;f_1\;(\;x\;)}h$$
$$=\lim_{h\;->\;0}\;\frac{x\;+\;h\;-\;x}h=\;1$$
La limite est finie et existe donc f1 est dérivable.
De plus, on a supposé pn vraie donc fn est dérivable.
Donc
$$f’_{n+1}\;=\;f’_1\;f_n\;+\;f_1\;f’_n$$
$$f’_{n+1}\;=1\times\;x^n\;+\;x\times nx^{n-1}$$
$$f’_{n+1}\;=\;x^n\;+\;nx^n$$
$$f’_{n+1}\;=(\;n+1\;)\times\;x^n$$
Donc on a montré que s’il existe n ≥ 2 tel que pn vraie alors fn+1 est dérivable (produit de terme dérivables ) et sa dérivée est f’n+1 = (n+1)xn donc s’il existe n ≥ 2 tel que pn vraie alors pn+1 est vraie.
Conclusion:
On a montré que p2 est vraie et que pn est héréditaire donc pour tout n ≥ 2 pn est vraie.
