3
$\begingroup$

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?

  • 0
    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.2012-07-20
  • 0
    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$.2012-11-30

2 Answers 2

5

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

4

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