Mathematical Induction

 

Prove by mathematical induction \[ \sum_{i=1}^n (2i-1) = n^2 \] for all natural numbers n > 0.

Prove the statement is true for a particular n. Here n = 1 looks a reasonable choice.

To show this is true for n=1, observe that the left hand side = 1 and the right hand side = 1.
So the statement is true for n=1.

Assume the statement is true for n = k and show it is true for n = k + 1.

To show the statement is true for n = k+1, call the LHS \( S_{k+1} \). Then \[ \begin{align} S_{k+1} &= S_k + 2(k+1) - 1 \\ \end{align} \ \]

Use the inductive hypothesis to simplify the right hand side.

By the inductive hypothesis, \[ \begin{align} S_{k+1} &= \sum_{i=1}^k (2i-1) + 2(k+1) - 1 \\ &= k^2 + 2(k+1) - 1 \\ &= k^2 + 2k + 1 \\ &= (k+1)^2 \end{align} \ \] Now the RHS has the same form as the RHS of the original expression with k+1 substituted for n. So the statement is true for n = k+1.

By the principle of mathematical induction,

The statement is true for \( n \gt 0 \).

You will gain most benefit if you work through each problem first and then come back and check your work against the solution.

 

y

Now You Try:

Prove by mathematical induction \[ \frac{1}{1 \times 2} + \frac{1}{2 \times 3} + \cdots + \frac{1}{n(n+1)} = \frac{n}{n+1} \] for all natural numbers n > 0.