Exercice 1
Exercice 2
Exercice 3
Exercice 4
Exercice 5
Exercice 6
Exercice 7
Exercice 8

Introduction

Allons-y, mes amis, nous allons essayer de comprendre à travers un exemple ce qu'est le raisonnement par récurrence et comment l'utiliser. Nous allons commencer tout de suite. Le raisonnement par récurrence, avec démonstration par récurrence, est une technique qui vous permet de démontrer quelque chose sans vraiment comprendre ce que vous êtes en train de démontrer.

Exemple

Prenons un exemple. Supposons que nous voulons démontrer que la suite \(u_n\) qui est définie de manière récurrente, avec le terme suivant égal à trois fois le terme précédent plus deux, c'est-à-dire \(u_{n+1} = 3u_n + 2\), est positive. Il y a plusieurs stratégies pour démontrer cela. La première serait de vérifier par le calcul. Par exemple, nous savons que \(u_0 = 2\), et \(2\) est positif, donc \(u_0\) est positif. Ensuite, nous pouvons vérifier que \(u_1\) est positif, puisque \(u_1 = 3u_0 + 2 = 3 \times 2 + 2 = 8\), et \(8\) est bien positif, donc \(u_1\) est positif. Cependant, cette méthode serait infiniment longue pour démontrer que tous les termes de la suite sont positifs. Ce que nous allons faire à la place, c'est utiliser la technique suivante : nous allons vérifier que le premier terme est plus grand que zéro, et ensuite nous allons vérifier que si un terme est plus grand que zéro, alors le terme suivant est aussi plus grand que zéro.

Démonstration par récurrence

Pour faire cela en pratique, nous allons d'abord identifier trois choses : ce que nous devons démontrer, pour quelle valeur de \(n\) nous devons le démontrer, et comment nous allons le faire. Dans cet exemple, ce que nous devons démontrer est que la suite est positive. Pour quelle valeur de \(n\) nous devons le démontrer est facile à voir : cela commence pour \(n = 0\). Comment nous allons le faire est donné par cette relation de récurrence : \(u_{n+1} = 3u_n + 2\). La démonstration par récurrence commence en définissant une propriété \(P(n)\), qui est la propriété que nous voulons démontrer. Dans cet exemple, \(P(n)\) est la propriété que \(u_n\) est plus grand que zéro. La première étape de la récurrence est l'initialisation, où nous montrons que la propriété est vraie pour la première valeur de \(n\), qui est zéro dans cet exemple. Ensuite, nous passons à l'étape de l'hérédité, où nous montrons que si la propriété est vraie pour un certain \(n\), alors elle est aussi vraie pour \(n+1\). Enfin, nous concluons que la propriété est vraie pour tout \(n\) appartenant à \(\mathbb{N}\), car elle est initialisée et héréditaire. Voilà, c'est la puissance de la démonstration par récurrence. Vous devriez maintenant être capable de comprendre et d'utiliser cette technique.