**Graph Theory Practice 7 (Mathematical Induction and More)
**

Prepared by:

Joseph Malkevitch

Department of Mathematics and Computer Studies

York College (CUNY)

Jamaica, New York

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^{2} > 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^{3} - n is divisible by 3.

7. Show that 1 + 2^{1} + 2^{2} + 2^{3} + ... + 2^{n} = 2^{n+1} - 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^{n} for n at least 4.

10. Show that 1^{2} + 2^{2} + 3^{2} + ... + n^{2} = 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} > n^{2} when n is at least 4.

13. Show that 5 divides n^{5} - 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^{n} 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)^{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} < 2 - 1/n when n is at least 1.