Inequality: $\sum_{i = 1}^{n} x_{i} = kn$ if and only if $x_{i} = k$ (proof verification)

31 Views Asked by At

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_{m}\big) \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$.$\qquad\square$

1

There are 1 best solutions below

1
On BEST ANSWER

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.