Raisonnement par récurrence : cours | Notions de logique 1ère Bac SM

À 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)$ une propriété qui dépend d'un entier $n$ , et $n_0 \in \mathbb{N}$ . Si :

Initialisation : $P(n_0)$ est vraie,
Hérédité : pour tout $n \geq n_0$ , $P(n) \Rightarrow P(n+1)$ ,

alors $P(n)$ est vraie pour tout entier $n \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

① Je sais monter la 1ʳᵉ marche (initialisation) ② De chaque marche, je sais monter à la suivante (hérédité)

Choisis les deux conditions, puis monte.

À l'examen

Rédaction type

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

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

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

Attention

L'hypothèse de récurrence

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

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

Explore

Observer avant de démontrer

Voici les valeurs de $u_n = 7^n - 2^n$ (Ex 7.1). Change le diviseur : lesquels semblent diviser tous les $u_n$ ?

Diviseur testé :

$n$	$7^n - 2^n$	reste ÷ 5
0	0	0
1	5	0
2	45	0
3	335	0
4	2385	0
5	16775	0
6	117585	0
7	823415	0
8	5764545	0
9	40353095	0
10	282474225	0
11	1977324695	0
12	13841283105	0

Méthode

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

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

$7^{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 $5$ divise $7^n - 2^n$ , les deux termes sont des multiples de $5$ .

Attention

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

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

Pourtant $P(n)$ est fausse pour tout $n$ : $10^0 + 1 = 2$ , $10^1 + 1 = 11$ … Sans initialisation, aucune conclusion !

Explore

Somme des cubes (Ex 10.3)

Compare les deux colonnes. Quelle formule semble vraie pour tout $n \geq 1$ ?

$n$	$\sum_{k=1}^{n} k^3$	$\left(\sum_{k=1}^{n} k\right)^2$
1	1	1
2	9	9
3	36	36
4	100	100
5	225	225
6	441	441
7	784	784
8	1296	1296
9	2025	2025
10	3025	3025