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?
Answer
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$$
No comments:
Post a Comment