Streak00/3aujourd'hui

Notions de logique · Leçon 5

Raisonnement par récurrence

0score
À ton avis ?

Une longue file de dominos. On sait que :

  • (1) le premier domino tombe ;
  • (2) chaque domino qui tombe fait tomber le suivant.

Que peut-on conclure ?

Propriété

Principe de récurrence

Soit P(n)P(n) une propriété qui dépend d'un entier nn, et n0∈Nn_0 \in \mathbb{N}. Si :

  • Initialisation : P(n0)P(n_0) est vraie,
  • Hérédité : pour tout n≥n0n \geq n_0, P(n)⇒P(n+1)P(n) \Rightarrow P(n+1),

alors P(n)P(n) est vraie pour tout entier n≥n0n \geq n_0.

Dans la vraie vie

L'escalier

Tu sais monter sur la première marche. Et depuis n'importe quelle marche, tu sais monter sur la suivante. Alors tu peux monter tout l'escalier.

Manipule

Monte l'escalier

P(0)P(1)P(2)P(3)P(4)P(5)P(6)

Choisis les deux conditions, puis monte.

À l'examen

Rédaction type

Initialisation : pour n=n0n = n_0, … donc P(n0)P(n_0) est vraie.

Hérédité : soit n≥n0n \geq n_0. Supposons que P(n)P(n) est vraie (hypothèse de récurrence) et montrons que P(n+1)P(n+1) est vraie. …

Conclusion : d'après le principe de récurrence, pour tout n≥n0n \geq n_0, P(n)P(n) est vraie.

Attention

L'hypothèse de récurrence

Dans l'hérédité, on fixe un entier nn et on suppose P(n)P(n) pour cet entier.

Écrire « supposons que pour tout nn, P(n)P(n) est vraie » revient à supposer ce qu'on veut démontrer !

Explore

Observer avant de démontrer

Voici les valeurs de un=7n−2nu_n = 7^n - 2^n.

La dernière colonne donne le reste de la division de unu_n par le diviseur. Reste 00 veut dire « divisible ».

Essaie d'autres diviseurs : 33, 44, 77…

nn7n−2n7^n - 2^nreste ÷ 5
000
150
2450
33350
423850
5167750
61175850
78234150
857645450

Avec 55, le reste vaut 00 sur toutes les lignes. On devine que 55 divise 7n−2n7^n - 2^n pour tout nn.

Un tableau ne prouve rien. La méthode suivante le démontre.

Méthode

L'astuce de l'hérédité (divisibilité)

On écrit le terme de rang n+1n+1 en fonction de celui de rang nn, pour faire apparaître l'hypothèse de récurrence :

7n+1−2n+1=7⋅7n−2⋅2n=7(7n−2n)+7⋅2n−2⋅2n=7(7n−2n)+5⋅2n7^{n+1} - 2^{n+1} = 7 \cdot 7^n - 2 \cdot 2^n = 7(7^n - 2^n) + 7 \cdot 2^n - 2 \cdot 2^n = 7(7^n - 2^n) + 5 \cdot 2^n

Si 55 divise 7n−2n7^n - 2^n, les deux termes sont des multiples de 55.

Attention

L'hérédité seule ne suffit pas

P(n)P(n) : « 99 divise 10n+110^n + 1 » est héréditaire : si 10n+1=9k10^n + 1 = 9k, alors 10n+1+1=10(10n+1)−9=9(10k−1)10^{n+1} + 1 = 10(10^n + 1) - 9 = 9(10k - 1).

Pourtant P(n)P(n) est fausse pour tout nn : 100+1=210^0 + 1 = 2, 101+1=1110^1 + 1 = 11… Sans initialisation, aucune conclusion !

Explore

Deviner une formule

Compare les deux colonnes, ligne par ligne.

  • Colonne 1 : la somme des cubes, 13+23+⋯+n31^3 + 2^3 + \cdots + n^3.
  • Colonne 2 : le carré de la somme, (1+2+⋯+n)2(1 + 2 + \cdots + n)^2.
nn13+23+⋯+n31^3 + 2^3 + \cdots + n^3(1+2+⋯+n)2(1 + 2 + \cdots + n)^2
111
299
33636
4100100
5225225
6441441

Les deux colonnes sont égales sur toutes les lignes. On devine la formule :

13+23+⋯+n3=(1+2+⋯+n)2pour tout n≥11^3 + 2^3 + \cdots + n^3 = (1 + 2 + \cdots + n)^2 \quad \text{pour tout } n \geq 1

Six lignes ne sont pas « pour tout nn ». Pour le démontrer, on utilise la récurrence.

Révision rapide · 17 exercices