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.

I'm learning the basics of proof by induction and wanted to see if I took the right steps with the following proof:

Theorem: for $n \in \mathbb{N}, \sum\limits_{k=1}^{n} (2k+1) = n^{2} + 2n $

Base Case:

let $$ n = 1 $$ Therefore $$2*1+1 = 1^{2}+2*1 $$ Which proves base case is true.

Inductive Hypothesis:

Assume $$\sum_{k=1}^{n} (2k+1) = n^{2} + 2n $$

Then $$\sum_{k=1}^{n+1} (2k+1) = (n+1)^{2} + 2(n+1) $$ $$\iff (2(n+1) +1)+ \sum_{k=1}^{n} (2k+1) = (n+1)^{2} + 2(n+1) $$ Using inductive hypothesis on summation term: $$\iff(2(n+1) +1)+ n^{2} + 2n = (n+1)^{2} + 2(n+1) $$ $$\iff 2(n+1) = 2(n+1) $$

Hence for $n \in \mathbb{N}, \sum\limits_{k=1}^{n} (2k+1) = n^{2} + 2n $ Q.E.D.

Does this prove the theorem? Or was my use of the inductive hypothesis circular logic?

share|improve this question
    
You should probably not try to treat what you're trying to prove in the inductive step like an equation where you can do what you want to both sides. Work with one side at a time to try to get it into the appropriate form. If it makes things easier, it is fine to do "a=c,b=c, therefore a=b". A proper inductive step would look more like Wacdonald's answer. –  Mike Jul 20 '12 at 7:23
    
The sum of the first $n$ positive odd numbers is $n^2$. Thus $1+3+5+\cdots+(2n+1)=(n+1)^2$, and $3+5+\cdots+(2n+1)=(n+1)^2-1=n^2+2n$. –  Jonas Meyer Nov 30 '12 at 6:19

2 Answers 2

up vote 5 down vote accepted

Your proof looks fine, but if you know that $$1+2+...+n=\frac{n(n+1)}{2}$$ then you can evaluate $$\sum_{k=1}^n(2k+1)=2\sum_{k=1}^n k+\sum_{k=1}^n1=\rlap{/}2\frac{n(n+1)}{\rlap{/}2}+n=n^2+2n$$

share|improve this answer

Your proof is fine, but for me, it didn't look like the clearest presentation. For instance, I think it'd be better to drop the biconditionals, and for your inductive step just write

$$\begin{eqnarray} \sum_{k=1}^{n+1} (2k+1) &=& n^2 + 2n + 2(n+1) + 1 \\ &=& n^2 + 2n + 1 + 2(n + 1)\\ &=& (n+1)^2 + 2(n+1)\\ \end{eqnarray}$$

share|improve this answer

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.