Principe de la démonstration par réccurence

Soit P(n) une proposition faite sur n

1) P(n) est vrai pour un certain n=n0

2) P(n) vraie P(n+1) vraie, pour nn0

si ces deux conditions sont vérifiées alors :

La propriété est alors vraie pour tout nn0.

la condition 1 est appellée initialisation
la condition 2 est appellée hérédité

Démonstration :

soit le plus petit entier m, m>n0 tel que P(m) soit fausse.
alors P(m-1) est fausse (si il etait vrai, P(m) serait vrai d'apres 2)

donc m n'est pas le plus petit entier tel que P(m) soit fausse

on en arrive à une contradiction.

exercice corrigé

Montrer que P(n) : 10^n-1 est divisible par 9, est vraie pour tout n0

--------------------------------------------

1) P(0) : 10^0 - 1 = 0 ; 0 est divisible par 9, P(0) est vraie.

2) Supposons P(n) vrai :

on a 10^n - 1 = 9k (k)
10^n = 9k + 1
10^(n+1) =90k+10
10^(n+1) - 1 = 9(10k+1)

P(n)P(n+1)

10^n - 1 est divisible par 9 pour tout n0