Graph Theory Practice 7 (Mathematical Induction and More)
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York
(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.