2
$\begingroup$

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?

  • 0
    @MarkDomi$n$us, 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.)2012-05-31

3 Answers 3

7

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

2

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.

1

\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}

  • 0
    My computer didn't update to notify me that you accepted Marvis's answer. Oh well. Hopefully this can be of some help.2012-05-31