CS161 Lab Week 8: Mathematical Induction

In this lab you will gain more experience with mathematical induction. Write your answers to the following problems on paper and show the instructor your answers before leaving. The instructor will lead initial discussion of each question.

Prove the following proposition, P(n), for n > 0. This one should be easy, since we did it in lecture.

1 + 2 + 3 + ⋯ + n = n(n + 1) ⁄ 2

Prove the following proposition, P(n), for n > 0.

1 + 3 + 5 + ⋯ + (2n − 1) = n²

Prove this proposition, P(n), for n > 0.

1⋅2 + 2⋅3 + 3⋅4 + ⋯ + n(n + 1) = n(n + 1)(n + 2) ⁄ 3

Determine which amounts of postage can be formed using only 4 cent and 11 cent stamps. Prove your answer using mathematical induction.
Prove that n! < nⁿ.
Find a formula for 1 ⁄ 2 + 1 ⁄ 4 + 1 ⁄ 8 + ... + 1 ⁄ (2ⁿ) and then prove your formula is correct.
Consider the sequence 1 + 2 + 4 + 8 + 16 + ⋯. What is the sum of the first n elements? Prove it.

8. Prove that this recursive method does calculate xⁿ.

public int power( int x, int n) {
   if (n == 0)
      return 1;

   return x * power(x,n-1);
}

Remember the solution to the Tower of Hanoi puzzle? Prove that the smallest number, S_n, of disk moves for the solution of a puzzle with three pegs and n disks is 2ⁿ − 1. In other words, prove

S_n = 2ⁿ − 1