Question

3) Prove by induction that for all natural numbers n:

(a) 1 + 3 + 5 + · · · + (2n − 1) = n²

Answer 1

Let $P(n)$ be the proposition that the sum $1+3+5+...+(2n-1)$ is $n^2$ for all natural numbers $n$

$$1+3+5+...+(2n-1)=n^2$$

Basic step

$P(1)$ is true, because $1=1^2.$

Inductive step

For the inductive hypothesis we assume that $P(k)$ holds for an arbitrary

natural number $k.$ That is, we assume that

$$1+3+5+...+(2k-1)=k^2$$

Under this assumption, it must be shown that $P(k+1)$ is true, namely, that

$$1+3+5+...+(2(k+1)-1)=(k+1)^2$$

When we add $(2(k+1)-1)$ to both sides of the equation in $P(k),$ we obtain

$$1+3+5+...+(2k-1)+(2(k+1)-1))$$

$$=k^2+(2(k+1)-1)$$

$$1+3+5+...+(2k-1)+(2(k+1)-1))=$$

$$=k^2+2k+1$$

$$1+3+5+...+(2k-1)+(2(k+1)-1))=$$

$$=(k+1)^2$$

This last equation shows that $P(k+1)$ is true under the assumption that $P(k)$ is true. This completes the inductive step.

We have completed the basis step and the inductive step, so by mathematical induction we know that $P(n)$ is true for all natural numbers $n$. That is, we have proven that

$$1+3+5+...+(2n-1)=n^2$$

for all natural numbers $n.$