Recitation 8: Proof by Induction Solutions

Prove the following statements using mathematical induction.

Prove that $1+2+3+...+n=\frac{n(n+1)}{2}$ for every positive integer $n$ .

We shall prove this using induction.

In the basis step, $n=1$ , we see that
$1 = 1$
and
$\frac{n(n+1)}{2} = \frac{1(1 + 1)}{2} = 1$
and so the basis step holds.

In the inductive step, we will assume that $1+2+3+...+k=\frac{k(k+1)}{2}$ for some positive integer $k$ and show that $1+2+3+...+k+(k+1)=\frac{(k+1)(k+2)}{2}$ . By the inductive hypothesis,
$1+2+3+...+k+(k+1)= \frac{k(k+1)}{2} + (k + 1).$
With some algebraic manipulation this becomes
$1+2+3+...+k+(k+1)= \frac{k(k+1) + 2(k+1)}{2}$
or
$1+2+3+...+k+(k+1)=\frac{(k+1)(k+2)}{2}$
and so the inductive step holds.

Since the inductive step and the basis step hold, it is true that $1+2+3+...+n=\frac{n(n+1)}{2}$ for every positive integer $n$ .

Prove that $1+3+5+...+(2n-1)=n^2$ for every positive integer $n$ . ∎

We shall prove this using induction.

In the basis step, $n=1$ , we see that
$2(1)-1 = 1$
and
$1^2 = 1$
and so the basis step holds.

In the inductive step, we will assume that $1+3+5+...+(2k-1)=k^2$ for some positive integer $k$ and show that $1+3+5+...+(2k-1)+(2(k+1)-1)=(k+1)^2$ . By the inductive hypothesis,
$1+3+5+...+(2k-1)+(2(k+1)-1)= k^2 + (2(k+1)-1) = k^2 + 2k + 1.$
Factoring this yields
$1+3+5+...+(2k-1)+(2(k+1)-1)=(k+1)^2$
and so the inductive step holds.

Since the inductive step and the basis step hold, it is true that $1+3+5+...+(2n-1)=n^2$ for every positive integer $n$ . ∎

Prove that $2^n>n^2$ for every positive n that is greater than 4.

We shall prove this using induction.

In the basis step, $n = 5$ , we see that
$2^5 = 32 > 25 = 5^2$
and so the basis step holds.

In the inductive step, we will assume $2^k > k^2$ for some positive integer $k$ and show that $2^{k+1} > (k+1)^2$ . Applying the inductive hypothesis,
$2^{k+1} = 2*2^k > 2k^2 = k^2 + k^2.$
Note that for $k \geq 3$ ,
$k^2 - 2k - 1 = (k-1)^2 - 2 > 0,$
so
$k^2 > 2k + 1.$
By substitution,
$2^{k+1} > k^2 + k^2 > k^2 + 2k + 1 = (k+1)^2$
and hence the inductive step holds.

Since the inductive step and the basis step hold, $2^n>n^2$ for every positive n that is greater than 4. ∎

There are many different ways to show
$k^2 > 2k+1$
for $k \geq 3$ - it may be useful to try induction here.

Prove that $n^5-n$ is divisible by 5 for every positive integer n.

We shall prove this using induction.

In the basis step, $n = 1$ ,
$n^5 - n = 1-1 = 0 = 5*0$
so the basis step holds.

In the inductive step, we assume $k^5 - k$ is divisible by 5 for some positive integer $k$ and we will show $(k+1)^5 - (k+1)$ is divisible by 5. Expanding the left-hand side yields,
$(k+1)^5 - (k+1) = (k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1) - (k+1)$
or, combining like terms except for $(k^5 -k)$ ,
$(k+1)^5 - (k+1) = (k^5 - k) + 5(k^4 + 2k^3 + 2k^2 + k).$
Since this is the sum of two integers which are divisble by five, $(k+1)^5 - (k+1)$ is divisible by 5. Hence, the inductive step holds.

Since the inductive step and the basis step hold, $n^5-n$ is divisible by 5 for every positive integer n. ∎

Prove that $1*2+2*3+3*4+...+n*(n+1)=\frac{(n)(n+1)(n+2)}{3}$ for every positive integer n.

We shall prove this using induction.

In the basis step, $n = 1$ ,
$1*2 = 2$
and
$\frac{(1)(2)(3)}{3} = 2$
so the basis step holds.

In the inductive step, we assume $1*2+2*3+3*4+...+k*(k+1)=\frac{(k)(k+1)(k+2)}{3}$ for some positive integer $k$ and we will show $1*2+2*3+3*4+...+k*(k+1)+(k+1)*(k+2)=\frac{(k+1)(k+2)(k+3)}{3}$ . Applying the inductive hypothesis to the left-hand side yields
$1*2+2*3+3*4+...+k*(k+1)+(k+1)*(k+2)= \frac{(k)(k+1)(k+2)}{3} + (k+1)*(k+2)$
or
$1*2+2*3+3*4+...+k*(k+1)+(k+1)*(k+2) = \frac{(k)(k+1)(k+2)}{3} + \frac{3(k+1)*(k+2)}{3}$
which gives
$1*2+2*3+3*4+...+k*(k+1)+(k+1)*(k+2) = \frac{k(k+1)(k+2) + 3(k+1)(k+2)}{3}$
so
$1*2+2*3+3*4+...+k*(k+1)+(k+1)*(k+2) = \frac{(k+3)(k+1)(k+2)}{3}$
and hence the inductive step holds.

Since the inductive step and the basis step hold, $1*2+2*3+3*4+...+n*(n+1)=\frac{(n)(n+1)(n+2)}{3}$ for every positive integer n. ∎

Find a formula for $\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+...+\frac{1}{2^n}$ and prove it.

The formula is $1 - 2^{-n}$ . The proof is left to the reader.

Consider the sequence: $1+2+4+8+16+...$ What is the sum of the first n elements? Prove this.

The sum is $2^{n+1}-1$ . The proof is left to the reader.