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