Inequality: $sum_i = 1^n x_i = kn$ if and only if $x_i = k$ (proof verification)
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
The current inequality solution that I need to determine is the following.
Let $n geq 1$ be a natural number and consider a collection of natural numbers $x_1, x_2, ldots, x_n$. Suppose that $x_i geq k$ for a natural number $k geq 1$. Then
$$
sum_i = 1^n x_i = kn
$$
if and only if $x_i = k$ for all $i = 1, 2, ldots, n$.
This feels trivial, but I would clarification that my proof holds (other proofs are also welcomed). My attempt is the following.
Proof. The $(Leftarrow)$ direction is clear.
We prove the $(Rightarrow)$ direction by induction on $n$. The case $n = 1$ is clear. If $n = 2$, then $x_1, x_2 geq k$ and $x_1 + x_2 = 2k$. Now
$$
x_2 = 2k - x_1 geq k implies k - x_1 geq 0 implies x_1 leq k.
$$
Thus $x_1 = k$, from which it follows that $x_2 = k$ also.
Now suppose that the case holds for all natural numbers up to $m$. Suppose that $x_1, x_2, ldots, x_m, x_m+1 geq k$ and that
$$
x_1 + x_2 + cdots + x_m + x_m+1 = (m + 1)k.
$$
Then
$$
x_m+1 = (m + 1)k - big(x_1 + x_2 + cdots + x_mbig) geq k
$$
so that
$$
x_1 + x_2 + cdots + x_m leq mk.tag$ast$
$$
But $x_1, x_2, ldots, x_m, x_m+1 geq k$ implies that
$$
mk leq x_1 + x_2 + cdots + x_m
$$
which, combined with $(ast)$, implies that
$$
x_1 + x_2 + cdots + x_m = km.
$$
By the inductive hypothesis, we have $x_1 = x_2 = cdots = x_m = k$ from which it follows that $x_m+1 = k$.$qquadsquare$
proof-verification inequality
add a comment |Â
up vote
1
down vote
favorite
The current inequality solution that I need to determine is the following.
Let $n geq 1$ be a natural number and consider a collection of natural numbers $x_1, x_2, ldots, x_n$. Suppose that $x_i geq k$ for a natural number $k geq 1$. Then
$$
sum_i = 1^n x_i = kn
$$
if and only if $x_i = k$ for all $i = 1, 2, ldots, n$.
This feels trivial, but I would clarification that my proof holds (other proofs are also welcomed). My attempt is the following.
Proof. The $(Leftarrow)$ direction is clear.
We prove the $(Rightarrow)$ direction by induction on $n$. The case $n = 1$ is clear. If $n = 2$, then $x_1, x_2 geq k$ and $x_1 + x_2 = 2k$. Now
$$
x_2 = 2k - x_1 geq k implies k - x_1 geq 0 implies x_1 leq k.
$$
Thus $x_1 = k$, from which it follows that $x_2 = k$ also.
Now suppose that the case holds for all natural numbers up to $m$. Suppose that $x_1, x_2, ldots, x_m, x_m+1 geq k$ and that
$$
x_1 + x_2 + cdots + x_m + x_m+1 = (m + 1)k.
$$
Then
$$
x_m+1 = (m + 1)k - big(x_1 + x_2 + cdots + x_mbig) geq k
$$
so that
$$
x_1 + x_2 + cdots + x_m leq mk.tag$ast$
$$
But $x_1, x_2, ldots, x_m, x_m+1 geq k$ implies that
$$
mk leq x_1 + x_2 + cdots + x_m
$$
which, combined with $(ast)$, implies that
$$
x_1 + x_2 + cdots + x_m = km.
$$
By the inductive hypothesis, we have $x_1 = x_2 = cdots = x_m = k$ from which it follows that $x_m+1 = k$.$qquadsquare$
proof-verification inequality
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
The current inequality solution that I need to determine is the following.
Let $n geq 1$ be a natural number and consider a collection of natural numbers $x_1, x_2, ldots, x_n$. Suppose that $x_i geq k$ for a natural number $k geq 1$. Then
$$
sum_i = 1^n x_i = kn
$$
if and only if $x_i = k$ for all $i = 1, 2, ldots, n$.
This feels trivial, but I would clarification that my proof holds (other proofs are also welcomed). My attempt is the following.
Proof. The $(Leftarrow)$ direction is clear.
We prove the $(Rightarrow)$ direction by induction on $n$. The case $n = 1$ is clear. If $n = 2$, then $x_1, x_2 geq k$ and $x_1 + x_2 = 2k$. Now
$$
x_2 = 2k - x_1 geq k implies k - x_1 geq 0 implies x_1 leq k.
$$
Thus $x_1 = k$, from which it follows that $x_2 = k$ also.
Now suppose that the case holds for all natural numbers up to $m$. Suppose that $x_1, x_2, ldots, x_m, x_m+1 geq k$ and that
$$
x_1 + x_2 + cdots + x_m + x_m+1 = (m + 1)k.
$$
Then
$$
x_m+1 = (m + 1)k - big(x_1 + x_2 + cdots + x_mbig) geq k
$$
so that
$$
x_1 + x_2 + cdots + x_m leq mk.tag$ast$
$$
But $x_1, x_2, ldots, x_m, x_m+1 geq k$ implies that
$$
mk leq x_1 + x_2 + cdots + x_m
$$
which, combined with $(ast)$, implies that
$$
x_1 + x_2 + cdots + x_m = km.
$$
By the inductive hypothesis, we have $x_1 = x_2 = cdots = x_m = k$ from which it follows that $x_m+1 = k$.$qquadsquare$
proof-verification inequality
The current inequality solution that I need to determine is the following.
Let $n geq 1$ be a natural number and consider a collection of natural numbers $x_1, x_2, ldots, x_n$. Suppose that $x_i geq k$ for a natural number $k geq 1$. Then
$$
sum_i = 1^n x_i = kn
$$
if and only if $x_i = k$ for all $i = 1, 2, ldots, n$.
This feels trivial, but I would clarification that my proof holds (other proofs are also welcomed). My attempt is the following.
Proof. The $(Leftarrow)$ direction is clear.
We prove the $(Rightarrow)$ direction by induction on $n$. The case $n = 1$ is clear. If $n = 2$, then $x_1, x_2 geq k$ and $x_1 + x_2 = 2k$. Now
$$
x_2 = 2k - x_1 geq k implies k - x_1 geq 0 implies x_1 leq k.
$$
Thus $x_1 = k$, from which it follows that $x_2 = k$ also.
Now suppose that the case holds for all natural numbers up to $m$. Suppose that $x_1, x_2, ldots, x_m, x_m+1 geq k$ and that
$$
x_1 + x_2 + cdots + x_m + x_m+1 = (m + 1)k.
$$
Then
$$
x_m+1 = (m + 1)k - big(x_1 + x_2 + cdots + x_mbig) geq k
$$
so that
$$
x_1 + x_2 + cdots + x_m leq mk.tag$ast$
$$
But $x_1, x_2, ldots, x_m, x_m+1 geq k$ implies that
$$
mk leq x_1 + x_2 + cdots + x_m
$$
which, combined with $(ast)$, implies that
$$
x_1 + x_2 + cdots + x_m = km.
$$
By the inductive hypothesis, we have $x_1 = x_2 = cdots = x_m = k$ from which it follows that $x_m+1 = k$.$qquadsquare$
proof-verification inequality
asked Aug 21 at 13:33
Bill Wallis
2,2361826
2,2361826
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
Your inductive proof looks correct, but as you feel, for such a simple statement there is a simpler (non-inductive) proof. To prove the forward direction, it suffices to show that each $x_i leq k$. Suppose not, so that some $x_i geq k+1$. Then the sum of all $x_i$ must be strictly greater than $nk$, a contradiction.
That's what I was thinking, but for some reason couldn't formulate it properly. Thanks!
â Bill Wallis
Aug 21 at 13:50
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Your inductive proof looks correct, but as you feel, for such a simple statement there is a simpler (non-inductive) proof. To prove the forward direction, it suffices to show that each $x_i leq k$. Suppose not, so that some $x_i geq k+1$. Then the sum of all $x_i$ must be strictly greater than $nk$, a contradiction.
That's what I was thinking, but for some reason couldn't formulate it properly. Thanks!
â Bill Wallis
Aug 21 at 13:50
add a comment |Â
up vote
1
down vote
accepted
Your inductive proof looks correct, but as you feel, for such a simple statement there is a simpler (non-inductive) proof. To prove the forward direction, it suffices to show that each $x_i leq k$. Suppose not, so that some $x_i geq k+1$. Then the sum of all $x_i$ must be strictly greater than $nk$, a contradiction.
That's what I was thinking, but for some reason couldn't formulate it properly. Thanks!
â Bill Wallis
Aug 21 at 13:50
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Your inductive proof looks correct, but as you feel, for such a simple statement there is a simpler (non-inductive) proof. To prove the forward direction, it suffices to show that each $x_i leq k$. Suppose not, so that some $x_i geq k+1$. Then the sum of all $x_i$ must be strictly greater than $nk$, a contradiction.
Your inductive proof looks correct, but as you feel, for such a simple statement there is a simpler (non-inductive) proof. To prove the forward direction, it suffices to show that each $x_i leq k$. Suppose not, so that some $x_i geq k+1$. Then the sum of all $x_i$ must be strictly greater than $nk$, a contradiction.
answered Aug 21 at 13:41
Bob Krueger
4,0502722
4,0502722
That's what I was thinking, but for some reason couldn't formulate it properly. Thanks!
â Bill Wallis
Aug 21 at 13:50
add a comment |Â
That's what I was thinking, but for some reason couldn't formulate it properly. Thanks!
â Bill Wallis
Aug 21 at 13:50
That's what I was thinking, but for some reason couldn't formulate it properly. Thanks!
â Bill Wallis
Aug 21 at 13:50
That's what I was thinking, but for some reason couldn't formulate it properly. Thanks!
â Bill Wallis
Aug 21 at 13:50
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2889860%2finequality-sum-i-1n-x-i-kn-if-and-only-if-x-i-k-proof-veri%23new-answer', 'question_page');
);
Post as a guest
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
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
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