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

Récurrences doubles et fortes : Définitions, divers exemples et exercices
Domino récurrence

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

Suite définie par récurrence

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

Suite définie par la somme des termes précédents

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 :

Récurrence double
Entier relatif et puissance d'inverse
Suite récurrente double

Exercices de récurrence forte

Voici quelques exercices de récurrence forte :

Récurrence forte
Récurrence forte et arithmétique
Suite triviale

Total
0
Partages
1 commentaire

Laisser un commentaire

Articles similaires