3

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) $$

Geralt
  • 313
  • What have you tried and where are you stuck? You are more likely to get useful help on this site if you show you have expended some effort on the problem. – rogerl Oct 08 '18 at 01:51
  • first prove that $1+2+3+...+n=\frac{n(n+1)}{2}$. This can be done without induction. – Vasili Oct 08 '18 at 01:52
  • Can someone clarify what the question means when it says "for a collection of natural numbers x1,x2. What value would x2 have. Would it just be 1 + 2 – Geralt Oct 08 '18 at 02:16
  • Why is induction to be avoided? And can you assume $\sum_{j\in S} j$ will be the same value no matter what order you add the finite terms? Or that if $x_k \le k$ then $\sum x_k \le k$? Theoretically, to assume either of those requires induction. – fleablood Oct 08 '18 at 02:18
  • ""for a collection of natural numbers x1,x2. What value would x2 have. Would it just be 1 + 2" No. It could be $x_1 = 30; x_2 =1; x_3 =5, x_4=7; x_5 = 7, .....$. It means exactly what it says... the $x_i$ can be any natural numbers. They do not need to be sorted by size and the do not have to be distinct. – fleablood Oct 08 '18 at 02:22

4 Answers4

1

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.

JMoravitz
  • 79,518
1

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.

fleablood
  • 124,253
0

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.

David
  • 1
0

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$.

bubba
  • 43,483
  • 3
  • 61
  • 122