Solutions - Exercices sur la récurrence - 02

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

Quelques essais conduisent à conjecturer que :

$\boxed{\forall n\in\mathbb{N}^{\star},\thinspace\forall x\geqslant0,\thinspace f^{n}\left(x\right)=\frac{F_{n}+F_{n-1}x}{F_{n+1}+F_{n}x}}$

où $F_{n}$

désigne le $n-$

ème nombre de Fibonacci. On rappelle que, par définition :

$\boxed{F_{0}=0,\qquad F_{1}=1,\qquad\forall n\in\mathbb{N}^{\star},\thinspace F_{n+1}=F_{n}+F_{n-1}}$

On vérifie cette conjecture par récurrence. L’initialisation consiste à voir que :

$\forall x\geqslant0,\thinspace f^{1}\left(x\right)=\frac{F_{1}+F_{0}x}{F_{2}+F_{1}x}$

ce qui est vrai. Ensuite, supposons la formule vraie au rang $n$

pour un certain $n\geqslant1.$

Alors, pour tout $x\geqslant0$ :

$\begin{eqnarray*}f^{n+1}\left(x\right) & = & f\left(f^{n}\left(x\right)\right)\\& = & \frac{1}{1+f^{n}\left(x\right)}\\& = & \frac{1}{1+\frac{F_{n}+F_{n-1}x}{F_{n+1}+F_{n}x}}\\& = & \frac{F_{n+1}+F_{n}x}{\left(F_{n+1}+F_{n}\right)+\left(F_{n}+F_{n-1}\right)x}\end{eqnarray*}$

c’est-à-dire, comme souhaité :

$f^{n+1}\left(x\right)=\frac{F_{n+1}+F_{n}x}{F_{n+2}+F_{n+1}x}$

Le réel $x$ étant fixé, on observe que cette inégalité est évidente pour $n=0$ et pour $n=1.$

Supposons-la vraie aux rangs $n-1$ et $n$ pour un certain $n\geqslant1.$ Comme :

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

il vient par inégalité triangulaire et d’après l’hypothèse de récurrence :

$\begin{eqnarray*}\left|\sin\left(\left(n+1\right)x\right)\right| & \leqslant & \left|\sin\left(nx\right)\right|\thinspace\left|\cos\left(x\right)\right|+\left|\cos\left(nx\right)\right|\thinspace\left|\sin\left(x\right)\right|\\& \leqslant & \left|\sin\left(nx\right)\right|+\left|\sin\left(x\right)\right|\\& \leqslant & n\left|\sin\left(x\right)\right|+\left|\sin\left(x\right)\right|\\& = & \left(n+1\right)\left|\sin\left(x\right)\right|\end{eqnarray*}$

On commence par calculer $S_{n}$ pour de petites valeurs de $n$ :

$S_{1}=1$

$S_{2}=\frac{1}{1}+\frac{1}{2}+\frac{1}{1\times2}=2$

$S_{3}=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\frac{1}{1\times2}+\frac{1}{1\times3}+\frac{1}{2\times3}+\frac{1}{1\times2\times3}=3$

Montrons par récurrence que $S_{n}=n,$ pour tout $n\geqslant1.$ L’initialisation étant (largement) faite, passons à l’hérédité.

On suppose donc l’égalité établie au rang $n.$

L’ensemble des parties non vides de $\mathbb{N}_{n+1}$ est l’union disjointe de l’ensemble des parties non vides de $\mathbb{N}_{n}$ et de l’ensemble des parties de $\mathbb{N}_{n+1}$ qui contiennent $n+1.$

De plus les parties de $\mathbb{N}_{n+1}$ qui contiennent $n+1$ sont exactement les $X\cup\left\{ n+1\right\}$ où $X$ parcourt $\mathcal{P}\left(\mathbb{N}_{n}\right).$ Donc :

$\begin{eqnarray*}\sum_{X\in\mathcal{P}\left(\mathbb{N}_{n+1}\right)-\left\{ \emptyset\right\} }\frac{1}{f\left(X\right)} & = & \sum_{X\in\mathcal{P}\left(\mathbb{N}_{n}\right)-\left\{ \emptyset\right\} }\frac{1}{f\left(X\right)}\\& & +\frac{1}{n+1}\thinspace\left(1+\sum_{X\in\mathcal{P}\left(\mathbb{N}_{n}\right)-\left\{ \emptyset\right\} }\frac{1}{f\left(X\right)}\right)\\& = & n+\frac{1}{n+1}\left(1+n\right)=n+1\end{eqnarray*}$

Calculons de deux façons la somme :

$\Delta\left(n,p\right)=\sum_{k=1}^{n}\left(\left(k+1\right)^{p+1}-k^{p+1}\right)$

D’une part, par « télescopage des termes » :

$\Delta\left(n,p\right)=\left(n+1\right)^{p+1}-1$

D’autre part, la formule du binôme appliquée à $\left(k+1\right)^{p+1}$

donne :

$\left(k+1\right)^{p+1}=\sum_{j=0}^{p+1}\binom{p+1}{j}k^{j}$

et donc :

$\left(k+1\right)^{p+1}-k^{p+1}=\sum_{j=0}^{p}\binom{p+1}{j}k^{j}$

d’où, en reportant :

$\Delta\left(n,p\right)=\sum_{k=1}^{n}\sum_{j=0}^{p}\binom{p+1}{j}k^{j}$

En intervertissant les deux sommations, on obtient :

$\Delta\left(n,p\right)=\sum_{j=0}^{p}\sum_{k=1}^{n}\binom{p+1}{j}k^{j}=\sum_{j=0}^{p}\binom{p+1}{j}S_{j}\left(n\right)$

La confrontation des deux expressions obtenues pour $\Delta\left(n,p\right)$

donne :

$\boxed{\sum_{j=0}^{p}\binom{p+1}{j}S_{j}\left(n\right)=\left(n+1\right)^{p+1}-1}$

Il s’agit d’une formule de récurrence forte donnant $S_{p}\left(n\right)$

en fonction des $S_{j}\left(n\right)$

pour $0\leqslant j<p$

$S_{p}\left(n\right)=\frac{1}{p+1}\left[\left(n+1\right)^{p+1}-1-\sum_{j=0}^{p-1}\binom{p+1}{j}S_{j}\left(n\right)\right]\qquad\left(\star\right)$

Vu que $S_{0}\left(n\right)=n,$

on peut affirmer que $S_{0}$

est polynomiale de degré 1.

Supposons établi que, pour un certain $p\geqslant1$ et pour chaque $j\in\left\{ 0,\cdots,p-1\right\} ,$ $S_{j}$ est polynomiale de degré $j+1.$ La formule $\left(\star\right)$ montre alors que $S_{p}$ est polynomiale de degré $p+1$ (en effet, l’expression $\left(n+1\right)^{p+1}-1$ est de degré $p+1$ en $n,$ et la somme qui suit à l’intérieur du crochet est une combinaison linéaire d’expressions polynomiales de degrés $\leqslant p).$

Enfin, l’unicité de $S_{p}$ résulte du fait que deux fonctions polynomiales qui coïncident sur un ensemble infini (ici : $\mathbb{N}^{\star})$ sont identiques.

Notons $\mathcal{A}_{n}$ l’assertion :

$\boxed{\forall\left(x_{1},\cdots,x_{n}\right)\in\mathbb{R}^{n},\thinspace\forall\left(y_{1},\cdots,y_{n}\right)\in\mathbb{R}^{n},\thinspace\left(\sum_{i=1}^{n}x_{i}y_{i}\right)^{2}\leqslant\left(\sum_{i=1}^{n}x_{i}^{2}\right)\left(\sum_{i=1}^{n}y_{i}^{2}\right)}$

D’évidence, $\mathcal{A}_{1}$

est vraie.

Supposons $\mathcal{A}_{n}$ vraie pour un certain entier $n\geqslant1$ et soient alors $a_{1},\cdots,a_{n+1},b_{1},\cdots,b_{n+1}\in\mathbb{R}.$

D’une part :

$\begin{eqnarray*}\left(\sum_{i=1}^{n+1}a_{i}b_{i}\right)^{2} & = & \left[\left(\sum_{i=1}^{n}a_{i}b_{i}\right)+a_{n+1}b_{n+1}\right]^{2}\\& = & \left(\sum_{i=1}^{n}a_{i}b_{i}\right)^{2}+2a_{n+1}b_{n+1}\left(\sum_{i=1}^{n}a_{i}b_{i}\right)+a_{n+1}^{2}b_{n+1}^{2}\end{eqnarray*}$

et d’autre part :

$\begin{eqnarray*}\left(\sum_{i=1}^{n+1}\,a_{i}^{2}\right)\left(\sum_{i=1}^{n+1}\,b_{i}^{2}\right) & = & \left[\left(\sum_{i=1}^{n}\,a_{i}^{2}\right)+a_{n+1}^{2}\right]\left[\left(\sum_{i=1}^{n}\,b_{i}^{2}\right)+b_{n+1}^{2}\right]\\& = & \left(\sum_{i=1}^{n}\,a_{i}^{2}\right)\left(\sum_{i=1}^{n}\,b_{i}^{2}\right)+a_{n+1}^{2}\left(\sum_{i=1}^{n}\,b_{i}^{2}\right)+b_{n+1}^{2}\left(\sum_{i=1}^{n}\,a_{i}^{2}\right)+a_{n+1}^{2}b_{n+1}^{2}\end{eqnarray*}$

Compte tenu de l’hypothèse de récurrence, il suffit de prouver que :

$a_{n+1}^{2}\left(\sum_{i=1}^{n}\,b_{i}^{2}\right)+b_{n+1}^{2}\left(\sum_{i=1}^{n}\,a_{i}^{2}\right)-2a_{n+1}b_{n+1}\left(\sum_{i=1}^{n}a_{i}b_{i}\right)\geqslant0\qquad\left(\spadesuit\right)$

Or, pour tout $i\in\llbracket1,n\rrbracket$

$a_{n+1}^{2}b_{i}^{2}+b_{n+1}^{2}a_{i}^{2}-2a_{n+1}b_{n+1}a_{i}b_{i}=\left(a_{n+1}b_{i}-b_{n+1}a_{i}\right)^{2}\geqslant0$

et l’on obtient $\left(\spadesuit\right)$

en sommant ces inégalités.

Pour $n=2,$ c’est la définition de la convexité.

Supposons le résultat établi pour un certain $n\geqslant2$ et soient alors $x_{1},\cdots,x_{n+1}\in I$ ainsi que $t_{1},\cdots,t_{n+1}\geqslant0$ tels que $\sum_{i=1}^{n+1}t_{i}=1.$ Posons :

$T=\sum_{i=1}^{n}t_{i}$

de sorte que $T\in\left[0,1\right]$

et $t_{n+1}=1-T.$

En supposant $t_{n+1}\neq1,$ on observe que :

$\sum_{i=1}^{n+1}t_{i}x_{i}=T\left(\sum_{i=1}^{n}\frac{t_{i}}{T}x_{i}\right)+\left(1-T\right)x_{n+1}$

d’où par convexité de $f$

$f\left(\sum_{i=1}^{n+1}t_{i}x_{i}\right)\leqslant T\thinspace f\left(\sum_{i=1}^{n}\frac{t_{i}}{T}x_{i}\right)+\left(1-T\right)\thinspace f\left(x_{n+1}\right)$

On peut ensuite appliquer l’hypothèse de récurrence, car les réels $t_{i}/T$

pour $1\leqslant i\leqslant n$

sont positifs et de somme $1,$

ce qui donne :

$f\left(\sum_{i=1}^{n+1}t_{i}x_{i}\right)\leqslant T\thinspace\sum_{i=1}^{n}\frac{t_{i}}{T}f\left(x_{i}\right)+\left(1-T\right)\thinspace f\left(x_{n+1}\right)$

c’est-à-dire :

$f\left(\sum_{i=1}^{n+1}t_{i}x_{i}\right)\leqslant\sum_{i=1}^{n+1}t_{i}\thinspace f\left(x_{i}\right)$

Pour finir, cette inégalité est triviale si $t_{n+1}=1$

car alors $t_{i}=0$

pour tout $i\in\llbracket1,n\rrbracket.$

Soit $u\in\mathcal{L}\left(E\right).$ Montrons que l’assertion suivante est vraie pour tout entier $r\geqslant1$ :

Assertion $\mathcal{A}_{r}$

Quels que soient les vecteurs propres $x_{1},\cdots,x_{r}$ (pour $u)$ associés à des valeurs propres $\lambda_{1},\cdots,\lambda_{r}$ toutes distinctes, la famille $\left(x_{1},\cdots,x_{r}\right)$ est libre.

Pour $r=1,$ aucun problème puisqu’une famille réduite à un seul vecteur non nul est libre.

Supposons le résultat établi au rang $r,$ pour un certain $r\in\mathbb{N}^{\star}.$

Soient alors $\lambda_{1},\cdots,\lambda_{r+1}$ des valeurs propres de $u,$ deux à deux distinctes et soient $x_{1},\cdots,x_{r+1}$ des vecteurs propres respectivement associés aux $\lambda_{i}.$

Considérons des scalaires $\alpha_{1},\cdots,\alpha_{r+1}$ tels que :

(1) $\sum_{i=1}^{r+1}\alpha_{i}x_{i}=0_{E}$

En appliquant $u,$

il vient :

(2) $\sum_{i=1}^{r+1}\alpha_{i}\lambda_{i}x_{i}=0_{E}$

Puis, en effectuant (2) – $\lambda_{r+1}$

(1) :

$\sum_{i=1}^{r}\alpha_{i}\left(\lambda_{i}-\lambda_{r+1}\right)x_{i}=0_{E}$

D’après l’hypothèse de récurrence, la famille $\left(x_{1},\cdots,x_{r}\right)$

est libre et donc :

$\forall i\in\llbracket1,r\rrbracket,\thinspace\alpha_{i}\left(\lambda_{i}-\lambda_{r+1}\right)=0$

Ceci impose $\alpha_{i}=0$ pour tout $i\in\llbracket1,r\rrbracket.$

Enfin, en reportant dans (1) et compte tenu de $x_{r+1}\neq0_{E},$ on obtient $\lambda_{r+1}=0.$

La famille $\left(x_{1},\cdots,x_{r+1}\right)$ est donc libre, comme souhaité.

Montrons par récurrence que l’assertion $\mathcal{A}_{n}$ suivante est vraie pour tout $n\geqslant1$ :

Pour toute famille $\left(x_{1},\cdots,x_{n}\right)\in E^{n},$ si les vecteurs $y_{1},\cdots,y_{n+1}$ sont tous combinaisons linéaires de $x_{1},\cdots,x_{n}$ alors la famille $\left(y_{1},\cdots,y_{n+1}\right)$ est liée.

Pour $n=1,$ c’est simple : si $y_{1}=\lambda_{1}x_{1}$ et $y_{2}=\lambda_{2}x_{1},$ alors $\left(y_{1},y_{2}\right)$ est liée. En effet, c’est évident
si $\lambda_{1}=\lambda_{2}=0;$ et sinon, cela résulte de $\lambda_{2}y_{1}-\lambda_{1}y_{2}=0_{E}.$

Supposons la propriété établie au rang $n$ et soient alors $x_{1},\cdots,x_{n+1}$ des vecteurs de $E$ et $y_{1},\cdots,y_{n+2}$ des combinaisons linéaires des $x_{i}.$ On dispose pour chaque $i\in\left\{ 1,\cdots,n+2\right\}$ d’une expression de $y_{i}$ de la forme :

$y_{i}=\sum_{j=1}^{n+1}\,\lambda_{i,j}\,x_{j}\qquad\qquad\left(\blacksquare_{i}\right)$

Si $\forall i\in\left\{ 1,\cdots,n+2\right\} ,\,\lambda_{i,n+1}=0,$

alors les $y_{i}$

sont en fait combinaisons linéaires de $x_{1},\cdots,x_{n}$

seulement. Dans ce cas, l’hypothèse de récurrence montre que $\left(y_{1},\cdots,y_{n+1}\right)$

est liée et, à plus forte raison, $\left(y_{1},\cdots,y_{n+2}\right)$

est liée.

Sinon, $\exists i\in\left\{ 1,\cdots,n+2\right\} ;\,\lambda_{i,n+1}\neq0.$

Quitte à ré-indexer, on peut supposer pour simplifier que $\lambda_{1,n+1}\neq0.$ Il vient alors, d’après $\left(\blacksquare_{1}\right)$ :

$x_{n+1}=\frac{1}{\lambda_{1,n+1}}\left(y_{1}-\sum_{j=1}^{n}\,\lambda_{1,j}\,x_{j}\right)$

D’où, en remplaçant dans $\left(\blacksquare_{i}\right),$

pour $i\in\left\{ 2,\cdots,n+2\right\}$

$y_{i}=\sum_{j=1}^{n}\,\lambda_{i,j}\,x_{j}+\frac{\lambda_{i,n+1}}{\lambda_{1,n+1}}\left(y_{1}-\sum_{j=1}^{n}\,\lambda_{1,j}\,x_{j}\right)$

Par conséquent, en posant :

$\forall i\in\left\{ 2,\cdots,n+2\right\} ,\,z_{i}=y_{i}-\frac{\lambda_{i,n+1}}{\lambda_{1,n+1}}y_{1}$

on constate que $z_{2},\cdots,z_{n+2}$

sont combinaisons linéaires de $x_{1},\cdots,x_{n}.$

L’hypothèse de récurrence montre alors que $\left(z_{2},\cdots,z_{n+2}\right)$

est liée :

$\exists\left(\mu_{2},\cdots,\mu_{n+2}\right)\in\mathbb{\mathbb{K}}^{n+1}-\left\{ \left(0,\cdots,0\right)\right\} ;\,\sum_{i=2}^{n+2}\,\mu_{i}\,z_{i}=0_{E}$

Mais cette dernière égalité s’écrit aussi :

$\alpha\,y_{1}-\sum_{i=2}^{n+2}\,\mu_{i}\,y_{i}=0_{E}$

où l’on a posé

$\alpha=\sum_{i=2}^{n+2}\,\mu_{i}\frac{\lambda_{i,n+1}}{\lambda_{1,n+1}}$

La famille $\left(y_{1}\cdots,y_{n+2}\right)$

est donc liée.

Soient $x_{1},x_{2}>0.$ L’inégalité $\left(\sqrt{x_{1}}-\sqrt{x_{2}}\right)^{2}\geqslant0$ donne, après développement :
$\sqrt{x_{1}x_{2}}\leqslant\frac{x_{1}+x_{2}}{2}$
On notera $G$ la moyenne géométrique de $x_{1},\cdots,x_{n+1}$ :
$G=\left(\prod_{i=1}^{n+1}x_{i}\right)^{1/\left(n+1\right)}$

a) Si $x_{i}=A$ pour tout $i,$ alors $G=A.$

b) Par hypothèse, il existe $i\in\left\{ 1,\cdots,n+1\right\}$ tel que $x_{i}\neq A.$

Supposons par exemple $x_{i}<A.$ Si l’on avait $x_{j}\leqslant A$ pour tout $j\in\left\{ 1,\cdots,n+1\right\} -\left\{ i\right\} ,$ il en résulterait (par sommation d’inégalités) :

$\sum_{k=1}^{n+1}x_{k}<\left(n+1\right)A$

ce qui est absurde (par définition de $A).$

Il existe donc $j$ tel que $x_{j}>A.$

c) Avec ce qui précède, on voit que $\left(A-x_{i}\right)\left(x_{j}-A\right)>0,$ c’est-à-dire

$A\left(x_{i}+x_{j}\right)-A^{2}-x_{i}x_{j}>0$

ou encore :

$A\left(x_{i}+x_{j}-A\right)>x_{i}x_{j}$

d) On peut toujours supposer $i<j,$ quitte à échanger les termes $x_{i}$ et $x_{j}$ dans la liste (ce n’est pas essentiel mais cela va simplifier la présentation). L’hypothèse de récurrence appliquée à la liste $\left(x_{1},\cdots,x_{i-1},x_{i+1},\cdots,x_{j-1},x_{j+1},\cdots,x_{n+1},x_{i}+x_{j} A\right)$ donne :

$\begin{eqnarray*}& \left(x_{1}\cdots x_{i-1}x_{i+1}\cdots x_{j-1}x_{j+1}\cdots x_{n+1}\left(x_{i}+x_{j}-A\right)\right)^{1/n} &\\& \leqslant &\\& \frac{1}{n}\left(x_{1}+\cdots+x_{i-1}+x_{i+1}+\cdots+x_{j-1}+x_{j+1}+\cdots+x_{n+1}+\left(x_{i}+x_{j}-A\right)\right) &\end{eqnarray*}$

Dans cette dernière inégalité, le membre de droite (on devrait dire « le membre du haut », mais bon) vaut :

$\frac{1}{n}\left(\left(n+1\right)A-A\right)=A$

On a donc, en élevant à la puissance $n$

$G^{n+1}\thinspace\frac{x_{i}+x_{j}-A}{x_{i}x_{j}}\leqslant A^{n}$

donc, d’après le point c) :

$\frac{G^{n+1}}{A}\leqslant A^{n}$

et finalement $G\leqslant A,$

comme souhaité.

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

Laisser un commentaire Annuler la réponse