Solutions - Exercices sur la récurrence - 01

Solutions détaillées de neuf exercices sur raisonnement par récurrence (fiche 01).
Cliquer ici pour accéder aux énoncés.

Posons pour simplifier : $u_{n}=10\times8^{n-1}+3^{3n-1},$ pour tout $n\geqslant1.$

D’une part : $u_{1}=19$ est multiple de $19.$

D’autre part, si pour un certain $n\geqslant1,$ il existe $K\in\mathbb{N}$ tel que $u_{n}=19K,$ alors :

$\begin{eqnarray*}u_{n+1} & = & 10\times8^{n}+3^{3n+2}\\& = & 8\left(10\times8^{n-1}+3^{3n-1}\right)+3^{3n+2}-8\times3^{3n-1}\\& = & 8\times19K+3^{3n-1}\left(3^{3}-8\right)\\& = & 19\left(8K+3^{3n-1}\right)\end{eqnarray*}$

La propriété « $u_{n}$ est multiple de $19$ » est donc héréditaire. Comme elle est vraie pour $n=1,$ alors elle est vraie pour tout $n\geqslant1.$

Fixons $x>0.$

Au rang $2,$ l’inégalité est claire :

$\left(1+x\right)^{2}=1+2x+x^{2}>1+2x$

Supposons-la vraie au rang $n$ pour un certain entier $n\geqslant2.$ En multipliant chaque membre de l’inégalité $\left(1+x\right)^{n}>1+nx$ par le réel strictement positif $\left(1+x\right),$ on obtient :

$\left(1+x\right)^{n+1}>\left(1+x\right)\left(1+nx\right)$

c’est-à-dire :

$\left(1+x\right)^{n+1}>1+\left(n+1\right)x+nx^{2}$

et donc, a fortiori :

$\left(1+x\right)^{n+1}>1+\left(n+1\right)x$

On effectue une récurrence d’ordre $2.$ On l’initialise en calculant successivement :

$F_{11}=89>\left(\frac{3}{2}\right)^{11}$

car

$2^{11}\times89=2\thinspace048\times89=182\thinspace172>177\thinspace147=3^{11}$

$F_{12}=144>\left(\frac{3}{2}\right)^{12}$

car

$2^{12}\times144=4\thinspace096\times144=589\thinspace824>531\thinspace441=3^{12}$

Passons à l’hérédité. Si, pour un certain $n\geqslant13,$ on a $F_{n-2}>\left(\frac{3}{2}\right)^{n-2}$ et $F_{n-1}>\left(\frac{3}{2}\right)^{n-1},$ alors :

$F_{n}=F_{n-1}+F_{n-2}>\frac{3^{n-1}}{2^{n-1}}+\frac{3^{n-2}}{2^{n-2}}=\frac{3^{n-2}\times10}{2^{n}}>\frac{3^{n-2}\times9}{2^{n}}=\left(\frac{3}{2}\right)^{n}$

On peut établir directement l’inégalité demandée en étudiant les variations de la fonction :

$\left]0,+\infty\right[\rightarrow\mathbb{R},\thinspace t\mapsto t\ln\left(1+\frac{1}{t}\right)$

Il s’avère que celle-ci est croissante et donc majorée par sa limite en $+\infty$ qui vaut $1.$ On peut aussi invoquer l’inégalité très classique :

$\forall x>0,\thinspace\ln\left(1+x\right)\leqslant x$

(inégalité d’ailleurs valable pour tout $x>-1)$ et remplacer $x$ par ${\displaystyle \frac{1}{t}}.$ D’une façon ou d’une autre, on parvient à :

$\boxed{\forall t>0,\left(1+\frac{1}{t}\right)^{t}<e}$

Prouvons maintenant que :

$\forall n\in\mathbb{N},\thinspace n!\geqslant e^{-n}\left(n+1\right)^{n}\qquad\left(\star\right)$

par récurrence.

Pour $n=0,$ cette inégalité est vraie. Supposons-la vraie au rang $n;$ alors :

$\left(n+1\right)!=\left(n+1\right)\thinspace n!\geqslant e^{-n}\thinspace\left(n+1\right)^{n+1}$

Il suffit pour conclure que l’on ait :

$e^{-n}\left(n+1\right)^{n+1}\geqslant e^{-\left(n+1\right)}\left(n+2\right)^{n+1}$

c’est-à-dire :

$\left(1+\frac{1}{n+1}\right)^{n+1}\leqslant e$

et c’est bien le cas d’après $\left(\star\right).$

Montrons par récurrence que pour tout entier $n\geqslant2$ et pour tout $\left(a_{1},\cdots,a_{n}\right)\in\left]0,1\right[^{n}$ :

$\prod_{k=1}^{n}\left(1-a_{k}\right)>1-\sum_{k=1}^{n}a_{k}$

Pour $n=2,$ c’est vrai; en effet :

$\left(1-a_{1}\right)\left(1-a_{2}\right)=1-a_{1}-a_{2}+a_{1}a_{2}>1-a_{1}-a_{2}$

Supposons le résultat établi au rang $n,$ et soient $a_{1},\cdots,a_{n+1}\in\left]0,1\right[.$ Alors :

$\begin{eqnarray*}\left[\prod_{k=1}^{n}\left(1-a_{k}\right)\right]\left(1-a_{n+1}\right) & > & \left(1-\sum_{k=1}^{n}a_{k}\right)\left(1-a_{n+1}\right)\\& = & 1-\sum_{k=1}^{n+1}a_{k}+a_{n+1}\left(\sum_{k=1}^{n}a_{k}\right)\\& > & 1-\sum_{k=1}^{n+1}a_{k}\end{eqnarray*}$

On sait que si deux fonctions polynômes coïncident sur une partie infinie de $\mathbb{R},$ alors elles sont égales (autrement dit : elles coïncident en tout point). Il en résulte que, pour un $n$ donné, un tel polynôme est unique : en effet, si $Q$ et $R$ conviennent pour un même $n\in\mathbb{N},$ alors :

$\forall x\in\mathbb{R},\thinspace Q\left(\sin\left(x\right)\right)=\sin\left(nx\right)=R\left(\sin\left(x\right)\right)$

et donc :

$\forall t\in\left[-1,1\right],\thinspace Q\left(t\right)=R\left(t\right)$

Pour l’existence, on procède par récurrence. Il est clair que :

$\forall x\in\mathbb{R},\thinspace\sin\left(x\right)=\sin\left(x\right)Q_{0}\left(\cos\left(x\right)\right)\qquad\text{avec }Q_{0}=1$

$\forall x\in\mathbb{R},\sin\left(2x\right)=\sin\left(x\right)Q_{1}\left(\cos\left(x\right)\right)\qquad\text{avec }Q_{1}=2X$

Supposons (hypothèse de récurrence) que, pour un certain $n\geqslant1,$ il existe des polynômes $Q_{n-1}$ et $Q_{n}$ à coefficients entiers, tels que :

$\forall x\in\mathbb{R},\thinspace\left\{ \begin{array}{ccc}\sin\left(\left(n-1\right)x\right) & = & \sin\left(x\right)Q_{n-1}\left(\cos\left(x\right)\right)\\\\\sin\left(nx\right) & = & \sin\left(x\right)Q_{n}\left(\cos\left(x\right)\right)\end{array}\right.$

alors, d’après la …

Formule (transformation de somme en produit)

$\forall\left(a,b\right)\in\mathbb{R}^{2},\:\sin\left(a+b\right)+\sin\left(a-b\right)=2\sin\left(a\right)\cos\left(b\right)$

on voit que :

$\begin{eqnarray*}\sin\left(\left(n+1\right)x\right) & = & 2\sin\left(nx\right)\cos\left(x\right)-\sin\left(\left(n-1\right)x\right)\\& = & 2\sin\left(x\right)\cos\left(x\right)Q_{n}\left(\cos\left(x\right)\right)-\sin\left(x\right)Q_{n-1}\left(\cos\left(x\right)\right)\\& = & \sin\left(x\right)Q_{n+1}\left(\cos\left(x\right)\right)\end{eqnarray*}$

où l’on a posé : $Q_{n+1}=2XQ_{n}-Q_{n-1}.$ Manifestement, le polynôme $Q_{n+1}$ ainsi défini est à coefficients entiers.

Ce n’était pas demandé, mais il est possible d’expliciter $Q_{n}$ pour tout $n\in\mathbb{N}.$

On observe pour cela que, pour tout $n\in\mathbb{N}$ et pour tout $x\in\mathbb{R}$ :

$\begin{eqnarray*}\sin\left(\left(n+1\right)x\right) & = & \text{Im}\left(e^{i\left(n+1\right)x}\right)\end{eqnarray*}$

or, d’après la formule de Moivre :

$e^{i\left(n+1\right)x}=\left(e^{ix}\right)^{n+1}=\left(\cos\left(x\right)+i\sin\left(x\right)\right)^{n+1}$

puis celle du binôme :

$\left(\cos\left(x\right)+i\sin\left(x\right)\right)^{n+1}=\sum_{k=0}^{n+1}\binom{n+1}{k}\cos^{n+1-k}\left(x\right)\left(i\sin\left(x\right)\right)^{k}$

Dans cette dernière somme, les termes d’indices pairs sont réels et ceux d’indices impairs sont imaginaires purs; ainsi :

$\begin{eqnarray*}\sin\left(\left(n+1\right)x\right) & = & \sum_{p=0}^{\left\lfloor n/2\right\rfloor }\left(-1\right)^{p}\binom{n+1}{2p+1}\cos^{n-2p}\left(x\right)\sin^{2p+1}\left(x\right)\\& = & \sin\left(x\right)\sum_{p=0}^{\left\lfloor n/2\right\rfloor }\left(-1\right)^{p}\binom{n+1}{2p+1}\cos^{n-2p}\left(x\right)\left(1-\cos^{2}\left(x\right)\right)^{p}\\& = & \sin\left(x\right)Q_{n}\left(\cos\left(x\right)\right)\end{eqnarray*}$

avec :

$Q_{n}=\sum_{p=0}^{\left\lfloor n/2\right\rfloor }\left(-1\right)^{p}\binom{n+1}{2p+1}X^{n-2p}\left(1-X^{2}\right)^{p}$

ou encore :

$\boxed{Q_{n}=\sum_{p=0}^{\left\lfloor n/2\right\rfloor }\binom{n+1}{2p+1}X^{n-2p}\left(X^{2}-1\right)^{p}}$

Noter que cette preuve apporte aussi, mais sans récurrence, l’existence de $Q_{n}.$

Question 1

Calcul de $A_{n}$ pour $1\leqslant n\leqslant6$ :

Question 2

L’égalité $A_{n}=\frac{\left(-1\right)^{n-1}\left(2n+1\right)+1}{4}$ est vraie pour $n=1$ :

$A_{1}=1=\frac{\left(-1\right)^{0}\times3+1}{4}$

Supposons-la vraie pour un certain $n\geqslant1;$ alors :

$\begin{eqnarray*}A_{n+1} & = & A_{n}+\left(-1\right)^{n}\left(n+1\right)\\& = & \frac{\left(-1\right)^{n-1}\left(2n+1\right)+1}{4}+\left(-1\right)^{n}\left(n+1\right)\end{eqnarray*}$

c’est-à-dire :

$A_{n+1}=\frac{-\left(-1\right)^{n}\left(2n+1\right)+1+\left(-1\right)^{n}\left(4n+4\right)}{4}$

ou encore, comme souhaité :

$A_{n+1}=\frac{\left(-1\right)^{n}\left(2n+3\right)+1}{4}$

On a établi par récurrence que :

$\boxed{\forall n\in\mathbb{N}^{\star},\thinspace\sum_{k=1}^{n}\left(-1\right)^{k-1}k=\frac{\left(-1\right)^{n-1}\left(2n+1\right)+1}{4}}$

Question 3

Soit $n\in\mathbb{N}^{\star}.$ Distinguons deux cas selon la parité de $n.$ Si $n$ est pair, alors en posant $n=2p$ :

$\frac{\left(-1\right)^{n-1}\left(2n+1\right)+1}{4}=\frac{-\left(4p+1\right)+1}{4}=-p$

$\left(-1\right)^{n-1}\left\lfloor \frac{n+1}{2}\right\rfloor =-\left\lfloor p+\frac{1}{2}\right\rfloor =-p$

Et si $n$ est impair, alors en posant cette fois $n=2p+1$ :

$\frac{\left(-1\right)^{n-1}\left(2n+1\right)+1}{4}=\frac{2\left(2p+1\right)+1+1}{4}=p+1$

$\left(-1\right)^{n-1}\left\lfloor \frac{n+1}{2}\right\rfloor =\left\lfloor \frac{2p+2}{2}\right\rfloor =p+1$

On a ainsi montré que :

$\boxed{\forall n\in\mathbb{N}^{\star},\thinspace\sum_{k=1}^{n}\left(-1\right)^{k-1}k=\left(-1\right)^{n-1}\left\lfloor \frac{n+1}{2}\right\rfloor }$

On procède par récurrence. Pour $n=1,$ la formule proposée donne :

$-\frac{1}{x^{2}}f'\left(\frac{1}{x}\right)$

et elle est donc vérifiée.

Supposons-la établie au rang $n;$ alors pour tout $x>0$ :

$g^{\left(n+1\right)}\left(x\right)=\left(-1\right)^{n}\left(n-1\right)!\,\sum_{k=1}^{n}\,\frac{\binom{n}{k}}{\left(k-1\right)!}\left[-\frac{n+k}{x^{n+k+1}}f^{\left(k\right)}\left(\frac{1}{x}\right)-\frac{1}{x^{n+k+2}}f^{\left(k+1\right)}\left(\frac{1}{x}\right)\right]$

On sépare la somme en deux, puis on ré-indexe la seconde en posant $j=k+1$ :

$\begin{eqnarray*}g^{\left(n+1\right)}\left(x\right) & = & \left(-1\right)^{n+1}\left(n-1\right)!\,\left(\sum_{k=1}^{n}\,\frac{\binom{n}{k}\left(n+k\right)}{\left(k-1\right)!}\,\frac{1}{x^{n+k+1}}\,f^{\left(k\right)}\left(\frac{1}{x}\right)\right.\\& & \left.+\sum_{j=2}^{n+1}\,\frac{\binom{n}{j-1}}{\left(j-2\right)!}\,\frac{1}{x^{n+j+1}}\,f^{\left(j\right)}\left(\frac{1}{x}\right)\right)\end{eqnarray*}$

On isole alors, dans la première somme, le terme d’indice $1$ et, dans la seconde, celui d’indice $n+1;$ puis on fusionne ce qui reste en une seule somme. On obtient ainsi :

$\begin{eqnarray*}g^{\left(n+1\right)}\left(x\right) & = & \left(-1\right)^{n+1}\left(n-1\right)!\,\left(\frac{n\left(n+1\right)}{x^{n+2}}f'\left(\frac{1}{x}\right)+\frac{1}{\left(n-1\right)!\,x^{2n+2}}f^{\left(n+1\right)}\left(\frac{1}{x}\right)+\right.\\& & \left.\sum_{k=2}^{n}\,\frac{1}{\left(k-1\right)!}\left[\left(n+k\right)\binom{n}{k}+\left(k-1\right)\binom{n}{k-1}\right]\,\frac{1}{x^{n+k+1}}\,f^{\left(k\right)}\left(\frac{1}{x}\right)\right)\end{eqnarray*}$

Or :

$\begin{eqnarray*}\left(n+k\right)\binom{n}{k}+\left(k-1\right)\binom{n}{k-1} & = & n!\,\left(\frac{n+k}{k!\,\left(n-k\right)!}+\frac{k-1}{\left(k-1\right)!\,\left(n-k+1\right)!}\right)\\& = & \frac{n!\left[\left(n+k\right)\left(n-k+1\right)+k\left(k-1\right)\right]}{k!\,\left(n-k+1\right)!}\\& = & n\,\binom{n+1}{k}\end{eqnarray*}$

donc :

$\begin{eqnarray*}g^{\left(n+1\right)}\left(x\right) & = & \left(-1\right)^{n+1}n!\left(\frac{n+1}{x^{n+2}}f'\left(\frac{1}{x}\right)+\frac{1}{n!\,x^{2n+2}}f^{\left(n+1\right)}\left(\frac{1}{x}\right)\right.\\& & \left.+\sum_{k=2}^{n}\,\frac{\binom{n+1}{k}}{\left(k-1\right)!\,x^{n+1+k}}\,f^{\left(k\right)}\left(\frac{1}{x}\right)\right)\end{eqnarray*}$

soit finalement :

$g^{\left(n+1\right)}\left(x\right)=\left(-1\right)^{n+1}n!\,\sum_{k=1}^{n+1}\,\frac{\binom{n+1}{k}}{\left(k-1\right)!\,x^{n+1+k}}\,f^{\left(k\right)}\left(\frac{1}{x}\right)$

ce qui établit la formule au rang $n+1.$

On va établir la proposition suivante :

Soit $n\in\mathbb{N}^{\star}$ et soient $d_{1},\cdots,d_{q}$ ses diviseurs. Notons $m_{i}$ le nombre de diviseurs de $d_{i}.$ Alors :

$\sum_{i=1}^{q}m_{i}^{3}=\left(\sum_{i=1}^{q}m_{i}\right)^{2}$

On raisonne par récurrence sur le nombre $r$ de facteurs premiers de $n.$

Pour $r=1,$ il existe $p\in\mathbb{P}$ et $\alpha\in\mathbb{N}^{\star}$ tels que $n=p^{\alpha}.$ La liste des diviseurs de $n$ est alors :

$1,p,\cdots,p^{\alpha}$

et celle des nombres de diviseurs de chacun d’eux est :

$1,2,\cdots,\alpha+1$

Or il est classique que ${\displaystyle \sum_{i=1}^{\alpha+1}i^{3}=\left(\sum_{i=1}^{\alpha+1}i\right)^{2}};$ la propriété voulue est donc établie au rang $r=1.$

Supposons la établie au rang $r,$ pour un certain $r\in\mathbb{N}^{\star}.$

Soit alors un entier naturel $n$ possédant $r+1$ facteurs premiers. On peut écrire $n=Np^{\alpha}$ avec $N$ possédant $r$ facteurs premiers, $p\in\mathbb{P},$ $\alpha\in\mathbb{N}^{\star}$ et $N\wedge p=1.$

Notons $d_{1},\cdots,d_{q}$ les diviseurs de $N,$ et $m_{i}$ le nombre de diviseurs de $d_{i},$ pour tout $i\in\left\{ 1,\cdots,r\right\} .$

Les diviseurs de $n$ sont alors les $d_{i}p^{j}$ pour $\left(i,j\right)\in\left\{ 1,\cdots,q\right\} \times\left\{ 0,\cdots,\alpha\right\} ;$ et le nombre de diviseurs de $d_{i}p^{j}$ est $m_{i}\left(j+1\right).$
On constate alors que :

$\begin{eqnarray*}\sum_{i=1}^{q}\left(\sum_{j=0}^{\alpha}\left(m_{i}\left(j+1\right)\right)^{3}\right) & = & \left(\sum_{i=1}^{q}m_{i}^{3}\right)\left(\sum_{j=1}^{\alpha+1}j^{3}\right)\\& \underset{{\scriptstyle {HR}}}{=} & \left(\sum_{i=1}^{q}m_{i}\right)^{2}\left(\sum_{j=1}^{\alpha+1}j\right)^{2}\\& = & \left[\sum_{i=1}^{q}\left(\sum_{j=0}^{\alpha}m_{i}\left(j+1\right)\right)\right]^{2}\end{eqnarray*}$

Ce résultat est attribué au mathématicien français Joseph Liouville (1809 – 1882).

Si un point n’est pas clair ou vous paraît insuffisamment détaillé, n’hésitez pas à poster un commentaire ou à me joindre via le formulaire de contact.

Partager cet article