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 n2.

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, n2 > 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 n3 - n is divisible by 3.

7. Show that 1 + 21 + 22 + 23 + ... + 2n = 2n+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! > 2n for n at least 4.

10. Show that 12 + 22 + 32 + ... + n2 = 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 2n > n2 when n is at least 4.

13. Show that 5 divides n5 - 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 2n 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/n2 < 2 - 1/n when n is at least 1.