Démonstration d’une inégalité

Je vais présenter ici une solution de l’exercice proposé dans l’article précédent. Bien qu’elle ne soit guère compliquée, elle prend un peu de place et se serait avérée difficile à rédiger si j’avais voulu l’écrire dans un commentaire. Les commodités d’édition des commentaires sont en effet moins riches que celles disponibles pour les articles.

Voici d’abord une propriété utilisée dans cette solution et dont l’exercice est une sorte de généralisation.

(1) Soient des nombres réels positifs ou nuls u_0,\ldots,u_p tels que u_0+\cdots+u_p\leqslant q. On a

\sum_{r=1}^pru_r\leq pq

l’égalité ayant lieu si, et seulement si, u_0=\cdots=u_{p-1}=0 et u_p=q.

Vérifions cela.

Supposons donc que les u sont positifs ou nuls et que leur somme est inférieure ou égale à q. On a alors les inégalités u_r+\cdots+u_p\leqslant q, r\in\{1,\ldots,p\}. En les additionnant membre à membre, on obtient l’inégalité annoncée. De plus, c’est une égalité si, et seulement si, chacune des inégalités additionnées est une égalité, ce qui a lieu exactement lorsque u_p=q et u_r=0 pour 0< r<p. On obtient ensuite u_0=0 en imposant à la somme des u de ne pas dépasser q.

Pour le reste de l’article, k_0,\ldots,k_n sont des entiers positifs ou nuls vérifiant(*)

(2) \begin{cases}k_0+\cdots+k_n\leqslant n-1\\k_1+2k_2+\cdots+nk_n=n^2-n-i\end{cases}

pour un certain i\in\{0,\ldots,n\}.

Première observation

Nous allons constater que les k dont les indices sont strictement inférieurs à n-i sont nuls(**). Pour ce faire, nous écrivons

k_1+2k_2+\cdots+nk_n=\underbrace{k_1+\cdots+(n-i-1)k_{(n-i-1)}}_{A}+(n-i)k_{(n-i)}+\cdots+nk_n

et nous appliquons (1) à A, ce qui donne successivement, compte tenu de (2),

\begin{array}{rcl}n^2-n-i&\leqslant& (n-i-1)(k_0+\cdots+k_{n-i-1})+(n-i)k_{n-i}+\cdots+nk_n\\[1ex]&\leqslant&(n-i-1)(n-1-k_{n-i}-\cdots-k_n)+(n-i)k_{n-i}+\cdots+nk_n\\[1ex]&\leqslant&(n-i-1)(n-1)+\underbrace{k_{n-i}+2k_{n-i+1}+\cdots+(i+1)k_n}_B\end{array}

Si les k d’indices strictement inférieurs à n-i ne sont pas tous nuls, alors k_{n-i}+\cdots+k_n\leqslant n-2 et, en appliquant (1) à B, on obtient

n^2-n-i\leqslant (n-i-1)(n-1)+(n-2)(i+1)=n^2-n-(i+1)

une contradiction. On a ainsi prouvé que k_r=0 pour r<n-i.

Deuxième observation

L’observation suivante consiste à noter que si i=0, alors k_n=n-1. C’est une application immédiate de (1) avec p=n et q=n-1.

Dernière observation

On suppose cette fois que i>0 et k_{n-i}\neq 0. On va alors montrer que k_{n-i}=1, k_r=0 pour n-i<r<n et k_n=n-2.

Par la première observation, nous savons déjà que k_0=\cdots=k_{n-i-1}=0. D’ailleurs, en prouvant celle-ci, nous avons obtenu l’inégalité n^2-n-i\leqslant (n-i-1)(n-1)+B que nous réécrivons sous la forme

(i+1)(n-1)-i\leqslant \underbrace{k_{n-i}+\cdots+k_n}_C+\underbrace{k_{n-i+1}+2k_{n-i+2}+\cdots + ik_n}_D

Mais, compte tenu de (2), d’une part, C\leqslant n-1 et, d’autre part, en appliquant(***) (1), D\leqslant i(n-1-k_{n-i}). Dès lors

(i+1)(n-1)-i\leqslant (i+1)(n-1)-ik_{n-i}

Autrement dit k_{n-i}\leqslant 1. Comme nous supposons k_{n-i} non nul, il vaut donc 1. Mais alors, C=n-1 et, surtout, D=i(n-1-k_{n-i}). D’après la condition d’égalité énoncée dans (1), cette dernière égalité implique que k_r=0 pour n-i<r<n et k_n=n-1-k_{n-i}=n-2.

L’exercice du billet précédent est ainsi résolu. Je n’ai pas trouvé de propriétés significatives des solutions du système (2) pour les valeurs de i supérieures à n et des expérimentations réalisées avec mon esclave me donnent à penser qu’il n’y en a pas.

P.S. En examinant des exemples, je viens de faire une observation supplémentaire : si i <n, dans une solution (k_0,\ldots,k_n) de (2), la somme des k est toujours maximale, i. e. égale à n-1. Ce n’est pas vrai lorsque i=n puisque dans ce cas, (0,\ldots,0,n-2) est une solution. Je donnerai dans un commentaire la vérification de cette observation supplémentaire. P.L. 26/08/2014
__________
(*) Il est entendu que n\geqslant 1.
(**) Il y a de tels k pour autant que i soit plus petit que n.
(***) On prend p=i, u_0=0, u_1=k_{n-i+1},\ldots, u_i=k_n et q=n-1-k_{n-i}.

Une réflexion sur “Démonstration d’une inégalité

  1. Voici une preuve possible de la propriété donnée en post scriptum. Supposons que la somme des k d’une solution de (2) soit strictement plus petite que n-1. Alors, sachant déjà que k_r=0 pour r<n-i, il vient

    \begin{array}{rcl}n^2-n-i&=&(n-i)\sum_{r=n-i}^nk_r+\sum_{r=1}^irk_{n-i+r}\\[1ex]&\leqslant& (n-i)(n-2)+i(n-2)\\[1ex]&=&n^2-2n\end{array}

    soit i\geqslant n.

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s