Question about an inequality.
up vote
0
down vote
favorite
$$forall iin {1,2,cdots, k}, n_iinmathbb{N}$$ $$sum_{i=1}^k n_i =n$$
then
$$sum_{i=1}^k n_i^2leq n^2-(k-1)(2n-k)$$
Like comment, If we apply induction,
$i) k=2$
$n_1+n_2=nland n_1,n_2in 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^2leq 1^2+(n-1)^2= n^2-1*(2n-2)$$
ii)for induction,
suppose $sum_{i=1}^k n_i=nland n_iin mathbb{N}$
imply
$$sum_{i=1}^k n_i^2leq n^2-(k-1)(2n-k)$$
and
claim:$sum_{i=1}^{k+1} n_i=nland n_iin mathbb{N}$
imply
$$sum_{i=1}^{k+1} n_i^2leq n^2-k(2n-k-1)$$
$$sum_{i=1}^{k+1} n_i^2=sum_{i=1}^k n_i^2+n_{k+1}^2leq (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}=1lor 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^2leq 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$
inequality natural-numbers
add a comment |
up vote
0
down vote
favorite
$$forall iin {1,2,cdots, k}, n_iinmathbb{N}$$ $$sum_{i=1}^k n_i =n$$
then
$$sum_{i=1}^k n_i^2leq n^2-(k-1)(2n-k)$$
Like comment, If we apply induction,
$i) k=2$
$n_1+n_2=nland n_1,n_2in 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^2leq 1^2+(n-1)^2= n^2-1*(2n-2)$$
ii)for induction,
suppose $sum_{i=1}^k n_i=nland n_iin mathbb{N}$
imply
$$sum_{i=1}^k n_i^2leq n^2-(k-1)(2n-k)$$
and
claim:$sum_{i=1}^{k+1} n_i=nland n_iin mathbb{N}$
imply
$$sum_{i=1}^{k+1} n_i^2leq n^2-k(2n-k-1)$$
$$sum_{i=1}^{k+1} n_i^2=sum_{i=1}^k n_i^2+n_{k+1}^2leq (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}=1lor 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^2leq 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$
inequality natural-numbers
1
Induction looks like a useful starting point. I'm not going to guarantee it'll work, though, but it would be my instinct with things like these. If you could provide details on an approach you've tried, it might be more helpful.
– Eevee Trainer
Nov 16 at 9:29
It's false: for $n_1=n_2=0$ and $n_3=2$ we have $0^2+0^2+2^2leq 2^2-(3-1)(2cdot 2-3)$ which is false.
– Fabio Lucchini
Nov 16 at 10:41
$n_1,n_2,n_3in mathbb{N}$ so $n_1,n_2,n_3geq 1$
– 백주상
Nov 17 at 3:45
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
$$forall iin {1,2,cdots, k}, n_iinmathbb{N}$$ $$sum_{i=1}^k n_i =n$$
then
$$sum_{i=1}^k n_i^2leq n^2-(k-1)(2n-k)$$
Like comment, If we apply induction,
$i) k=2$
$n_1+n_2=nland n_1,n_2in 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^2leq 1^2+(n-1)^2= n^2-1*(2n-2)$$
ii)for induction,
suppose $sum_{i=1}^k n_i=nland n_iin mathbb{N}$
imply
$$sum_{i=1}^k n_i^2leq n^2-(k-1)(2n-k)$$
and
claim:$sum_{i=1}^{k+1} n_i=nland n_iin mathbb{N}$
imply
$$sum_{i=1}^{k+1} n_i^2leq n^2-k(2n-k-1)$$
$$sum_{i=1}^{k+1} n_i^2=sum_{i=1}^k n_i^2+n_{k+1}^2leq (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}=1lor 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^2leq 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$
inequality natural-numbers
$$forall iin {1,2,cdots, k}, n_iinmathbb{N}$$ $$sum_{i=1}^k n_i =n$$
then
$$sum_{i=1}^k n_i^2leq n^2-(k-1)(2n-k)$$
Like comment, If we apply induction,
$i) k=2$
$n_1+n_2=nland n_1,n_2in 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^2leq 1^2+(n-1)^2= n^2-1*(2n-2)$$
ii)for induction,
suppose $sum_{i=1}^k n_i=nland n_iin mathbb{N}$
imply
$$sum_{i=1}^k n_i^2leq n^2-(k-1)(2n-k)$$
and
claim:$sum_{i=1}^{k+1} n_i=nland n_iin mathbb{N}$
imply
$$sum_{i=1}^{k+1} n_i^2leq n^2-k(2n-k-1)$$
$$sum_{i=1}^{k+1} n_i^2=sum_{i=1}^k n_i^2+n_{k+1}^2leq (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}=1lor 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^2leq 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$
inequality natural-numbers
inequality natural-numbers
edited Nov 17 at 3:46
asked Nov 16 at 9:26
백주상
1139
1139
1
Induction looks like a useful starting point. I'm not going to guarantee it'll work, though, but it would be my instinct with things like these. If you could provide details on an approach you've tried, it might be more helpful.
– Eevee Trainer
Nov 16 at 9:29
It's false: for $n_1=n_2=0$ and $n_3=2$ we have $0^2+0^2+2^2leq 2^2-(3-1)(2cdot 2-3)$ which is false.
– Fabio Lucchini
Nov 16 at 10:41
$n_1,n_2,n_3in mathbb{N}$ so $n_1,n_2,n_3geq 1$
– 백주상
Nov 17 at 3:45
add a comment |
1
Induction looks like a useful starting point. I'm not going to guarantee it'll work, though, but it would be my instinct with things like these. If you could provide details on an approach you've tried, it might be more helpful.
– Eevee Trainer
Nov 16 at 9:29
It's false: for $n_1=n_2=0$ and $n_3=2$ we have $0^2+0^2+2^2leq 2^2-(3-1)(2cdot 2-3)$ which is false.
– Fabio Lucchini
Nov 16 at 10:41
$n_1,n_2,n_3in mathbb{N}$ so $n_1,n_2,n_3geq 1$
– 백주상
Nov 17 at 3:45
1
1
Induction looks like a useful starting point. I'm not going to guarantee it'll work, though, but it would be my instinct with things like these. If you could provide details on an approach you've tried, it might be more helpful.
– Eevee Trainer
Nov 16 at 9:29
Induction looks like a useful starting point. I'm not going to guarantee it'll work, though, but it would be my instinct with things like these. If you could provide details on an approach you've tried, it might be more helpful.
– Eevee Trainer
Nov 16 at 9:29
It's false: for $n_1=n_2=0$ and $n_3=2$ we have $0^2+0^2+2^2leq 2^2-(3-1)(2cdot 2-3)$ which is false.
– Fabio Lucchini
Nov 16 at 10:41
It's false: for $n_1=n_2=0$ and $n_3=2$ we have $0^2+0^2+2^2leq 2^2-(3-1)(2cdot 2-3)$ which is false.
– Fabio Lucchini
Nov 16 at 10:41
$n_1,n_2,n_3in mathbb{N}$ so $n_1,n_2,n_3geq 1$
– 백주상
Nov 17 at 3:45
$n_1,n_2,n_3in mathbb{N}$ so $n_1,n_2,n_3geq 1$
– 백주상
Nov 17 at 3:45
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
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
quadiffquad 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.
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
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
quadiffquad 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.
add a comment |
up vote
0
down vote
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
quadiffquad 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.
add a comment |
up vote
0
down vote
up vote
0
down vote
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
quadiffquad 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.
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
quadiffquad 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.
edited Nov 17 at 11:37
answered Nov 17 at 4:51
achille hui
93.7k5127251
93.7k5127251
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3000936%2fquestion-about-an-inequality%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
Induction looks like a useful starting point. I'm not going to guarantee it'll work, though, but it would be my instinct with things like these. If you could provide details on an approach you've tried, it might be more helpful.
– Eevee Trainer
Nov 16 at 9:29
It's false: for $n_1=n_2=0$ and $n_3=2$ we have $0^2+0^2+2^2leq 2^2-(3-1)(2cdot 2-3)$ which is false.
– Fabio Lucchini
Nov 16 at 10:41
$n_1,n_2,n_3in mathbb{N}$ so $n_1,n_2,n_3geq 1$
– 백주상
Nov 17 at 3:45