Raisonnement par récurrence

Raisonnement par récurrence.

P(n) désigne une certaine propriété dépendant d’un entier n et n0 désigne un entier naturel donné.

On veut démontrer que pour tout entier naturel n ≥ n0, la propriété P(n) est vraie.

Pour cela, on procède en deux étapes :

Etape 1. On vérifie que P(n0) est vraie,

Etape 2. On se donne un entier n ≥ n0 quelconque.

On suppose que pour cet entier n la propriété P(n) est vraie (c’est l’hypothèse de récurrence)

et on montre que sous cette hypothèse la propriété P(n + 1) est vraie.

Exemple 1. Montrer par récurrence que pour tout entier n ≥ 6, 2

n ≥ 6n + 7.

Solution 1.

• Si n = 6, 2

n = 2

6 = 64 et 6n + 7 = 6 × 6 + 7 = 43. Comme 43 < 64, l’inégalité de l’énoncé est vraie quand n = 6.

• Soit n ≥ 6. Supposons que 2

n ≥ 6n + 7 et montrons que 2

n+1 ≥ 6(n + 1) + 7.

2

n+1

= 2.2

n

≥ 2(6n + 7) (par hypothèse de récurrence)

= 12n + 14 = 6(n + 1) + 7 + 6n + 1

≥ 6(n + 1) + 7.

On a montré par récurrence que, pour tout entier naturel n ≥ 6, 2

n ≥ 6n + 7.

Exemple 2. Soit (un) la suite définie par u0 = 2 et pour tout entier naturel n, un+1 =

1

2

un + 2. Montrer par récurrence

que pour tout entier naturel n, un = 4 −

1

2

n−1

.

Solution 2.

• Si n = 0, 4 −

1

2

n−1

= 4 − 2 = 2 = u0. L’égalité de l’énoncé est vraie quand n = 0.

• Soit n ≥ 0. Supposons que un = 4 −

1

2

n−1

et montrons que un+1 = 4 −

1

2

(n+1)−1

.

un+1 =

1

2

un + 2

=

1

2



4 −

1

2

n−1



+ 2 (par hypothèse de récurrence)

= 2 −

1

2

1

2

n−1

+ 2 = 4 −

1

2

(n+1)−1

.

On a montré par récurrence que, pour tout entier naturel n, un = 4 −

1

2

n−1

.

Exemple 3. Montrer par récurrence que pour tout entier naturel n, 2

2n + 2 est un entier divisible par 3.

Solution 3.

• Si n = 0, 2

2n + 2 = 2

0 + 2 = 3 qui est bien divisible par 3. L’affirmation de l’énoncé est vraie quand n = 0.

• Soit n ≥ 0. Supposons que 2

2n + 2 est un entier divisible par 3, et montrons que 2

2(n+1) + 2 est un entier divisible par

3.

On a

2

2(n+1) + 2 = 2

2n+2 + 2 = 4.2

2n + 2 = 3.2

2n + 1.2

2n + 2 = 2

2n + 2 + 3.2

2n

.

Par hypothèse de récurrence, il existe un entier naturel k tel que 2

2n + 2 = 3.k. Mais alors,

2

2(n+1) + 2 = 2

2n + 2 + 3.2

2n = 3k + 3.2

2n = 3(2

2n + k).

Comme 2

2n + k est un entier, on en déduit que 2

2(n+1) + 2 est un entier divisible par 3.

On a montré par récurrence que, pour tout entier naturel n, 2

2n + 2 est un entier divisible par 3.