Dans cet article, nous allons nous intéresser à 2 formes particulières de récurrence, la récurrence double et la récurrence forte
Prérequis
Cours
La récurrence que nous vous avions présentée était un modèle de récurrence qu’on appelle récurrence simple. 2 autres modèles plus complexes existent : la récurrence double et la récurrence forte
Récurrence double
Le principe est le suivant : pour l’hérédité, au lieu d’utiliser le terme précédent, on va utiliser les deux termes précédents. La conséquence sur l’initialisation est qu’on va alors avoir besoin des deux premiers termes. Voici le principe de la récurrence double :
- La propriété est vraie pour un premier rang n0 et un rang n0 +1 souvent 0 et 1 ou 1 et 2. Cette étape s’appelle l’initialisation.
- Si on suppose que la propriété est vraie pour un rang n ≥ n0 et un rang n-1 alors on montre la propriété au rang n+1. Cette étape s’appelle l’hérédité, comme pour la récurrence simple.
Récurrence forte
Cette fois, au lieu de s’autoriser à utiliser un ou 2 termes pour l’hérédité, on va s’autoriser à utiliser tous les termes précédents. Voici le principe de la récurrence forte :
- La propriété est vraie pour un premier rang n0 souvent 0 ou 1. Cette étape s’appelle l’initialisation.
- Si on suppose que la propriété est vraie pour tous les rangs n0 ≤ k ≤ n alors on montre la propriété au rang n+1. Cette étape s’appelle encore et toujours l’hérédité.
Exercices corrigés
Récurrence double : Exercice 805
On va donc faire une récurrence double
Initialisation : On va donc démontrer que la propriété est vraie aux rangs 0 et 1.
n = 0 :
2^1 - 1 = 2 - 1 = 1 = u_0
n = 1 :
2^2 - 1 = 4 - 1 = 3 = u_1
La propriété est bien vraie aux rangs 0 et 1
Hérédité : Soit n un entier fixé. On suppose que la propriété est vraie aux rangs n et n – 1, c’est à dire que
u_{n-1} = 2^n - 1, u_n = 2^{n+1} - 1On a donc :
\begin{array}{ll}
u_{n+1} & = 3u_n - 2u_{n-1}\\
&= 3 (2^{n+1}-1) - 2(2^n - 1) \\
&= 3 \times 2^{n+1} - 3 - 2^{n+1} +2 \\
&= 2^{n+1}(3-1) - 1 \\
&= 2^{n+2} - 1
\end{array}L’hérédité est vérifiée, ce qui conclut cette récurrence double
Récurrence forte : Exercice 1044
Démontrons cette propriété via une récurrence forte
Initialisation : Pour n = 1, on a bien
u_1 = \sum_{k=0}^0 u_k = u_0 = 1 = 2^{1-1}Hérédité : Soit n un entier fixé : On suppose que
\forall k \leq n, u_k = 2^{k-1}On a alors :
\begin{array}{ll}
u_{n+1} &= \displaystyle \sum_{k=0}^n u_k \\
&= \displaystyle \sum_{k=1}^n u_k + u_0\\
&= \displaystyle \sum_{k=1}^n 2^{k-1} + u_0\\
&= \displaystyle \sum_{k=0}^{n-1} 2^k + 1\\
&= \displaystyle \dfrac{2^n-1}{2-1} + 1\\
&= 2^n-1 + 1\\
&= 2^n\\
\end{array}Ce qui démontre l’hérédité et conclut cette récurrence forte
Enoncés d’exercices
Exercices de récurrence double
Voici quelques exercices de récurrence double :
Exercices de récurrence forte
Voici quelques exercices de récurrence forte :
