# Proof $\sum\limits_{r=1}^{n} r >\frac{1}{2}n^2$ using induction

Question:

$$\text{Prove by induction that, for all integers } n, n \geq 1:$$ $$\sum\limits_{r=1}^{n} r >\frac{1}{2}n^2$$

Working:

Step 1 (Prove true for n=1): $$1>\frac{1}{2}(1)^2$$

Step 2 (Assume true for n=k): $$k >\frac{1}{2}k^2$$

Step 3 (Prove true for n=k+1):

And having only faced equations with an equals (=) sign I have no idea what to do next. Right now I have assumed that it stands true for $k$ and I will try to prove for $k+1$. What should be my next step?

-
Your step 2 is incorrect, since $$\sum_{r=1}^k r = 1+2+3+\cdots+k\neq k$$ – Zev Chonoles May 31 '12 at 19:35
Maybe the simplest thing to do is to prove that $\sum_{r=1}^n{r} = \frac12(n^2+n)$, from which the conclusion follows immediately. – MJD May 31 '12 at 20:36
@MarkDominus, I agree. However, that falls outside of the implied instructions. (Ironically, I do think that method of proof would be far more intelligent and obvious than the inductive proof.) – 000 May 31 '12 at 22:18

Your second step should read $$\sum_{r=1}^k r > \dfrac{k^2}{2}$$ Then note that $$\sum_{r=1}^{k+1} r = \underbrace{(k+1) + \sum_{r=1}^{k} r > (k+1) + \dfrac{k^2}{2}}_{\text{Induction hypothesis}} = \underbrace{\dfrac{k^2+2k+2}{2} > \dfrac{k^2+2k+1}{2}}_{a+\frac12 > a} = \dfrac{(k+1)^2}{2}$$

-
+1 Nice and simple to understand, thanks – εν οίδα ότι ουδέν οίδα May 31 '12 at 19:52

Hint $\$ It is easy to prove by induction that an increasing function remains $\ge$ its initial value, i.e. that $\rm\:f(n\!+\!1) \ge f(n)\:$ for $\rm\:n\ge 1\:$ $\Rightarrow$ $\rm\:f(n) \ge f(1)\:$ for $\rm n\ge 1$.

For $\rm\:f(n) =$ RHS - LHS of your inequality, $\rm\:f\:$ is increasing since

$$\rm f(n+1) - f(n)\: =\ n\!+\!1 - ((n+1)^2 -n^2)/2 \: =\: 1/2\, >\, 0$$

So for all $\rm\:n\ge 1,\: f(n) \ge f(1) = 1/2,\:$ i.e. RHS $-$ LHS $\ge 1/2,\:$ so $\,$ RHS > LHS. $\quad$ QED

Note how this viewpoint removes all the guesswork from the inductive proof, reducing it to a simple rote algebraic calculation, viz. proving the positivity needed to show that $\rm\:f\:$ is increasing. The same technique works for many inductive problems of this type. For many examples see my prior posts on telescopy, where I show how the above can be viewed as the trivial induction that a sum of positive terms is positive.

-

\begin{align} \sum_{1 \leq r \leq k+1}r &> \frac{(k+1)^2}{2}\\ \sum_{1 \leq r \leq k}r+(k+1) &> \frac{k^2}{2}+\frac{2k+1}{2}\\ 2\sum_{1 \leq r \leq k}r+2(k+1) &> k^2+(2k+1)\\ 2\sum_{1 \leq r \leq k}r &> k^2\\ 2(k+1) &> (2k+1)\\ \therefore \sum_{1 \leq r \leq k+1}r &> \frac{(k+1)^2}{2} \end{align}

-
My computer didn't update to notify me that you accepted Marvis's answer. Oh well. Hopefully this can be of some help. – 000 May 31 '12 at 20:15