La récurrence double et la récurrence forte : Cours et exercices corrigés

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

La récurrence

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 n₀ et un rang n₀ +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 ≥ n₀ 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 n₀ souvent 0 ou 1. Cette étape s’appelle l’initialisation.
• Si on suppose que la propriété est vraie pour tous les rangs n₀ ≤ 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} - 1

On 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 :