Summation of natural numbers How would you prove this without induction?
Prove the following statement for a collection of natural numbers $$ x_1, x_2, . . . , x_n $$ and the set
$$ I = \{1, 2, . . . , n\} $$

Statement : $$ (x_1 + x_2 + · · · + x_n) >
\frac{n(n + 1)}{2} → (∃i ∈ I, x_i > i) $$

Suppose otherwise.  Then $\forall i, x_i\leq i$
Then $x_1+x_2+\dots+x_n \leq 1+2+\dots+n=\frac{n(n+1)}{2}$
The first inequality is noticed by our hypothesis that $x_1\leq 1$, that $x_2\leq 2$, etc... and making those substitutions simultaneously across the board.  The second equality is a very well known identity that you should be aware of.
