Raisonnement par récurrence

L'induction mathématique est une façon particulière de prouver une vérité mathématique. Elle peut être utilisée pour prouver que quelque chose est vrai pour tous les nombres naturels (tous les nombres entiers positifs). L'idée est que

• Quelque chose est vrai pour le premier cas
• Il en va toujours de même pour le cas suivant

puis

• La même chose est vraie pour chaque cas

Dans le langage prudent des mathématiques :

• Préciser que la preuve sera apportée par induction sur n {\displaystyle n} . ( n {\displaystyle n} est la variable d'induction.)
• Démontrer que l'affirmation est vraie lorsque n {\displaystyle n} est égal à 1.
• Supposons que l'énoncé soit vrai pour tout nombre naturel n {\displaystyle n} . (C'est ce qu'on appelle l'étape d'induction).
• Montrez ensuite que la déclaration est vraie pour le nombre suivant, n + 1 {\style d'affichage n+1} .

Parce que c'est vrai pour 1, alors c'est vrai pour 1+1 (=2, par l'étape d'induction), alors c'est vrai pour 2+1 (=3), alors c'est vrai pour 3+1 (=4), et ainsi de suite.

Un exemple de preuve par induction :

Prouvez que pour tous les nombres naturels n :

1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\displaystyle 1+2+3+.... +(n-1)+n={\tfrac {1}{2}}n(n+1)}

Preuve :

Premièrement, la déclaration peut être écrite : pour tous les nombres naturels n

2 ∑ k = 1 n k = n ( n + 1 ) {\displaystyle 2\sum _{k=1}^{n}k=n(n+1)}

Par induction sur n,

Premièrement, pour n=1 :

2 ∑ k = 1 1 k = 2 ( 1 ) = 1 ( 1 + 1 ) {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)} ,

C'est donc vrai.

Ensuite, supposons que pour certains n=n0, l'affirmation est vraie. C'est-à-dire, :

2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)}

Puis pour n=n0+1 :

2 ∑ k = 1 n 0 + 1 k {\displaystyle 2\sum _{k=1}^{{{n_{0}}+1}k}

peut être réécrite

2 ( ∑ k = 1 n 0 k + ( n 0 + 1 ) ) {\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)}

Puisque 2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) , {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),}

2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)}

La preuve est donc correcte.