Question about an inequality.

81 Views Asked by At

$$\forall i\in \{1,2,\cdots, k\}, n_i\in\mathbb{N}$$ $$\sum_{i=1}^k n_i =n$$ then $$\sum_{i=1}^k n_i^2\leq n^2-(k-1)(2n-k)$$


Like comment, If we apply induction,

$i)\ k=2$

$n_1+n_2=n\land n_1,n_2\in \mathbb{N}$

then $$n_1^2+n_2^2=n_1^2+(n-n_1)^2=n^2-2n_1n+2n_1^2=2(n_1-\frac{n}{2})^2+\frac{n^2}{2}$$

Actually this have maximum if $|n_1-\frac{n}{2}|$ is maximum(when $n_1=1 \lor n_1=n-1$) therefore $$n_1^2+n_2^2\leq 1^2+(n-1)^2= n^2-1*(2n-2)$$

ii)for induction,

suppose $\sum_{i=1}^k n_i=n\land n_i\in \mathbb{N}$ imply $$\sum_{i=1}^k n_i^2\leq n^2-(k-1)(2n-k)$$

and

claim:$\sum_{i=1}^{k+1} n_i=n\land n_i\in \mathbb{N}$ imply $$\sum_{i=1}^{k+1} n_i^2\leq n^2-k(2n-k-1)$$ $$\sum_{i=1}^{k+1} n_i^2=\sum_{i=1}^k n_i^2+n_{k+1}^2\leq (n-n_{k+1})^2-(k-1)(2n-2n_{k+1}-k)+n_{k+1}^2$$ $$=2n_{k+1}^2-2n_{k+1}(n-k+1)+n^2-2n(k-1)+k(k-1)$$ $$=2(n_{k+1}-\frac{n-k+1}{2})^2-\frac{(n-k+1)^2}{2}+n^2-2n(k-1)+k(k-1)$$

Actually It have maximum if $|n_{k+1}-\frac{n-k+1}{2}|$ is maximum, (at $n_{k+1}=1\lor n-k$) therefore $$\leq \frac{(n-k-1)^2}{2}-\frac{(n-k+1)}{2}+n^2-2n(k-1)+k(k-1)$$ $$=-2(n-k)+n^2-2n(k-1)+(k-1)k$$ $$=n^2-k(2n-k-1)$$

therefore $$\sum_{i=1}^k n_i^2\leq n^2-(k-1)(2n-k)$$ and equality occur when $\forall i= 1,2,\cdots,k-1 ,n_i=1,n_k=n-k+1$

1

There are 1 best solutions below

0
On

Let $m = \min n_i$ and $M = \max n_i$. We are told $n_i \ge 1$ (i.e. $\mathbb{N}$ stands for the set of positive integers), so $m \ge 1$ and hence $$M \le n - (k-1)m \le n - k + 1$$

This leads to

$$\begin{align} \sum_i n_i^2 &= \sum_i ((n_i+1)(n_i-1) + 1) \le (M+1)\sum_i (n_i - 1) + k\\ &\le (n - k + 2)(n-k) + k = n^2 - (k-1)(2n-k) \end{align}\tag{*1} $$ This is the inequality we want to prove. We can improve this inequality by using the actual maximum $M$ and minimum $m$. We have

$$\begin{align} \sum_i n_i^2 &= \sum_i ((n_i+m)(n_i-m) + m^2) \le (M+m)\sum_i (n_i - m) + km^2\\ &\le (M+m)(n - km) + km^2 = (M+m)n - kMm \end{align} $$ Let $\mu = \frac{n}{k}$ and $\sigma$ be the mean and standard derivation of $n_i$. Above inequality is equivalent to

$$k (\sigma^2 + \mu^2) \le (M+m)\mu k - kMm \quad\iff\quad \sigma^2 \le (M - \mu)(\mu - m)\tag{*2}$$

When we replace $M$ and $m$ by other upper/lower bounds for $n_i$, $(M - \mu)(\mu - m)$ will only getting bigger and inequality $(*2)$ remains valid. The inequality $(*1)$ is really a special case of this when we replace $M, m$ by $n-k+1$ and $1$.

The inequality on RHS$(*2)$ is known as Bhatia–Davis inequality. Look at its wiki entry for similar bounds.