Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

3 Answers 3

up vote 6 down vote accepted

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

share|improve this answer
    
+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.

share|improve this answer

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.