Recitation 8: Proof by Induction Solutions

Prove the following statements using mathematical induction.

  1. 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.

  1. 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. ∎

  1. 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.

  1. 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. ∎

  1. 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. ∎

  1. 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.

  1. 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.