.Show that for any n real numbers
1. Let Dn denote the number of ways to cover the squares of a 2xn board using plain dominos. Then it is easy to see that D1 = 1, D2= 2, and D3 = 3. Compute a few more values of Dn and guess an expression for the value of Dn and use induction to prove you are right.
2. The triangle inequality says that for any two real numbers x and y, .
Show that for any n real numbers
3. How many ways are there to cover the squares of a 2xn chessboard with dominos?
Let Dn denote the number of such ways. For example, D1 =1, D2 =2, and D3 =3 as
illustrated below.
Work out the value of D4 and maybe D5, and guess an expression for Dn. To verify your guess you will need to use the strong form of induction. That means that instead of just assuming that the result is true for some k, you assume that it is true for all values less than some k, and then show that it must be true for k.
4. (a). Prove: For n >= 1, 
.
(b). Does the series 
converge or diverge?
5. Let an denote the number of subsets of {1, 2, 3, ... n} (including the empty set
and the set itself.)
(a). Show an = 2an-1. (This is pretty simple - you don't need induction here.)
(b). Guess a formula for the value of an and use induction to prove you are right.
6. Prove that for any n>=1, 4 | 3(2n-1) +1
7. Prove by induction: For any n >= 1, 13 + 23 + 33 + ... + n3 = (1 + 2 + 3 + ... + n)2.