Answer to Question #299224 in Combinatorics | Number Theory for Yaku

Question

a) i) Give an inductive formula for the sum of the first n odd numbers:

1 + 3 + 5 + ... + 2n -1

Show your induction process.

ii) Use the proof by mathematical induction to prove the correctness of your

inductive formula in i) above.

Answer 1

a)

i)

$$a_1=1, a_2=3, a_n=2n-1=1+2(n-1)$$

We have the arithmetic progression with the first term $a_1=1$ and the common difference $d=2.$

$$S_n=\dfrac{a_1+a_n}{2}\cdot n=\dfrac{1+2n-1}{2}\cdot n=n^2$$

ii) Let $P(n)$ be the proposition that the sum of the first $n$ odd positive integers, $1+3+5+...+2n-1$ is $n^2.$

Basis Step

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

Inductive Step

For the inductive hypothesis we assume that $P(k)$ holds for an arbitrary positive integer $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+...+2k-1+2(k+1)-1=(k+1)^2$$

is also true.

When we add $k + 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$$ $$=k^2+2k+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 positive integers n. That is, we have proven that the sum of the first $n$ odd numbers $1+3+5+...+2n-1=n^2$ for all positive integers $n$ .