Practice With Induction

1. Prove the formula for the sum of the first n natural numbers:

   

2. Guess and prove a formula for the sum of the first n odd natural numbers.
3. Prove the formula for the sum of the first n+1 terms of an arithmetic progression:

   

   (Note that this equals the average of the first and last terms, multiplied by the number of terms.)

4. Prove the formula for the sum of the first n+1 terms of a geometric progression:

   

5. Prove the formula for the sum of the squares of the first n natural numbers:

   

6. Prove the formula for the sum of the cubes of the first n natural numbers:

   

7. The Fibonacci numbers are defined by and thereafter , . Prove the formula:

   

8. Prove that the set has exactly subsets.
9. For nonnegative integers n and k, define to be the number of subsets of size k contained in a set of size n. First prove (but not necessarily by induction!) that

   

   Then prove that

   

   remembering that we define 0!=1.

10. Prove the binomial formula:

    

11. Find and prove a formula for the number of ways n different men can be completely paired up with n different women.
12. A group of 2n individuals are to be paired off into n pairs to play checkers. Find and prove a formula for the number of ways to do this.
13. Prove that the Tower of Hanoi puzzle with n disks can be solved in moves.
14. Find and prove a formula for the maximum number of regions a plane can be divided up into using exactly n lines.
15. Find and prove a formula for the maximum number of regions space can be divided up into using exactly n planes.
16. Observe that

    

    Guess and prove the general result.

17. Guess and prove a formula for

    

    for .

18. Prove that every natural number greater than 1 can be factored into powers of primes.
19. Define (a,b) to be the greatest common divisor of natural numbers a and b. Assume without loss of generality that . Suppose c is the remainder when a is divided by b.
    1. Prove (without induction) that (b,c)=(a,b).
    2. Prove by induction (on what?) that if z=(a,b) then there exist integers m and n such that z=ma+nb.
    3. Prove (without induction) that if z is relatively prime to m and z is a divisor mn, then z is a divisor of n.
    4. Let n be a natural number greater than 1. Assume that where are primes and are positive natural numbers. Assume also that where are primes and are positive natural numbers. Prove by induction on n that , , , and , .

20. Prove that the number of ways to divide up a convex n-gon, , into triangles using its diagonals is

    

21. Three students, A, B, and C are seated in a circle facing each other. There is a supply of three red hats and two black hats, and the students are aware of the types of hats available. The students close their eyes, and a hat is placed on each one's head. The unused two hats are hidden. When they open their eyes, each can see the hats of the other two, but cannot see their own hat. Unknown to them, each has been given a red hat. Each one is asked in turn, ``Do you know the color of your hat?'' A answers truthfully, ``No.'' B does the same. But C's answer is ``Yes, my hat is red.'' How did C know this? Generalize to n students.