Practice Problems Involving Mathematical Induction

prepared by:

Joseph Malkevitch
Mathematics and Computing Department
York College (CUNY)
Jamaica, NY 11451

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk/

(n below denotes a positive integer unless otherwise indicated.)

1. Verify that the sum of the first n positive integers is n(n+1)/2.

2. Verify that the sum of the first n odd positive integers is n².

3. Verify that if T is a tree, then the number of vertices of T is one more than the number of edges in the tree.

(An example of a tree is shown below:

4. Verify that for n at least 2, n² > n + 1.

5. Show that the interior angles of a plane n-sided polygon sum to (n-2)(180) degrees.

(An example of a 7-sided plane polygon is shown below:

6. Show that n³ - n is divisible by 3.

7. Show that 1 + 2¹ + 2² + 2³ + ... + 2ⁿ = 2ⁿ⁺¹ - 1.

8. Show that:

(This result shows how to sum a geometric progression. A geometric progression is one in which each term being summed is r times the previous term (r not 1).)

9. Show that n! > 2ⁿ for n at least 4.

10. Show that 1² + 2² + 3² + ... + n² = n(n+1)(2n+1)/6.

(Problem 1 dealt with summing the first n integers. This problem gives a "formula" for the sum of the squares of the first n integers.)


11. Verify that: 1(2) + 2(3) + 3(4) + ... + n(n+1) = n (n+1)(n+2)/3.

12. Show that 2ⁿ > n² when n is at least 4.

13. Show that 5 divides n⁵ - n whenever n is a non-negative integer.

14. Show that for a plane connected graph, the number of vertices V, the number of edges E, and the number of faces F obeys V + F - E = 2.

(The plane connected graph below has 8 dots (V = 8), 13 line segments (E = 13), and 7 regions (F = 7). Note that one of the faces (regions) is the "unbounded region" that surrounds all the dots and line segments.)

(This diagram illustrates Euler's famous "polyhedral formula.")

15. Show that a set with n elements (n at least one) has exactly 2ⁿ subsets.

16. Show that the sum of the third powers (the cubes) of the first n positive integers is given by: (n(n+1)/2)².

17. 1(1!) + 2(2!) + 3(3!) + ... + n(n!) = (n+1)! - 1, when n is a positive integer.

18. Show that 1 + 1/4 + 1/9 + ... + 1/n² < 2 - 1/n when n is at least 1.