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) $$
 A: 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.
A: Depends on what you consider induction to be.
We know that $k + (n-(k-1)) = n+1$ so $$2\sum_{k=1}^n k = \sum_{k=1}^n k + \sum_{k=n;-1}^1 k = \sum_{k=1}^n k + \sum_{k=1}^n (n-(k-1)) = \sum_{k=1}^n (n+1) = n(n+1)$$.
However it can be argued we need to use induction to know that addition is commutative over multiple terms or that the $k$th terms of the two sequences are $k$ and $n-(k-1)$ or even that $\sum_{k=1}^n c = n*c$.  (At least I think those can be argued to require induction.  I might be wrong but I doubt it.)
And since for all $a<b$ we know $a +c < b+c$ we can prove that $a_1 < b_1$ and $a_2 < b_2$ implies $a_1 + b_1 < a_1 + b_2 < a_2 + b_2$.  So if $x_k \le k$ for all $k$, we have $\sum_{k=1}^n x_k \le \sum_{k=1}^n k = \frac {n(n+1)}2$.  And our result is proven by contrapositive.
But proving $x_k \le k\implies \sum x_k \le \sum k$ requires assuming induction.
So in that sense, I don't think this can be done without induction.  However the induction needed is so basic I don't think most, except the most devout Peano apostles, would consider it induction. 
A: Contrapositive?
If all $x_i$ were less than or equal to $i$ then
$$x_1+x_2 + \cdots +x_n \le 1+2+\cdots + n = \dfrac{n(n+1)}{2}$$
where the equality 
$$\sum_{i=1}^n i = \dfrac{n(n+1)}{2}$$
can be easily proven without induction.
A: If $x_i \le i$ for $i=1,2,\ldots,n$, then
$$
x_1 + \cdots + x_n \le 1+2+3+\cdots+n = \tfrac12 n(n+1)
$$
So, if 
$$
x_1 + \cdots + x_n > \tfrac12 n(n+1)
$$
then it cannot be true that $x_i \le i$ for $i=1,2,\ldots,n$. In other words, there must be some $i \in \{1,2,\ldots,n\}$ such that $x_i > i$.
