Suites et récurrence/Exercices/Démonstration par récurrence

Montrer par récurrence les propriétés suivantes :

1. $\forall n\in \mathbb {N} ^{*}\quad \sum _{1\leq j\leq n}{(j\times j!)}=(n+1)!-1$ ;
2. $\forall n\in \mathbb {N} \quad {\frac {1}{n!}}\leq {\frac {1}{2^{n-1}}}$ ;
3. $\forall n\in \mathbb {N} \quad 5^{n}-2^{n}$ est multiple de 3.

Solution

1. Notons ${\mathcal {P}}_{n}$ la propriété « $\sum _{1\leq j\leq n}{(j\times j!)}=(n+1)!-1$ ».
   • Intitialisation : $\sum _{1\leq j\leq 1}{(j\times j!)}=1\times 1!=1$ et $(1+1)!-1=2!-1=1$, donc ${\mathcal {P}}_{1}$ est vraie.
   • Hérédité : soit $n\in \mathbb {N} ^{*}$ tel que ${\mathcal {P}}_{n}$ soit vraie, montrons que ${\mathcal {P}}_{n+1}$ est vraie.
     Par définition, $\sum _{1\leq j\leq n+1}{(j\times j!)}$ est égal à $(n+1)\times (n+1)!+\sum _{1\leq j\leq n}{(j\times j!)}$ donc (par hypothèse de récurrence) à $(n+1)\times (n+1)!+(n+1)!-1=(n+2)\times (n+1)!-1=(n+2)!-1$, donc ${\mathcal {P}}_{n+1}$ est vraie.
   • Conclusion : le principe de récurrence permet de conclure : $\forall n\in \mathbb {N} ^{*}\quad {\mathcal {P}}_{n}$.
   • Remarque : $(0+1)!-1=0$ et par convention sur les sommes vides $\sum _{1\leq j\leq 0}{(j\times j!)}=0$ donc ${\mathcal {P}}_{0}$ est vraie. Cette convention est cohérente avec la définition par récurrence des sommes indexées utilisée dans la preuve d'hérédité ci-dessus, qui reste valide pour $n\in \mathbb {N}$. On aurait donc pu initialiser la récurrence à $n=0$ et démontrer ainsi : $\forall n\in \mathbb {N} \quad {\mathcal {P}}_{n}$.
2. Notons ${\mathcal {Q}}_{n}$ la propriété « ${\frac {1}{n!}}\leq {\frac {1}{2^{n-1}}}$ ».
   • Hérédité : soit $n\in \mathbb {N}$ tel que ${\mathcal {Q}}_{n}$ soit vraie, essayons de montrer que ${\mathcal {Q}}_{n+1}$ est vraie.
     ${\frac {1}{(n+1)!}}={\frac {1}{(n+1)\times n!}}={\frac {1}{n+1}}\times {\frac {1}{n!}}$ est inférieur ou égal (par hypothèse de récurrence) à ${\frac {1}{n+1}}\times {\frac {1}{2^{n-1}}}$ qui, à condition que $n\geq 1$, est lui-même majoré par ${\frac {1}{2}}\times {\frac {1}{2^{n-1}}}={\frac {1}{2^{(n+1)-1}}}$. On a donc bien ${\mathcal {Q}}_{n}\Rightarrow {\mathcal {Q}}_{n+1}$, mais seulement pour tout entier $n\in \mathbb {N} ^{*}$. Ceci oblige à initialiser la récurrence à $n=1$, et à étudier séparément le cas $n=0$.
   • Intitialisation : ${\frac {1}{1!}}={\frac {1}{1}}=1$ et ${\frac {1}{2^{1-1}}}=1$, donc ${\mathcal {Q}}_{1}$ est vraie.
   • Conclusion : le principe de récurrence permet de conclure : $\forall n\in \mathbb {N} ^{*}\quad {\mathcal {Q}}_{n}$.
   • Cas $n=0$ : ${\frac {1}{0!}}={\frac {1}{1}}=1$ et ${\frac {1}{2^{0-1}}}=2$. Puisque $1\leq 2$, ${\mathcal {Q}}_{0}$ est vraie.
   • Synthèse : de $\forall n\in \mathbb {N} ^{*}\quad {\mathcal {Q}}_{n}$ et ${\mathcal {Q}}_{0}$, on déduit : $\forall n\in \mathbb {N} \quad {\mathcal {Q}}_{n}$.
3. Notons ${\mathcal {R}}_{n}$ la propriété « $5^{n}-2^{n}$ est multiple de 3 ».
   • Intitialisation : $5^{0}-2^{0}=1-1=0=3\times 0$, donc ${\mathcal {R}}_{0}$ est vraie.
   • Hérédité : soit $n\in \mathbb {N}$ tel que ${\mathcal {R}}_{n}$ soit vraie, montrons que ${\mathcal {R}}_{n+1}$ est vraie.
     Par hypothèse de récurrence, il existe un entier $k$ tel que $5^{n}-2^{n}=3k$. Alors, $5^{n+1}-2^{n+1}=5\times 5^{n}-2^{n+1}=5(3k+2^{n})-2^{n+1}=15k+(5-2)2^{n}=3(5k+2^{n})$ donc ${\mathcal {R}}_{n+1}$ est vraie.
   • Conclusion : le principe de récurrence permet de conclure : $\forall n\in \mathbb {N} \quad {\mathcal {R}}_{n}$.