# Proof By Induction - $n^2 = \sum_{i=1} ^{n} (2i-1)$ for all $n\geq 1$ [duplicate]

Using Proof By Induction I am trying to prove the following:

$n^2 = \sum_{i=1} ^{n} (2i-1)$ for all $n\geq 1$

Here is my solutions so Far:

Base Case: $n=1, LHS: 2(1)-1 = 1, RHS = 1^2 = 1, True$

Induction Hypothesis:

Assume true for $n=k$

$k^2 =\sum_{i=1} ^{k} (2i-1)$ for some $k\geq 1$

Induction Step: Should be True for $n=k+1$

$(k+1)^2 =\sum_{i=1} ^{k+1} (2i-1)$ for some $k\geq 1$

However here is where I get stuck

• Are you only allowed an inductive proof? Perturbation method would be much better – Alex Apr 26 '15 at 14:26
• @Alex Yes only Inductive – RandomMath Apr 26 '15 at 14:27
• On your hypothesis step you said it was true for all $k \geq 1$. If that was true then you are done. You should instead say it is true for SOME $k \ge 1$. – Ebearr Apr 26 '15 at 14:27
• @Ebearr - Changed – RandomMath Apr 26 '15 at 14:29
• In the original question, the summation should be taken from $i=1$ instead of from $i=0$. Putting $n=1$ clearly shows this. – hypergeometric Apr 26 '15 at 14:35

We want to show that, given the inductive hypothesis, $$(k+1)^2 =\sum_{i=1} ^{k+1} (2i-1)$$

LHS: $k^2 + 2k+1$.

The RHS

\begin{align} \sum_{i=1} ^{k+1} (2i-1)& \overset{IH}{=} k^2 + 2(k+1) - 1 \\ & = k^2 + 2k +2-1 \\ \\ & = k^2 + 2k + 1\end{align}

Hence, given the inductive hypothesis, it follows that $(k+1)^2 =\sum_{i=1} ^{k+1} (2i-1)$. Hence, $$n^2 = \sum_{i=1}^{n} (2i-1)$$

• Could I just ask, how you got $k^2 + 2(k+1)-1$ – RandomMath Apr 26 '15 at 14:29
• hmm I probably miss something but RHS should be $(k+1)(k+2)-(k+1)=(k+1)^2$ – Alex Apr 26 '15 at 14:32
• @RandomMath $$\sum_{i = 0}^{k + 1} (2i - 1) = \sum_{i = 0}^{k} (2i - 1) + (2 (k + 1) - 1) = k^{2} + (2 (k + 1) - 1)$$ – mattos Apr 26 '15 at 14:37
• As Matteo notes, the sum includes $$\sum_{i = 1}^{k + 1} (2i - 1) = \underbrace{\Big(\sum_{i = 1}^{k} (2i - 1)\Big)}_{\large = k^2} +[ (2 (k + 1) - 1)] = \underbrace{k^{2}}_{\text{by IH}} + [2 (k + 1) - 1)]$$ – Jordan Glen Apr 26 '15 at 14:40