Articles
Sciences and sociétés
Math - Démonstrations par récurrence

A) Définition

• La démonstration par récurrence se fait en 3 étapes:

1.Vérifier que la propriété P(n) est vraie à son premier rang, généralement 0 ou 1. C'est à dire on vérifie que P(0) est vraie. C'est l'initialistion.

• 2. Supposer que la propriété est vraie au rang n. C'est à dire P(n) est vraie. C'est l'hérédité ou l'héritage.

• 3. Vérifier alors que la propriété est aussi vraie au rang n+1. C'est à dire que P(n+1) est aussi vraie. C'est la conclusion.

Très rapidement,

P(0) est vraie,
Si P(n) alors P(n+1)

ou

P(0),
Si P(n) ⇒ P(n+1)

Le symbole "⇒" veut dire «implique» ou «si …, alors … »

B) Exemples:


Exemple 1:

On veut démontrer par récurrence l'inégalité suivante:

\(\sum _{k=1}^{n}\frac{1}{k^{2}}>\frac{3n}{2n+1}\)     pour \(n\ge 1\).

• Pour \(n=1\), le membre de gauche se calcule ainsi:

\(\sum _{k=1}^{1}\frac{1}{k^{2}}=\frac{1}{1^{2}}=1\).

Le membre de droite:

\(\frac{3(1)}{2(1)+1}=\frac{3}{3}=1\).

Comme l'inégalité \(1>1\) est fausse, l'inégalité n'est pas satisfaite pour \(n=1\).

• Pour \(n=2\), le membre de gauche se calcule ainsi:

\(\sum _{k=1}^{2}\frac{1}{k^{2}}=\frac{1}{1^{2}}+\frac{1}{2^{2}}=1+\frac{1}{4}=\frac{5}{4}\).

Le membre de droite:

\(\frac{3(2)}{2(2)+1}=\frac{6}{5}\).

Puisque \(\frac{5}{4}=1.25\) et \(\frac{6}{5}=1.2\), on observe que \(\frac{5}{4}>\frac{6}{5}\), Par conséquent, l'inégalité est vérifiée pour \(n=2\).

• On suppose que l'inégalité est vraie pour un entier \(m\ge 2\), c'est à dire, \(\sum _{k=1}^{m}\frac{1}{k^{2}}>\frac{3m}{2m+1}\).

Il faut alors montrer que l'inégalité est vraie pour \(m+1\), c'est à dire ,

\(\sum _{k=1}^{m+1}\frac{1}{k^{2}}>\frac{3(m+1)}{2(m+1)+1}\).

La somme pour \(m+1\) a pour expression:

\(\sum _{k=1}^{m+1}\frac{1}{k^{2}}=\sum _{k=1}^{m}\frac{1}{k^{2}}+\frac{1}{(m+1)^{2}}\).

Utilisons l'hypothèse de récurrence, on sait que

\(\sum _{k=1}^{m}\frac{1}{k^{2}}>\frac{3m}{2m+1}\) . Donc,

\(\sum _{k=1}^{m+1}\frac{1}{k^{2}}>\frac{3m}{2m+1}+\frac{1}{(m+1)^{2}}\).

Il faut montrer que : \(\frac{3m}{2m+1}+\frac{1}{(m+1)^{2}}>\frac{3(m+1)}{2(m+1)+1}\).

L'inégalité à démontrer est:

\(\frac{3m}{2m+1}+\frac{1}{(m+1)^{2}}>\frac{3m+3}{2m+3}\).

Ou, en réarrangant les termes,

\(\frac{1}{(m+1)^{2}}>\frac{3m+3}{2m+3}-\frac{3m}{2m+1}\).

On simplifie le membre de droite:

\(\frac{3m+3}{2m+3}-\frac{3m}{2m+1}=\frac{(3m+3)(2m+1)-3m(2m+3)}{(2m+3)(2m+1)}\).

Développant le numérator:

\((6m^{2}+3m+6m+3)-(6m^{2}+9m)=6m^{2}+9m+3-6m^{2}-9m=3\).

Ainsi, l'inégalité devient:

\(\frac{1}{(m+1)^{2}}>\frac{3}{(2m+3)(2m+1)}\).

Ce qui est équivalent à

\((2m+3)(2m+1)>3(m+1)^{2}\).

On développe les deux membres de l'inéquation: \(4m^{2}+2m+6m+3 > 3(m^{2}+2m+1)\).

Cela se simplifie en:

\(4m^{2}+8m+3>3m^{2}+6m+3\). En soustrayant \(3m^{2}+6m+3\) des deux membres, on obtient: \(m^{2}+2m>0\).

Mettons \(m\) en facteur, on obtient \(m(m+2)>0\).

Puisque \(m\ge 2\), \(m\) et \(m+2\) sont positifs, donc leur produit \(m(m+2)\) est toujours positif.

Ainsi, l'inégalité \(m(m+2)>0\) est vraie pour tout \(m\ge 2\).

Donc la démonstration par récurrence est complétée.

Réponse finale:

L'inégalité \(\sum _{k=1}^{n}\frac{1}{k^{2}}>\frac{3n}{2n+1}\) est vraie pour tout entier \(n\ge 2\).


Exemple 2:

On veut démontrer par récurrence l'inégalité suivante:

\(4^{n}(n!)^{3}<(n+1)^{3n}\)

• Pour \(n=1\),

Le membre de gauche est: \(4^{1}(1!)^{3}=4\cdot 1^{3}=4\).
Le membre de droite est \((1+1)^{3\cdot 1}=2^{3}=8\).

Puisque \(4<8\), l'inégalité est vraie pour \(n=1\).

• L'hypothèse de récurrence est supposée vraie pour l'entier positif \(k\), C'est à dire, \(4^{k}(k!)^{3}<(k+1)^{3k}\).

Il faut alors prouver que l'inégalité est vraie pour \(n=k+1\), c'est à dire, \(4^{k+1}((k+1)!)^{3}<(k+2)^{3(k+1)}\).

Le membre de gauche de l'énégalité pour \(n=k+1\) est \(4^{k+1}((k+1)!)^{3}\).

Qui peut s'écrire \(4\cdot 4^{k}\cdot (k+1)^{3}(k!)^{3}\).

En réarrangant les termes, cela devient \(4(k+1)^{3}\cdot 4^{k}(k!)^{3}\).

En utilisant l'Hypothèse de récurrence, \(4^{k}(k!)^{3}<(k+1)^{3k}\), l'expression peut s'ecrire:

: \(4(k+1)^{3}\cdot 4^{k}(k!)^{3}<4(k+1)^{3}(k+1)^{3k}=4(k+1)^{3k+3}\).

Maintenant, on a besoin de montrer que \(4(k+1)^{3k+3}<(k+2)^{3(k+1)}\). Ou:

\(4<\left(\frac{k+2}{k+1}\right)^{3(k+1)}\).

Le term \(\left(\frac{k+2}{k+1}\right)^{3(k+1)}\) peut s'ecrire :

\(\left(1+\frac{1}{k+1}\right)^{3(k+1)}\).

On sait que \(\left(1+\frac{1}{m}\right)^{m}>2\) for \(m\ge 1\).

Ici, \(m=k+1\). Donc, \(\left(1+\frac{1}{k+1}\right)^{k+1}>2\).

Par conséquent,

\(\left(1+\frac{1}{k+1}\right)^{3(k+1)}=\left(\left(1+\frac{1}{k+1}\right)^{k+1}\right)^{3}>2^{3}=8\).

Puisque \(4<8\),

l'inégalité \(4<\left(\frac{k+2}{k+1}\right)^{3(k+1)}\) est vraie.

Ainsi, \(4^{k+1}((k+1)!)^{3}<(k+2)^{3(k+1)}\) est démontrée.

Réponse finale

L'inégalité \(4^{n}(n!)^{3}<(n+1)^{3n}\) est vraie pour tout entier positif \(n\) .


Exemple 3:

Étape 1 : Initialisation

Nous devons d'abord vérifier l'inégalité pour la plus petite valeur de \(n\). Dans ce cas, nous choisissons \(n=1\).

Le côté gauche de l'inégalité devient :\(1!\times 3!=1\times 6=6\)

Le côté droit de l'inégalité devient :\(((1+1)!)^{1+1}=(2!)^{2}=2^{2}=4\)

Puisque \(6\ge 4\), l'inégalité est vraie pour \(n=1\).

Étape 2 : Hypothèse de récurrence

Nous supposons que l'inégalité est vraie pour un certain entier \(k\ge 1\). Autrement dit, nous supposons que :\(1!\times 3!\times \dots \times (2k+1)!\ge ((k+1)!)^{k+1}\)

Étape 2 : Hérédité

Nous devons maintenant prouver que l'inégalité est également vraie pour \(n=k+1\). Pour cela, nous devons démontrer que :

\(1!\times 3!\times \dots \times (2k+1)!\times (2(k+1)+1)!\ge ((k+1+1)!)^{k+1+1}\)

Ceci se simplifie en :\(1!\times 3!\times \dots \times (2k+1)!\times (2k+3)!\ge ((k+2)!)^{k+2}\)

En utilisant notre hypothèse de récurrence, nous savons que :\(1!\times 3!\times \dots \times (2k+1)!\ge ((k+1)!)^{k+1}\)

Multiplions les deux côtés de cette inégalité par \((2k+3)!\) :\(1!\times 3!\times \dots \times (2k+1)!\times (2k+3)!\ge ((k+1)!)^{k+1}\times (2k+3)!\)

Pour prouver l'inégalité pour \(n=k+1\), il suffit de montrer que

:\(((k+1)!)^{k+1}\times (2k+3)!\ge ((k+2)!)^{k+2}\)

Simplifions le côté droit de l'inégalité

:\(((k+2)!)^{k+2}=((k+2)(k+1)!)^{k+2}=(k+2)^{k+2}((k+1)!)^{k+2}\)\(=(k+2)^{k+2}((k+1)!)^{k+1}(k+1)!\)

Maintenant, nous devons démontrer que :

\(((k+1)!)^{k+1}\times (2k+3)!\ge (k+2)^{k+2}((k+1)!)^{k+1}(k+1)!\)

Divisons les deux côtés par \(((k+1)!)^{k+1}\) (qui est un nombre positif)

:\((2k+3)!\ge (k+2)^{k+2}(k+1)!\)

Réorganisons l'inégalité :

\((2k+3)!=(2k+3)(2k+2)\dots (k+2)(k+1)!\)

Donc, nous devons montrer que :

\((2k+3)(2k+2)\dots (k+2)(k+1)!\ge (k+2)^{k+2}(k+1)!\)

Divisons par \((k+1)!\) :\((2k+3)(2k+2)\dots (k+2)\ge (k+2)^{k+2}\)

Le produit \((2k+3)(2k+2)\dots (k+2)\) contient \(k+2\) termes.\(2k+3>k+2\)\(2k+2>k+2\)...\(k+3>k+2\)\(k+2=k+2\)

Chacun des \(k+2\) termes du produit sur le côté gauche est supérieur ou égal à \(k+2\).

Le produit est donc supérieur ou égal à \((k+2)^{k+2}\).

L'inégalité est donc vraie pour \(n=k+1\).

Par le principe de la récurrence mathématique, l'inégalité est vraie pour tous les entiers \(n\ge 1\).

Étape 3 : Conclusion

L'inégalité \(\mathbf{1!\times 3!\times \dots \times (2n+1)!\ge ((n+1)!)}^{\mathbf{n+1}}\) est vraie pour tout entier \(n\ge 1\).


Exemple 4:



On veut prouver la double inéqualité suivante par le méthode du raisonnement par récurrence:

\(\sqrt{\frac{3}{4n+3}}<\prod _{k=1}^{n}\frac{4k+1}{4k+3}<\sqrt{\frac{5}{4n+5}}\)

On va la séparer en deux inéqualités :

Étape 1: Preuve de l'inégalité du membre de gauche

On va démontrer

\(\sqrt{\frac{3}{4n+3}}<\prod _{k=1}^{n}\frac{4k+1}{4k+3}\) pour tout entier \(n\ge 1\)

• Pour (n=1): ona besoin de vérifier:

\(\sqrt{\frac{3}{4(1)+3}}<\frac{4(1)+1}{4(1)+3}\) , qui est \(\sqrt{\frac{3}{7}}<\frac{5}{7}\)

Prenons le carré des deux memmbres, on obtient:

\(\frac{3}{7}<\frac{25}{49}\).

Qui se simplifie en \(21<25\), qui est vraie.

• On suppose que l'inégalité est vraie pour l'entier \(n=p\), c'est à dire,

\(\sqrt{\frac{3}{4p+3}}<\prod _{k=1}^{p}\frac{4k+1}{4k+3}\)

Il faut démontrer qu'elle l'est aussi pour \(n=p+1\), c'est à dire,

\(\sqrt{\frac{3}{4(p+1)+3}}<\prod _{k=1}^{p+1}\frac{4k+1}{4k+3}\).

On peut ecrire le produit pour \(n=p+1\) comme:

\(\prod _{k=1}^{p+1}\frac{4k+1}{4k+3}=\left(\prod _{k=1}^{p}\frac{4k+1}{4k+3}\right)\cdot \left(\frac{4(p+1)+1}{4(p+1)+3}\right)\)

D'après l'hypothèse de récurrence, on a:

\(\left(\prod _{k=1}^{p}\frac{4k+1}{4k+3}\right)\cdot \left(\frac{4p+5}{4p+7}\right)>\sqrt{\frac{3}{4p+3}}\cdot \frac{4p+5}{4p+7}\)

Il faut donc montrer que :

\(\sqrt{\frac{3}{4p+3}}\cdot \frac{4p+5}{4p+7}>\sqrt{\frac{3}{4p+7}}\).

Qui se simplifie en:

\(\frac{4p+5}{4p+7}>\sqrt{\frac{4p+3}{4p+7}}\).

Prenons le carré des deux membres , on obtient:

\((\frac{4p+5}{4p+7})^{2}>\frac{4p+3}{4p+7}\),

Qui se simplifie en \(\frac{(4p+5)^{2}}{4p+7}>4p+3\).

Qui mène à

\((4p+5)^{2}>(4p+3)(4p+7)\), qui est \(16p^{2}+40p+25>16p^{2}+40p+21\).

Cette inégalité est vraie (\(25>21\)). Ainsi, la démonstration par récurrence est prouvée et le membre de gauche de l'inégalité est démontré.

Étape 2: Preuve de l'inégalité du membre de droite

On va démontrer

\(\prod _{k=1}^{n}\frac{4k+1}{4k+3}<\sqrt{\frac{5}{4n+5}}\) pour tout entier \(n\ge 1\)

• (n=1):On a besoin de vérifier:

\(\frac{4(1)+1}{4(1)+3}<\sqrt{\frac{5}{4(1)+5}}\).

On a:

\(\frac{5}{7}<\sqrt{\frac{5}{9}}\), , qui est \(\frac{5}{7}<\frac{\sqrt{5}}{3}\).

Prenons le carré des deux memmbres, on obtient:

\(\frac{25}{49}<\frac{5}{9}\).

Qui se simplifie en \(225<245\),

Ce qui est vraie.

• On suppose que l'inégalité est vraie pour un entier \(n=p\), c'est à dire, \(\prod _{k=1}^{p}\frac{4k+1}{4k+3}<\sqrt{\frac{5}{4p+5}}\).

On a besoin de montrer qu'elle est vraie pour \(n=p+1\), c'est à dire, \(\prod _{k=1}^{p+1}\frac{4k+1}{4k+3}<\sqrt{\frac{5}{4(p+1)+5}}\).

À partir de l'hypothèse de récurrence, on a :

\(\prod _{k=1}^{p+1}\frac{4k+1}{4k+3}=\left(\prod _{k=1}^{p}\frac{4k+1}{4k+3}\right)\cdot \left(\frac{4p+5}{4p+7}\right)<\sqrt{\frac{5}{4p+5}}\cdot \frac{4p+5}{4p+7}\)

Ainsi on a besoin de montrer que \(\sqrt{\frac{5}{4p+5}}\cdot \frac{4p+5}{4p+7}<\sqrt{\frac{5}{4p+9}}\).

Qui se simplifie en

\(\frac{4p+5}{4p+7}<\sqrt{\frac{4p+5}{4p+9}}\).

Prenons le carré des deux membres, on obtient: \((\frac{4p+5}{4p+7})^{2}<\frac{4p+5}{4p+9}\).

Qui se simplifie en \(\frac{4p+5}{(4p+7)^{2}}<\frac{1}{4p+9}\),

Ce qui donne: \((4p+5)(4p+9)<(4p+7)^{2}\).

Ou: \(16p^{2}+56p+45<16p^{2}+56p+49\),

Ce qui est vrai (\(45<49\)).

Par conséquent, l'étape de récurrence est vérifiée et l'inégalité du membre de droite est démontrée.

En prouvant les inégalités du membre de gauche et du membre de droite par la démonstration par récurrence, nous pouvons conclure que l'inégalité

\(\sqrt{\frac{3}{4n+3}}<\prod _{k=1}^{n}\frac{4k+1}{4k+3}<\sqrt{\frac{5}{4n+5}}\) est vraie pour tout entier \(n\ge 1\).

-- Abdurrazzak Ajaja
Septembre 2025