discrete_mathematics_with_applications/chapter_5/exercises.md

Exercise Set 5.1

Page 296

Write the first four terms of the sequences defined by the formulas 1-6.

1. a_k = \dfrac{k}{10 + k}, for every integer k \geq 1.

 a_1 = \frac{1}{10 + 1} = \frac{1}{11} 

 a_2 = \frac{2}{10 + 2} = \frac{2}{12} 

 a_3 = \frac{3}{10 + 3} = \frac{3}{13} 

 a_4 = \frac{4}{10 + 4} = \frac{4}{14} 

2. b_j = \dfrac{5 - j}{5 + j}, for every integer j \geq 1.

 b_1 = \dfrac{5 - 1}{5 + 1} = \frac{4}{6} 

 b_2 = \dfrac{5 - 2}{5 + 2} = \frac{3}{7} 

 b_3 = \dfrac{5 - 3}{5 + 3} = \frac{2}{8} 

 b_4 = \dfrac{5 - 4}{5 + 4} = \frac{1}{9} 

3. c_i = \dfrac{(-1)^i}{3^i}, for every integer i \geq 0.

 c_0 = \dfrac{(-1)^0}{3^0} = \frac{1}{1} 

 c_1 = \dfrac{(-1)^1}{3^1} = \frac{-1}{3} 

 c_2 = \dfrac{(-1)^2}{3^2} = \frac{1}{9} 

 c_3 = \dfrac{(-1)^3}{3^3} = \frac{-1}{27} 

4. d_m = 1 + \left(\dfrac{1}{2}\right)^m for every integer m \geq 0.

 d_0 = 1 + \left(\dfrac{1}{2}\right)^0 = 1 

 d_1 = 1 + \left(\dfrac{1}{2}\right)^1 = \frac{1}{2} 

 d_2 = 1 + \left(\dfrac{1}{2}\right)^2 = \frac{1}{4} 

 d_3 = 1 + \left(\dfrac{1}{2}\right)^3 = \frac{1}{8} 

5. e_n = \left\lfloor \dfrac{n}{2} \right\rfloor \cdot 2, for every integer n \geq 0.

 e_0 = \left\lfloor \dfrac{0}{2} \right\rfloor \cdot 2 = 0 

 e_1 = \left\lfloor \dfrac{1}{2} \right\rfloor \cdot 2 = 0 

 e_2 = \left\lfloor \dfrac{2}{2} \right\rfloor \cdot 2 = 2 

 e_3 = \left\lfloor \dfrac{3}{2} \right\rfloor \cdot 2 = 2 

6. f_n = \left\lfloor \dfrac{n}{4} \right\rfloor \cdot 4, for every integer n \geq 1.

 f_1 = \left\lfloor \dfrac{1}{4} \right\rfloor \cdot 4 = 0 

 f_2 = \left\lfloor \dfrac{2}{4} \right\rfloor \cdot 4 = 0 

 f_3 = \left\lfloor \dfrac{3}{4} \right\rfloor \cdot 4 = 0 

 f_4 = \left\lfloor \dfrac{4}{4} \right\rfloor \cdot 4 = 4 

7. Let a_k = 2k + 1 and b_k = (k - 1)^3 + k + 2 for every integer k \geq 0. Show that the first three terms of these sequences are identical but that their fourth terms differ.

 a_0 = 2(0) + 1 = 1 

 a_1 = 2(1) + 1 = 3 

 a_2 = 2(2) + 1 = 5 

 a_3 = 2(3) + 1 = 7 

 b_0 = (0 - 1)^3 + 0 + 2 = 1 

 b_1 = (1 - 1)^3 + 1 + 2 = 3 

 b_2 = (2 - 1)^3 + 2 + 2 = 5 

 b_3 = (3 - 1)^3 + 3 + 2 = 13 

Compute the first fifteen terms of each of the sequences in 8 and 9, and describe the general behavior of these sequences in words. (A definition of logarithm is given in Section 7.1.)

8. g_n = \lfloor \log_{2}n \rfloor for every integer n \geq 1.

 g_1 = \lfloor \log_{2}(1) \rfloor = 0 

 g_2 = \lfloor \log_{2}(2) \rfloor = 1 

 g_3 = \lfloor \log_{2}(3) \rfloor = 1 

 g_4 = \lfloor \log_{2}(4) \rfloor = 2 

 g_5 = \lfloor \log_{2}(5) \rfloor = 2 

 g_6 = \lfloor \log_{2}(6) \rfloor = 2 

 g_7 = \lfloor \log_{2}(7) \rfloor = 2 

 g_8 = \lfloor \log_{2}(8) \rfloor = 3 

 g_9 = \lfloor \log_{2}(9) \rfloor = 3 

 g_{10} = \lfloor \log_{2}(10) \rfloor = 3 

 g_{11} = \lfloor \log_{2}(11) \rfloor = 3 

 g_{12} = \lfloor \log_{2}(12) \rfloor = 3 

 g_{13} = \lfloor \log_{2}(13) \rfloor = 3 

 g_{14} = \lfloor \log_{2}(14) \rfloor = 3 

 g_{15} = \lfloor \log_{2}(15) \rfloor = 3 

The general behavior of this sequence is that it increments in binary increments, as in it increments every 1, then 2, then 4, then 8 iterations of the index n.

9 h_n = n\lfloor \log_{2}n \rfloor for every integer n \geq 1.

 h_1 = (1)\lfloor \log_{2}(1) \rfloor = 0 

 h_2 = (2)\lfloor \log_{2}(2) \rfloor = 2 

 h_3 = (3)\lfloor \log_{2}(3) \rfloor = 3 

 h_4 = (4)\lfloor \log_{2}(4) \rfloor = 8 

 h_5 = (5)\lfloor \log_{2}(5) \rfloor = 10 

 h_6 = (6)\lfloor \log_{2}(6) \rfloor = 12 

 h_7 = (7)\lfloor \log_{2}(7) \rfloor = 14 

 h_8 = (8)\lfloor \log_{2}(8) \rfloor = 24 

 h_9 = (9)\lfloor \log_{2}(9) \rfloor = 27 

 h_{10} = (10)\lfloor \log_{2}(10) \rfloor = 30 

 h_{11} = (11)\lfloor \log_{2}(11) \rfloor = 33 

 h_{12} = (12)\lfloor \log_{2}(12) \rfloor = 36 

 h_{13} = (13)\lfloor \log_{2}(13) \rfloor = 39 

 h_{14} = (14)\lfloor \log_{2}(14) \rfloor = 42 

 h_{15} = (15)\lfloor \log_{2}(15) \rfloor = 45 

The sequence finds the minimal (floor) power of log_{2}n and then multiplies it by n, which is why there are sudden "jumps" when the floor calculates a jump to the next power of 2. For example, at n = 7 to n = 8, there is a noticeable jump because \lfloor \log_{2}7 \rfloor is 2, and then \lfloor \log_{2}8 \rfloor is 3.

Find explicit formulas for sequences of the form a_1, a_2, a_3, \dots with the initial terms given in 10-16.

10. -1, 1, -1, 1, -1, 1

a_n = (-1)^n where n is an integer such that n \geq 1.

11. 0, 1, -2, 3, -4, 5

a_n = (n - 1)(-1)^{n} where n is an integer such that n \geq 1.

12. \dfrac{1}{4}, \dfrac{2}{9}, \dfrac{3}{16}, \dfrac{4}{25}, \dfrac{5}{36}, \dfrac{6}{49}

a_n = \dfrac{n}{(n + 1)^2} where n is an integer such that n \geq 1.

13. 1 - \dfrac{1}{2}, \dfrac{1}{2} - \dfrac{1}{3}, \dfrac{1}{3} - \dfrac{1}{4}, \dfrac{1}{4} - \dfrac{1}{5}, \dfrac{1}{5} - \dfrac{1}{6}, \dfrac{1}{6} - \dfrac{1}{7}

a_n = \dfrac{1}{n} - \dfrac{1}{n + 1} where n is an integer such that n \geq 1.

14. \dfrac{1}{3}, \dfrac{4}{9}, \dfrac{9}{27}, \dfrac{16}{81}, \dfrac{25}{243}, \dfrac{36}{729}

a_n = \dfrac{n^2}{3^n} where n is an integer such that n \geq 1.

15. 0, -\dfrac{1}{2}, \dfrac{2}{3}, -\dfrac{3}{4}, \dfrac{4}{5}, -\dfrac{5}{6}, \dfrac{6}{7}

a_n = \dfrac{(n - 1)(-1)^{n + 1}}{n} where n is an integer such that n \geq 1.

16. 3, 6, 12, 24, 48, 96

a_n = 3 \cdot 2^{n - 1} where n is an integer such that n \geq 1.

17. Consider the sequence defined by a_n = \dfrac{2n + (-1)^n - 1}{4} for every integer n \geq 0. Find an alternative explicit formula for a_n that uses the floor notation.

Omitted.

18. Let a_0 = 2, a_1 = 3, a_2 = -2, a_3 = 1, a_4 = 0, a_5 = -1, \text{ and } a_6 = -2. Compute each of the summations and products below.

a. \sum_{i = 0}^{6}{a_i}

 \sum_{i = 0}^{6}{a_i} = 2 + 3 + (-2) + 1 + 0 + (-1) + (-2) = 1 

b. \sum_{i = 0}^{0}{a_i}

 \sum_{i = 0}^{0}{a_i} = 2 

c. \sum_{j = 1}^{3}{a_{2j}}

 \sum_{j = 1}^{3}{a_{2j}} = (-2) + 0 + (-2) = -4 

d. \prod_{k = 0}^{6}{a_k}

 \prod_{k = 0}^{6}{a_k} = 2 \cdot 3 \cdot (-2) \cdot 1 \cdot 0 \cdot (-1) \cdot (-2) = 0 

e. \prod_{k = 2}^{2}{a_k}

 \prod_{k = 2}^{2}{a_k} = -2 

Compute the summations and products in 19-28.

19. \sum_{k = 1}^{5}{(k + 1)}

 \sum_{k = 1}^{5}{(k + 1)} = (1 + 1) + (2 + 1) + (3 + 1) + (4 + 1) + (5 + 1) = 20 

20. \prod_{k = 2}^{4}{k^2}

 \prod_{k = 2}^{4}{k^2} = (2)^2 \cdot (3)^2 \cdot (4)^2 = 576 

21. \sum_{k = 1}^{3}{(k^2 + 1)}

 \sum_{k = 1}^{3}{(k^2 + 1)} = ((1)^2 + 1) + ((2)^2 + 1) + ((3)^2 + 1) = 17 

22. \prod_{j = 0}^{4}{(-1)^j}

 \prod_{j = 0}^{4}{(-1)^j} = (-1)^{(0)} \cdot (-1)^{(1)} \cdot (-1)^{(2)} \cdot (-1)^{(3)} \cdot (-1)^{(4)} = 1 

23. \sum_{i = 1}^{1}{i(i + 1)}

 \sum_{i = 1}^{1}{i(i + 1)} = (1)((1) + 1) = 2 

24. \sum_{j = 0}^{0}{(j + 2) \cdot 2^j}

 \sum_{j = 0}^{0}{(j + 2) \cdot 2^j} = (0 + 2) \cdot 2^0 = 2 

25. \prod_{k = 2}^{2}{\left(1 - \dfrac{1}{k}\right)}

 \prod_{k = 2}^{2}{\left(1 - \dfrac{1}{k}\right)} =  \left(1 - \dfrac{1}{2}\right) = \frac{1}{2} 

26. \sum_{k = -1}^{1}{(k^2 + 3)}

 \sum_{k = -1}^{1}{(k^2 + 3)} = ((-1)^2 + 3) + ((0)^2 + 3) + ((1)^2 + 3) = 11 

27. \sum_{n = 1}^{6}{\left(\dfrac{1}{n} - \dfrac{1}{n + 1}\right)}

 \sum_{n = 1}^{6}{\left(\dfrac{1}{n} - \dfrac{1}{n + 1}\right)} = \left(\dfrac{1}{(1)} - \dfrac{1}{(1) + 1}\right) + \left(\dfrac{1}{(2)} - \dfrac{1}{(2) + 1}\right) + \left(\dfrac{1}{(3)} - \dfrac{1}{(3) + 1}\right) + \left(\dfrac{1}{(4)} - \dfrac{1}{(4) + 1}\right) + \left(\dfrac{1}{(5)} - \dfrac{1}{(5) + 1}\right) + \left(\dfrac{1}{(6)} - \dfrac{1}{(6) + 1}\right) = \frac{6}{7} 

28. \prod_{i = 2}^{5}{\dfrac{i(i + 2)}{(i - 1) \cdot (i + 1)}}

 \prod_{i = 2}^{5}{\dfrac{i(i + 2)}{(i - 1) \cdot (i + 1)}} = \dfrac{(2)((2) + 2)}{((2) - 1) \cdot ((2) + 1)} + \dfrac{(3)((3) + 2)}{((3) - 1) \cdot ((3) + 1)} + \dfrac{(4)((4) + 2)}{((4) - 1) \cdot ((4) + 1)} + \dfrac{(5)((5) + 2)}{((5) - 1) \cdot ((5) + 1)} = \frac{35}{3} 

Write the summations in 29-32 in expanded form.

29. \sum_{i = 1}^{n}{(-2)^i}

 \sum_{i = 1}^{n}{(-2)^i} = (-2)^1 + (-2)^2 + (-2)^3 + \dots + (-2)^{n} 

30. \sum_{j = 1}^{n}{j(j + 1)}

 \sum_{j = 1}^{n}{j(j + 1)} = ((1)((1) + 1)) + ((2)((2) + 1)) + ((3)((3) + 1)) + \dots + ((n)((n) + 1)) = 2 + 6 + 12 + \dots n(n + 1) 

31. \sum_{k = 0}^{n + 1}{\dfrac{1}{k!}}

 \sum_{k = 0}^{n + 1}{\dfrac{1}{k!}} = \dfrac{1}{0!} + \dfrac{1}{1!} + \dfrac{1}{2!} + \dots + \dfrac{1}{(n + 1)!} 

32. \sum_{i = 1}^{k + 1}{i(i!)}

 \sum_{i = 1}^{k + 1}{i(i!)} = 1(1!) + 2(2!) + 3(3!) + \dots + (k + 1)((k + 1)!) 

Evaluate the summations and products in 33-36 for the indicated values of the variable.

33. \dfrac{1}{1^2} + \dfrac{1}{2^2} + \dfrac{1}{3^2} + \dots + \dfrac{1}{n^2}; n = 1

 \frac{1}{1^2} = 1 

34. 1(1!) + 2(2!) + 3(3!) + \dots + m(m!); m = 2

 1(1!) + 2(2!) = 5 

35. \left(\dfrac{1}{1 + 1}\right)\left(\dfrac{2}{2 + 1}\right)\left(\dfrac{3}{3 + 1}\right) \dots \left(\dfrac{k}{k + 1}\right); k = 3

 \left(\dfrac{1}{1 + 1}\right)\left(\dfrac{2}{2 + 1}\right)\left(\dfrac{3}{3 + 1}\right) = \frac{1}{4} 

36. \left(\dfrac{1 \cdot 2}{3 \cdot 4}\right)\left(\dfrac{4 \cdot 5}{6 \cdot 7}\right)\left(\dfrac{6 \cdot 7}{8 \cdot 9}\right) \dots \left(\dfrac{m \cdot (m + 1)}{(m + 2) \cdot (m + 3)}\right); m = 1

 \left(\frac{1 \cdot 2}{3 \cdot 4}\right) = \frac{2}{12} = \frac{1}{6} 

Write each of 37-39 as a single summation.

37. \sum_{i = 1}^{k}{i^3 + (k + 1)^3}

 \sum_{i = 1}^{k}{i^3 + (k + 1)^3} = \sum_{i = 1}^{k + 1}{i^3} 

38. \sum_{k = 1}^{m}{\dfrac{k}{k + 1} + \dfrac{m + 1}{m + 2}}

 \sum_{k = 1}^{m}{\dfrac{k}{k + 1} + \dfrac{m + 1}{m + 2}} = \sum_{k = 1}^{m + 1}{\dfrac{k}{k + 1}}  

39. \sum_{m = 0}^{n}{(m + 1)2^m + (n + 2)2^{n + 1}}

 \sum_{m = 0}^{n}{(m + 1)2^m + (n + 2)2^{n + 1}} = \sum_{m = 0}^{n + 1}{(m + 1)2^m} 

Rewrite 40-42 by separating off the final term.

40. \sum_{i = 1}^{k + 1}{i(i!)}

 \sum_{i = 1}^{k + 1}{i(i!)} = \sum_{i = 1}^{k}{i(i!) + (k + 1)(k + 1)!} 

41. \sum_{k = 1}^{m + 1}{k^2}

 \sum_{k = 1}^{m + 1}{k^2} = \sum_{k = 1}^{m}{k^2 + (m + 1)^2} 

42. \sum_{m = 1}^{n + 1}{m(m + 1)}

 \sum_{m = 1}^{n + 1}{m(m + 1)} = \sum_{m = 1}^{n}{m(m + 1) + (n + 1)(n + 2)} 

Write each of 43-52 using summation or product notation.

43. 1^2 - 2^2 + 3^2 - 4^2 + 5^2 - 6^2 + 7^2

 1^2 - 2^2 + 3^2 - 4^2 + 5^2 - 6^2 + 7^2 

 \sum_{k = 1}^{7}{(-1)^{k + 1}k^2} 

44. (1^3 - 1) - (2^3 - 1) + (3^3 - 1) - (4^3 - 1) + (5^3 - 1)

 \sum_{k = 1}^{5}{(-1)^{k + 1}(k^3 - 1)} 

45. (2^2 - 1) \cdot (3^2 - 1) \cdot (4^2 - 1)

 \prod_{k = 2}^{4}{(k^2 - 1)} 

46. \dfrac{2}{3 \cdot 4} - \dfrac{3}{4 \cdot 5} + \dfrac{4}{5 \cdot 6} - \dfrac{5}{6 \cdot 7} + \dfrac{6}{7 \cdot 8}

 \sum_{k=2}^{6}{\dfrac{(-1)^k \cdot k}{(k + 1) \cdot (k + 2)}} 

47. 1 - r + r^2 - r^3 + r^4 - r^5

 \sum_{k = 0}^{5}{(-1)^kr^{k + 1}} 

48. (1 - t) \cdot (1 - t^2) \cdot (1 - t^3) \cdot (1 - t^4)

 \prod_{k = 1}^{4}{(1 - t^k)} 

49. 1^3 + 2^3 + 3^3 + \dots + n^3

 \sum_{k}^{n}{k^3} 

50. \dfrac{1}{2!} + \dfrac{2}{3!} + \dfrac{3}{4!} + \dots + \dfrac{n}{(n + 1)!}

 \sum_{k = 1}^{n}{\frac{k}{(k + 1)!}} 

51. n + (n - 1) + (n - 2) + \dots + 1

 \sum_{k = 0}^{n - 1}{(n - k)} 

52. n + \dfrac{n - 1}{2!} + \dfrac{n - 2}{3!} + \dfrac{n - 3}{4!} + \dots + \dfrac{1}{n!}

 \sum_{k = 0}^{n - 1}{\frac{n - k}{(k + 1)!}} 

Transform each of 53 and 54 by making the change of variable i = k + 1.

 i = k + 1 

 i - 1 = k 

53. \sum_{k = 0}^{5}{k(k - 1)}

 \sum_{k = 0}^{5}{k(k - 1)} = \sum_{i = 1}^{6}{(i - 1)(i - 2)} 

54. \prod_{k = 1}^{n}{\dfrac{k}{k^2 + 4}}

 \prod_{k = 1}^{n}{\dfrac{k}{k^2 + 4}} = \prod_{i = 2}^{n + 1}{\frac{i - 1}{(i - 1)^2 + 4}} 

Transform each of 55-58 by making the change of variable j = i - 1.

 j = i - 1 

 i = j + 1 

55. \sum_{i = 1}^{n + 1}{\dfrac{(i - 1)^2}{i \cdot n}}

 \sum_{i = 1}^{n + 1}{\dfrac{(i - 1)^2}{i \cdot n}} = \sum_{j = 0}^{n}{\frac{j^2}{jn + n}} 

56. \sum_{i = 3}^{n}{\dfrac{i}{i + n - 1}}

 \sum_{i = 3}^{n}{\dfrac{i}{i + n - 1}} = \sum_{j = 2}^{n - 1}{\frac{j + 1}{j + n}} 

57. \sum_{i = 1}^{n - 1}{\dfrac{i}{(n - i)^2}}

 \sum_{i = 1}^{n - 1}{\dfrac{i}{(n - i)^2}} = \sum_{j = 0}^{n - 2}{\frac{j + 1}{(n - j - 1)^2}} 

58. \prod_{i = n}^{2n}{\dfrac{n - i + 1}{n + i}}

 \prod_{i = n}^{2n}{\dfrac{n - i + 1}{n + i}} = \prod_{j = n - 1}^{2n - 1}{\frac{n - j}{n + j + 1}} 

Write each of 59-61 as a single summation or product.

59. 3 \cdot \sum_{k = 1}^{n}{(2k - 3)} + \sum_{k = 1}^{n}{(4 - 5k)}

 \sum_{k = 1}^{n}{3(2k - 3) + (4 - 5k)} 

 \sum_{k = 1}^{n}{(6k - 9 + 4 - 5k)} 

 \sum_{k = 1}^{n}{(k - 5)} 

60. 2 \cdot \sum_{k = 1}^{n}{(3k^2 + 4)} + 5 \cdot \sum_{k = 1}^{n}{(2k^2 - 1)}

 \sum_{k = 1}^{n}{2(3k^2 + 4) + 5(2k^2 - 1)} 

 \sum_{k = 1}^{n}{(6k^2 + 8 + 10k^2 - 5)} 

 \sum_{k = 1}^{n}{(16k^2 + 3)} 

61. \left(\prod_{k = 1}^{n}{\dfrac{k}{k + 1}}\right) \cdot \left(\prod_{k = 1}^{n}{\dfrac{k + 1}{k + 2}}\right)

 \prod_{k = 1}^{n}{\left(\frac{k}{k + 1}\right)\left(\frac{k + 1}{k + 2}\right)} 

 \prod_{k = 1}^{n}{\left(\frac{k(k + 1)}{(k + 1)(k + 2)}\right)} 

 \prod_{k = 1}^{n}{\left(\frac{k\cancel{(k + 1)}}{\cancel{(k + 1)}(k + 2)}\right)} 

 \prod_{k = 1}^{n}{\left(\frac{k}{k + 2}\right)} 

Compute each of 62-76. Assume the values of the variables are restricted so that the expressions are defined.

62. \dfrac{4!}{3!}

 \frac{4!}{3!} = \frac{4 \cdot 3 \cdot 2 \cdot 1}{3 \cdot 2 \cdot 1} = 4 

63. \dfrac{6!}{8!}

 \frac{6!}{8!} = \frac{6!}{8 \cdot 7 \cdot 6!} = \frac{1}{56} 

64. \dfrac{4!}{0!}

 \frac{4!}{0!} = \frac{4 \cdot 3 \cdot 2 \cdot 1}{1} = 24 

65. \dfrac{n!}{(n - 1)!}

 \frac{n!}{(n - 1)!} = \frac{n(n - 1)!}{(n - 1)!} = n 

66. \dfrac{(n - 1)!}{(n + 1)!}

 \frac{(n - 1)!}{(n + 1)!} = \frac{(n - 1)!}{(n + 1)(n)(n - 1)!} = \frac{1}{n(n + 1)} 

67. \dfrac{n!}{(n - 2)!}

 \dfrac{n!}{(n - 2)!} = \frac{n(n - 1)(n - 2)!}{(n - 2)!} = n(n - 1) 

68. \dfrac{((n + 1)!)^2}{(n!)^2}

 \frac{((n + 1)!)^2}{(n!)^2} = \frac{((n + 1)(n!))^2}{(n!)^2} = (n + 1)^2 

69. \dfrac{n!}{(n - k)!}

 (n - k)! = (n - k)(n - k - 1)(n - k - 2) \dots (2)(1) 

 n! = n(n - 1)(n - 2) \dots (n - k + 1)(n - k)(n - k - 1)(n - k - 2) \dots (2)(1) 

 \frac{n!}{(n - k)!} = n(n - 1)(n - 2) \dots (n - k + 1) 

70. \dfrac{n!}{(n - k + 1)!}

 (n - k + 1)! = (n - k + 1)(n - k)(n - k - 1) \dots (2)(1) 

 n! = n(n - 1)(n - 2) \dots (n - k + 2)(n - k + 1)(n - k)(n - k - 1) \dots (2)(1)

 \frac{n!}{(n - k + 1)!} = n(n - 1)(n - 2) \dots (n - k + 2) 

71. \dbinom{5}{3}

 \binom{n}{r} = \frac{n!}{r!(n - r)!} 

 \binom{5}{3} = \frac{5!}{3!(5 - 3)!} 

 = \frac{5 \cdot 4 \cdot 3!}{3!(2)!} 

 = \frac{20}{2 \cdot 1} 

 = 10 

72. \dbinom{7}{4}

 \binom{n}{r} = \frac{n!}{r!(n - r)!} 

 \binom{7}{4} = \frac{7!}{4!(7 - 4)!} 

 = \frac{7 \cdot 6 \cdot 5 \cdot 4!}{4!(3)!} 

 = \frac{210}{3!} 

 = \frac{210}{6} 

 = 35 

73. \dbinom{3}{0}

 \binom{n}{r} = \frac{n!}{r!(n - r)!} 

 \binom{3}{0} = \frac{3!}{0!(3 - 0)!} 

 = \frac{3!}{1(3)!} 

 = 1 

74. \dbinom{5}{5}

 \binom{n}{r} = \frac{n!}{r!(n - r)!} 

 \binom{5}{5} = \frac{5!}{5!(5 - 5)!} 

 = \frac{1}{1(0)!} 

 = 1 

75. \dbinom{n}{n - 1}

 \binom{n}{r} = \frac{n!}{r!(n - r)!} 

 \binom{n}{n - 1} = \frac{n!}{(n - 1)!(n - (n - 1))!} 

 = \frac{n!}{(n - 1)!(n - n + 1)!} 

 = \frac{n!}{(n - 1)!(1)!} 

 = \frac{n(n - 1)!}{(n - 1)!(1)!} 

 = \frac{n}{1} 

 = n 

76. \dbinom{n + 1}{n - 1}

 \binom{n}{r} = \frac{n!}{r!(n - r)!} 

 \binom{n + 1}{n - 1} = \frac{(n + 1)!}{(n - 1)!((n + 1) - (n - 1))!} 

 = \frac{(n + 1)!}{(n - 1)!(n + 1 - n + 1)!} 

 = \frac{(n + 1)!}{(n - 1)!(2)!} 

 = \frac{(n + 1)(n)(n - 1)!}{(n - 1)!(2)!} 

 = \frac{n(n + 1)}{2} 

a. Prove that n! + 2 is divisible by 2, for every integer n \geq 2.

Proof:

Suppose that n is any integer such that n \geq 2.

By the definition of a factorial:

 n! = n \cdot (n - 1) \dots 3 \cdot 2 \cdot 1 

Since n \geq 2, this can be represented as:

n! = \begin{cases} 2 & \text{if } n = 2 \ 3 \cdot 2 \cdot 1& \text{if } n = 3 \ n \cdot (n - 1) \dots \cdot 2 \cdot 1 & \text{if } n > 3 \ \end{cases}

In each case, n! has a factor of 2. Then:

 n! + 2 = 2k + 2 

 n! + 2 = 2(k + 1) 

for some integer k.

Now, k + 1 is an integer by the sum of integers.

Therefore n! + 2 is divisible by 2.

Q.E.D.

b. Prove that n! + k is divisible by k, for every integer n \geq 2 and k = 2, 3, \dots, n.

Proof:

Suppose n is any integer such that n \geq 2, and k is any integer such that 2 \leq k \leq n.

Since 2 \leq k \leq n, it follows that k is one of the factors of n!. Then:

 n! = km 

for some integer m.

By substitution:

 n! + k = km + k 

 = k(m + 1) 

Now, m + 1 is an integer by the sum of integers.

Therefore n! + k is divisible by k.

Q.E.D.

c. Given any integer m \geq 2, is it possible to find a sequence of m - 1 consecutive positive integers none of which is prime? Explain your answer.

Proof:

Suppose m is any integer such that m \geq 2.

Consider the sequence

 m! + 2, m! + 3, \dots, m! + m 

This is a sequence of m - 1 consecutive positive integers.

Let k be any integer such that 2 \leq k \leq m. The $k - 1$^th term of the sequence is m! + k.

Since k \leq m, it follows that k \mid m! (by part b). Then:

 m! = kt 

for some integer t.

Then:

 m! + k = kt + k = k(t + 1) 

Now, t + 1 is an integer by the sum of integers. Thus k divides m! + k and since k \geq 2 and (t + 1) > 1 are both factors greater than or equal to 1, it follows that m! + k is composite.

Therefore every term in the sequence is not prime, so there exists a sequence of m - 1 consecutive positive integers none of which is prime.

Q.E.D.

78. Prove that for all nonnegative integers n and r with

 r + 1 \leq n, \binom{n}{r + 1} = \frac{n - r}{r + 1}\binom{n}{r} 

Proof:

Suppose n and r are any nonnegative integers such that r + 1 \leq n.

The given equation shown is:

 \frac{n - r}{r + 1}\binom{n}{r} = \frac{n - r}{r + 1}\left(\frac{n!}{r!(n - r)!}\right) 

 = \frac{n!(n - r)}{r!(r + 1)(n - r)!}

 = \frac{n!(n - r)}{r!(r + 1)(n - r)(n - r - 1)!}

 = \frac{n!}{r!(r + 1)(n - r - 1)!}

 = \frac{n!}{r!(r + 1)(n - (r + 1))!}

Notice that this in the form of a "n choose $r + 1$":

 \binom{n}{r + 1} 

Therefore, it has been shown that:

 \binom{n}{r + 1} = \frac{n - r}{r + 1}\binom{n}{r} 

Q.E.D.

79. Prove that if p is a prime number and r is an integer with 0 < r < p, then \dbinom{p}{r} is divisible by p.

Proof:

Suppose that p is any prime number and r is any integer such that 0 < r < p.

[We need to show that p \mid \dbinom{p}{r}.]

Consider:

 \binom{p}{r} = \frac{p!}{r!(p - r)!} 

Since 0 < r < p, both r! and (p - r)! are less than p. Thus, the denominator r!(p - r)! can never have a factor of p.

The numerator can be expressed as p! = p(p - 1)!:

 \binom{p}{r} = \frac{p(p - 1)!}{r!(p - r)!} 

Factoring p out of the numerator gives:

 \binom{p}{r} = p \cdot \frac{(p - 1)!}{r!(p - r)!} 

Therefore it has been shown that:

 p \mid \binom{p}{r} 

Q.E.D.

80. Suppose a[1], a[2], a[3], \dots, a[m] is a one-dimensional array and consider the following algorithm segment:

\text{sum } := 0\\ \text{\textbf{for }} k := 1 \text{\textbf{ to }} m\\ \ \ \text{sum } := \text{ sum } + a[k]\\ \text{\textbf{next }} k

Fill in the blanks below so that each algorithm segment performs the same job as the one shown in the exercise statement.

a.

\text{sum } := 0\\ \text{\textbf{for }} i := 0 \text{\textbf{ to \_\_\_\_}}\\ \ \ \text{sum } := \text{\_\_\_\_}\\ \text{\textbf{next }} i

m - 1; \text{sum } + a[i + 1]

b.

\text{sum } := 0\\ \text{\textbf{for }} j := 2 \text{\textbf{ to \_\_\_\_}}\\ \ \ \text{sum } := \text{\_\_\_\_}\\ \text{\textbf{next }} j

m + 1; \text{sum } + a[j - 1]

Use repeated division by 2 to convert (by hand) the integers in 81-83 from base 10 to base 2.

81. 90

 90_{10} = 1011010_2 

82. 98

 98_{10} = 1100010_2 

83. 205

 205_{10} = 11001101_2 

Make a trace table to trace the action of Algorithm 5.1.1 on the input in 84-86.

84. 23

	0	1	2	3	4	5
a	23
r[i]		1	1	1	0	1
q	23	11	5	2	1	0
i	0	1	2	3	4	5

Outputs: 10111, which is 23_{10} = 10111_2.

85. 28

	0	1	2	3	4	5
a	28
r[i]		0	0	1	1	1
q	28	14	7	3	1	0
i	0	1	2	3	4	5

Outputs: 11100, which is 28_{10} = 11100_2.

86. 44

	0	1	2	3	4	5	6
a	44
r[i]		0	0	1	1	0	1
q	44	22	11	5	2	1	0
i	0	1	2	3	4	5	6

Outputs: 101100, which is 44_{10} = 101100_2

87. Write an informal description of an algorithm (using repeated division by 16) to convert a nonnegative integer from decimal notation to hexadecimal notation (base 16).

Input: a [a nonnegative integer]

Algorithm Body:

q := a, i := 0

[Repeatedly perform the integer division of q by 16 until q becomes 0. Store successive remainders in a one-dimensional array r[0], r[1], r[2], \dots r[k]. Even if the initial-value of q equals 0, the loop should execute one time (so that r[0] is computed). Thus the guard condition for the while loop is i = 0 or q \neq 0.]

\text{\textbf{while }}(i = 0 \text{ or } q \neq 0)\\ \ \ r[i] := q \mod 16\\ \ \ q := q \text{ div } 16\\ \ \ \text{[r[i] and q can be obtained by calling the division algorithm.]}\\ \ \ i := i + 1\\ \text{\textbf{end while}}

[After execution of this step, the values of r[0], r[1], \dots, r[i - 1] are all 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, and a = \left(r[i - 1]r[i - 2] \dots r[2]r[1]r[0]\right)_{16}.]

Output: r[0], r[1], r[2], \dots, r[i - 1] [a sequence of integers]

Use the algorithm you developed for exercise 87 to convert the integers in 88-90 to hexadecimal notation.

88. 287

 287_{10} = 11F_{16} 

89. 693

 693_{10} = 1BF_{16} 

91. 2,301

 2301_{10} = 8FD_{16} 

91. Write a formal version of the algorithm you developed for exercise 87.

Already done.

---

Exercise Set 5.2

Page 309

1. Use the technique illustrated at the beginning of this section to show that the statements in (a) and (b) are true.

a. If \left(1 - \dfrac{1}{2}\right)\left(1 - \dfrac{1}{3}\right)\left(1 - \dfrac{1}{4}\right)\left(1 - \dfrac{1}{5}\right) = \dfrac{1}{5} then \left(1 - \dfrac{1}{2}\right)\left(1 - \dfrac{1}{3}\right)\left(1 - \dfrac{1}{4}\right)\left(1 - \dfrac{1}{5}\right)\left(1 - \dfrac{1}{6}\right) = \dfrac{1}{6}.

Since:

 \left(1 - \dfrac{1}{2}\right)\left(1 - \dfrac{1}{3}\right)\left(1 - \dfrac{1}{4}\right)\left(1 - \dfrac{1}{5}\right) = \dfrac{1}{5} 

then we can say that:

 \left(1 - \dfrac{1}{2}\right)\left(1 - \dfrac{1}{3}\right)\left(1 - \dfrac{1}{4}\right)\left(1 - \dfrac{1}{5}\right)\left(1 - \dfrac{1}{6}\right) = \dfrac{1}{6} = \frac{1}{5}\left(1 - \dfrac{1}{6}\right) 

Evaluating this right hand side, we find that:

 \frac{1}{5}\left(1 - \frac{1}{6}\right) 

 = \frac{1}{5}\left(\frac{6}{6} - \frac{1}{6}\right) 

 = \frac{1}{5}\left(\frac{5}{6}\right) 

 = \frac{1}{6} 

Which is equal to the right hand side of the equality to be proved.

b. If \left(1 - \dfrac{1}{2}\right)\left(1 - \dfrac{1}{3}\right)\left(1 - \dfrac{1}{4}\right)\left(1 - \dfrac{1}{5}\right)\left(1 - \dfrac{1}{6}\right) = \dfrac{1}{6} then \left(1 - \dfrac{1}{2}\right)\left(1 - \dfrac{1}{3}\right)\left(1 - \dfrac{1}{4}\right)\left(1 - \dfrac{1}{5}\right)\left(1 - \dfrac{1}{6}\right)\left(1 - \dfrac{1}{7}\right) = \dfrac{1}{7}.

Given that:

 \left(1 - \dfrac{1}{2}\right)\left(1 - \dfrac{1}{3}\right)\left(1 - \dfrac{1}{4}\right)\left(1 - \dfrac{1}{5}\right)\left(1 - \dfrac{1}{6}\right) = \dfrac{1}{6} 

Then, by substitution:

 \left(1 - \dfrac{1}{2}\right)\left(1 - \dfrac{1}{3}\right)\left(1 - \dfrac{1}{4}\right)\left(1 - \dfrac{1}{5}\right)\left(1 - \dfrac{1}{6}\right)\left(1 - \dfrac{1}{7}\right) = \frac{1}{6}\left(1 - \dfrac{1}{7}\right) 

Evaluating this right hand side, we find:

 \frac{1}{6}\left(1 - \frac{1}{7}\right) 

 = \frac{1}{6}\left(\frac{7}{7} - \frac{1}{7}\right) 

 = \frac{1}{6}\left(\frac{6}{7}\right) 

 = \frac{1}{7} 

And this is equal to the right hand side of the equality, and therefore shows that the statement is true.

2. For each positive integer n, let P(n) be the formula

 1 + 3 + 5 + \dots + (2n - 1) = n^2 

a. Write P(1). Is P(1) true?

 P(n) = 1 + 3 + 5 + \dots + (2(n) - 1) = (n)^2  

By 5.2.1:

 P(n) = \frac{(2n - 1)((2n - 1) + 1)}{2} 

 = \frac{(2n - 1)(2n)}{2} 

 = \frac{4n^2 - 2n}{2} 

 = 2n^2 - n 

 P(1) = 1 + 3 + 5 + \dots + (2(1) - 1) = (1)^2  

 = 2(1)^2 - (1) = (1)^2  

 = 2(1) - (1) = (1)  

 = 2 - 1 = 1 

 = 1 = 1 

P(1) is true.

b. Write P(k).

 P(n) = 1 + 3 + 5 + \dots + (2(n) - 1) = (n)^2  

 P(k) = 1 + 3 + 5 + \dots + (2k - 1) = k^2  

c. Write P(k + 1).

 P(n) = 1 + 3 + 5 + \dots + (2(n) - 1) = (n)^2  

 P(k + 1) = 1 + 3 + 5 + \dots + (2(k + 1) - 1) = (k + 1)^2 

Alternatively:

 P(k + 1) = 1 + 3 + 5 + \dots + (2k + 2 - 1) = k^2 + 2k + 1 

 P(k + 1) = 1 + 3 + 5 + \dots + (2k + 1) = k^2 + 2k + 1 

d. In a proof by mathematical induction that the formula holds for every integer n \geq 1, what must be shown in the inductive step?

In a proof by mathematical induction, where P(n) holds for every integer n \geq 1, the inductive step where for some integer k where it is assumed 1 + 3 + 5 + \dots + (2k - 1) = k^2 is true (inductive hypothesis), then 1 + 3 + 5 + \dots + (2(k + 1) - 1) = (k + 1)^2 must be shown to also be true.

3. For each positive integer n, let P(n) be the formula

 1^2 + 2^2 + \dots + n^2 = \frac{n(n + 1)(2n + 1)}{6} 

a. Write P(1). Is P(1) true?

 P(n) = 1^2 + 2^2 + \dots + (n)^2 = \frac{(n)((n) + 1)(2(n) + 1)}{6} 

By 5.2.1:

 P(n) = \frac{(n^2)((n^2) + 1)}{2} 

Then:

 P(1) = 1^2 + 2^2 + \dots + (1)^2 = \frac{(1)((1) + 1)(2(1) + 1)}{6} 

 = 1^2 + 2^2 + \dots + (1)^2 = \frac{(1)((1) + 1)(2(1) + 1)}{6} 

 = \frac{((1)^2)(((1)^2) + 1)}{2}= \frac{(1)((1) + 1)(2(1) + 1)}{6} 

 = \frac{(1)(1 + 1)}{2}= \frac{(1)(2)(2 + 1)}{6} 

 = \frac{(1)(2)}{2}= \frac{(1)(2)(3)}{6} 

 = \frac{2}{2} = \frac{6}{6} 

 = 1 = 1 

P(1) is true.

b. Write P(k).

 P(k) = 1^2 + 2^2 + \dots + k^2 = \frac{(k)(k + 1)(2k + 1)}{6} 

c. Write P(k + 1).

 P(k + 1) = 1^2 + 2^2 + \dots + (k + 1)^2 = \frac{(k + 1)((k + 1) + 1)(2(k + 1) + 1)}{6} 

d. In a proof by mathematical induction that the formula holds for every integer n \geq 1, what must be shown in the inductive step?

In a proof by mathematical induction, where P(n) holds for every integer n \geq 1, the inductive step where for some integer k where it is assumed 1^2 + 2^2 + \dots + k^2 = \frac{(k)(k + 1)(2k + 1)}{6} is true (inductive hypothesis), then 1^2 + 2^2 + \dots + (k + 1)^2 = \frac{(k + 1)((k + 1) + 1)(2(k + 1) + 1)}{6} must be shown to also be true.

4. For each integer n with n \geq 2, let P(n) be the formula

 \sum_{i = 1}^{n - 1}{i(i + 1)} = \frac{n(n - 1)(n + 1)}{3} 

a. Write P(2). Is P(2) true?

 P(n) = \sum_{i = 1}^{(n) - 1}{i(i + 1)} = \frac{(n)((n) - 1)((n) + 1)}{3} 

 P(2) = \sum_{i = 1}^{(2) - 1}{i(i + 1)} = \frac{(2)((2) - 1)((2) + 1)}{3} 

Compute left-hand side:

 \sum_{i = 1}^{(2) - 1}{i(i + 1)} 

 \sum_{i = 1}^{1}{i(i + 1)} 

 \sum_{i = 1}^{1}{i(i + 1)} = (1)((1) + 1) 

 = (1)(2) 

 = 2 

Compute right-hand side:

 \frac{(2)((2) - 1)((2) + 1)}{3} 

 = \frac{(2)(1)(3)}{3} 

 = \frac{6}{3} 

 = 2 

Since both the left hand side and the right hand side are equal, P(2) is true.

b. Write P(k).

 P(k) = \sum_{i = 1}^{(k) - 1}{i(i + 1)} = \frac{(k)((k) - 1)((k) + 1)}{3} 

c. Write P(k + 1).

 P(k + 1) = \sum_{i = 1}^{(k + 1) - 1}{i(i + 1)} = \frac{(k + 1)((k + 1) - 1)((k + 1) + 1)}{3} 

d. In a proof by mathematical induction that the formula holds for every integer n \geq 2, what must be shown in the inductive step?

In a proof by mathematical induction, where P(n) holds for every integer n \geq 2, the inductive step where for some integer k where it is assumed \sum_{i = 1}^{(k) - 1}{i(i + 1)} = \dfrac{(k)((k) - 1)((k) + 1)}{3} is true (inductive hypothesis), then \sum_{i = 1}^{(k + 1) - 1}{i(i + 1)} = \dfrac{(k + 1)((k + 1) - 1)((k + 1) + 1)}{3} must be shown to also be true.

5. Fill in the missing pieces in the following proof that

 1 + 3 + 5 + \dots + (2n - 1) = n^2 

for every integer n \geq 1.

Proof: Let the property P(n) be the equation

 1 + 3 + 5 + \dots + (2n - 1) = n^2 

Show that P(1) is true:

To establish P(1), we must show that when 1 is substituted in place of n, the left-hand side equals the right-hand side. But when n = 1, the left-hand side is the sum of all the odd integers from 1 to 2 \cdot 1 - 1, which is the sum of the odd integers from 1 to 1 and is just 1. The right-hand side is __ (a) __, which also equals 1. So P(1) is true.

Show that for every integer k \geq 1, if P(k) is true then P(k + 1) is true:

Let k be any integer with k \geq 1.

[Suppose P(k) is true. That is:]

Suppose

1 + 3 + 5 \cdot + (2k - 1) = __ (b) __.

[This is the inductive hypothesis.]

[We must show that P(k + 1) is true. That is:]

We must show that __ c __ = __ (d) __.

Now the left-hand side of P(k + 1) is

 1 + 3 + 5 + \dots + (2(k + 1) - 1) 

 = 1 + 3 + 5 + \dots + (2k + 1) 

 = [1 + 3 + 5 + \dots + (2k - 1)] + (2k + 1) 

the next-to-last term is 2k - 1 because __ (e) __

 = k^2 + (2k + 1) 

by __ (f) __

 = (k + 1)^2 

which is the right-hand side of P(k + 1) [as was to be shown].

[Since we have proved the basis step and the inductive step, we conclude that the given statement is true.]

Note: This proof was annotated to help make its logical flow more obvious. In standard mathematical writing, such annotation is omitted.

a. (1)^2

b. k^2

c. 1 + 3 + 5 + \dots + (2(k + 1) - 1)

d. (k + 1)^2

e. the odd integer just before 2k + 1 is 2k - 1

f. inductive hypothesis

Prove each statement in 6-9 using mathematical induction. Do not derive them from Theorem 5.2.1 or Theorem 5.2.2.

6. For every integer n \geq 1,

 2 + 4 + 6 + \dots + 2n = n^2 + n 

Proof (by mathematical induction):

Let P(n) be the equation

 2 + 4 + 6 + \dots + 2n = n^2 + n 

Basis Step: Show that P(1) is true:

To establish P(1), we must show that when 1 is substituted in place of n, the left-hand side equals the right-hand side.

When n = 1, the left-hand side is the sum of all even integers from 2 to 2(1), which is the sum of the even integers from 2 to 2 and is just 2.

The right-hand side is 1^2 + 1, which also equals 2.

Therefore P(1) is true.

Inductive Step:

Show that for every integer k \geq 1, if P(k) is true then P(k + 1) is true:

Let k be any integer with k \geq 1.

Suppose P(k) is true. That is, suppose:

 2 + 4 + 6 + \dots + 2k = k^2 + k 

This is the inductive hypothesis.

We must show that P(k + 1) is true. That is we must show that:

 2 + 4 + 6 + \dots + 2(k + 1) = (k + 1)^2 + (k + 1) 

Now the left-hand side of P(k + 1) is

 2 + 4 + 6 + \dots + 2(k + 1) 

 = [2 + 4 + 6 + \dots + 2k] + (2(k + 1)) 

Where 2k is the next-to-last even term before 2k + 1. Then, by inductive hypothesis:

 = (k^2 + k) + (2(k + 1)) 

Then, by algebra:

 = k^2 + 3k + 2 

Now, the right-hand side is:

 (k + 1)^2 + (k + 1) 

 (k + 1)(k + 1) + (k + 1) 

 (k^2 + 2k + 1) + (k + 1) 

 k^2 + 3k + 2 

Thus, the left-hand and right-hand sides of P(k + 1) are equal. Hence P(k + 1) is true.

Since we have proved the basis step and the inductive step, we conclude that P(n) is true for every integer n \geq 1.

Q.E.D.

7. For every integer n \geq 1,

 1 + 6 + 11 + 16 + \dots + (5n - 4) = \frac{n(5n - 3)}{2} 

Proof (by mathematical induction):

Let P(n) be the equation

 1 + 6 + 11 + 16 + \dots + (5n - 4) = \frac{n(5n - 3)}{2} 

Basis Step:

We must prove P(1):

 1 + 6 + 11 + 16 + \dots + (5(1) - 4) = \frac{(1)(5(1) - 3)}{2} 

When n = 1, the left-hand side is the sum of every fifth integer from 1 to 5(1) - 4, which is 1.

The right-hand side is:

 \frac{(1)(5(1) - 3)}{2} 

 = \frac{1(5 - 3)}{2} 

 = \frac{1(2)}{2} 

 = 1 

Both sides of the equality of P(1) are 1. So P(1) is true.

Inductive Step:

Let k be any integer with k \geq 1.

Suppose that P(k) is true. That is:

 1 + 6 + 11 + 16 + \dots + (5k - 4) = \frac{k(5k - 3)}{2} 

We must show that P(k + 1) is true. That is:

 1 + 6 + 11 + 16 + \dots + (5(k + 1) - 4) = \frac{(k + 1)(5(k + 1) - 3)}{2} 

Evaluating the left-hand side:

 1 + 6 + 11 + 16 + \dots + (5(k + 1) - 4) 

 = [1 + 6 + 11 + 16 + \dots + (5k - 4)] + (5(k + 1) - 4) 

Then, by inductive hypothesis:

 = \frac{k(5k - 3)}{2} + (5(k + 1) - 4) 

Then by algebra:

 = \frac{5k^2 - 3k}{2} + (5k + 5 - 4) 

 = \frac{5k^2 - 3k}{2} + \frac{2(5k + 5 - 4)}{2} 

 = \frac{5k^2 - 3k + 2(5k + 5 - 4)}{2} 

 = \frac{5k^2 - 3k + 10k + 10 - 8}{2} 

 = \frac{5k^2 + 7k + 2}{2} 

Now, the right-hand side:

 \frac{(k + 1)(5(k + 1) - 3)}{2} 

 = \frac{(k + 1)(5k + 5 - 3)}{2} 

 = \frac{5k^2 + 5k + 5k + 5 - 3k - 3}{2} 

 = \frac{5k^2 + 10k + 5 - 3k - 3}{2} 

 = \frac{5k^2 + 7k + 5 - 3}{2} 

 = \frac{5k^2 + 7k + 2}{2} 

which is the left-hand side of P(k + 1). Therefore P(k + 1) is true.

Q.E.D.

8. For every integer n \geq 0,

 1 + 2 + 2^2 + \dots + 2^n = 2^{n + 1} - 1 

Proof (by mathematical induction):

Let P(n) be the equation:

 1 + 2 + 2^2 + \dots + 2^n = 2^{n + 1} - 1 

Basis Step:

Prove P(0) is true.

 P(0) = 1 + 2 + 2^2 + \dots + 2^(0) = 2^{(0) + 1} - 1 

Evaluate the left-hand side when n = 0:

 1 + 2 + 2^2 + \dots + 2^(0) = 2^0 = 1 \quad \text{ when } n = 0 

Evaluate the right-hand side when n = 0:

 2^{(0) + 1} - 1 

 2^1 - 1 

 1 

Both the left-hand and right-hand sides of P(0) are equal. P(0) is true.

Inductive Step:

Let k be any integer with k \geq 0.

Suppose P(k) is true. That is:

 P(k) = 1 + 2 + 2^2 + \dots + 2^k = 2^{k + 1} + 1  

Prove that P(k + 1) is true:

 P(k + 1) = 1 + 2 + 2^2 + \dots + 2^(k + 1) = 2^{(k + 1) + 1} + 1  

 1 + 2 + 2^2 + \dots + 2^(k + 1) = 2^{(k + 1) + 1} + 1  

Evaluate the left-hand side:

 1 + 2 + 2^2 + \dots + 2^(k + 1) 

 [1 + 2 + 2^2 + \dots + 2^k] + 2^(k + 1) 

By inductive hypothesis:

 (2^{k + 1} + 1) + 2^(k + 1) 

 2(2^{k + 1}) + 1 

 2^{k + 2} + 1 

Evaluate the right-hand side:

 2^{(k + 1) + 1} + 1  

 = 2^{k + 2} + 1  

Therefore P(k + 1) is true.

Q.E.D.

9. For every integer n \geq 3,

 4^3 + 4^4 + 4^5 + \dots + 4^n = \frac{4(4^n - 16)}{3} 

Proof by mathematical induction:

Let P(n) be the equation:

 4^3 + 4^4 + 4^5 + \dots + 4^n = \frac{4(4^n - 16)}{3} 

Basis Step:

Prove P(3). That is:

 4^3 + 4^4 + 4^5 + \dots + 4^3 = \frac{4(4^3 - 16)}{3} 

Evaluate left-hand side when n = 3:

 4^3 + 4^4 + 4^5 + \dots + 4^3 = 4^3 = 64 \quad \text{ when } n = 3 

Evaluate right-hand side when n = 3:

 \frac{4(4^3 - 16)}{3} 

 = \frac{4(64 - 16)}{3} 

 = \frac{4(48)}{3} 

 = \frac{192}{3} 

 = 64 

Therefore P(3) is true.

Inductive Step:

Let k be any integer where k \geq 3.

Suppose P(k). That is:

 4^3 + 4^4 + 4^5 + \dots + 4^k = \frac{4(4^k - 16)}{3} 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 4^3 + 4^4 + 4^5 + \dots + 4^{k + 1} = \frac{4(4^{k + 1} - 16)}{3} 

Evaluate left-hand side:

 4^3 + 4^4 + 4^5 + \dots + 4^{k + 1} 

 = [4^3 + 4^4 + 4^5 + \dots + 4^k] + 4^{k + 1} 

By inductive hypothesis:

 = \frac{4(4^k - 16)}{3} + 4^{k + 1} 

 = \frac{4^{k + 1} - 64}{3} + \frac{3(4^{k + 1})}{3} 

 = \frac{4^{k + 1} - 64 + (3(4^{k + 1}))}{3} 

 = \frac{4^{k + 1} + 3(4^{k + 1}) - 64}{3} 

 = \frac{1(4^{k + 1}) + 3(4^{k + 1}) - 64}{3} 

 = \frac{4(4^{k + 1}) - 64}{3} 

 = \frac{4(4^{k + 1} - 16)}{3} 

Evaluate right-hand side:

 \frac{4(4^{k + 1} - 16)}{3} 

Both the left-hand and right-hand sides of P(k + 1) are equal. P(k + 1) is true.

Q.E.D.

Prove each of the statements in 10-18 by mathematical induction.

10. 1^2 + 2^2 + \dots + n^2 = \dfrac{n(n + 1)(2n + 1)}{6}, for every integer n \geq 1.

Proof (by mathematical induction):

Let P(n) be the equation:

 1^2 + 2^2 + \dots + n^2 = \dfrac{n(n + 1)(2n + 1)}{6} 

Basis Step:

Prove P(1). That is:

 1^2 + 2^2 + \dots + (1)^2 = \dfrac{(1)(1 + 1)(2(1) + 1)}{6} 

Evaluate left-hand side when n = 1:

 1^2 + 2^2 + \dots + (1)^2 = 1 

Evaluate right-hand side when n = 1:

 \dfrac{(1)(1 + 1)(2(1) + 1)}{6} 

 = \dfrac{(1)(2)(2 + 1)}{6} 

 = \dfrac{(1)(2)(3)}{6} 

 = \dfrac{6}{6} 

 = 1 

Both the left-hand and right-hand sides of P(1) are equal. Therefore P(1) is true.

Inductive Step:

Let k be any integer where k \geq 1.

Suppose P(k). That is:

 1^2 + 2^2 + \dots + k^2 = \dfrac{k(k + 1)(2k + 1)}{6} 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 1^2 + 2^2 + \dots + (k + 1)^2 = \dfrac{(k + 1)((k + 1) + 1)(2(k + 1) + 1)}{6} 

 1^2 + 2^2 + \dots + (k + 1)^2 = \dfrac{(k + 1)(k + 2)(2k + 2 + 1)}{6} 

 1^2 + 2^2 + \dots + (k + 1)^2 = \dfrac{(k + 1)(k + 2)(2k + 3)}{6} 

Evaluate left-hand side:

 1^2 + 2^2 + \dots + (k + 1)^2 

 = [1^2 + 2^2 + \dots + k^2] + (k + 1)^2 

By inductive hypothesis:

 = \dfrac{k(k + 1)(2k + 1)}{6} + (k + 1)^2 

 = \dfrac{k(k + 1)(2k + 1)}{6} + \frac{6(k + 1)^2}{6} 

 = \dfrac{k(k + 1)(2k + 1) + 6(k + 1)^2}{6} 

 = \dfrac{(k + 1)[k(2k + 1) + 6(k + 1)]}{6} 

 = \dfrac{(k + 1)[2k^2 + k + 6k + 6]}{6} 

 = \dfrac{(k + 1)[2k^2 + 7k + 6]}{6} 

 = \dfrac{(k + 1)(k + 2)(2k + 3)}{6} 

Evaluate right-hand side:

 = \dfrac{(k + 1)(k + 2)(2k + 3)}{6} 

Both the left-hand and right-hand sides of P(k + 1) are equal. Therefore P(k + 1) is true.

Q.E.D.

11. 1^3 + 2^3 + \dots + n^3 = \left[\dfrac{n(n + 1)}{2}\right]^2, for every integer n \geq 1.

Proof (by mathematical induction):

Let P(n) be the equation:

 1^3 + 2^3 + \dots + n^3 = \left[\dfrac{n(n + 1)}{2}\right]^2 

Basis Step:

Prove P(1). That is:

 1^3 + 2^3 + \dots + (1)^3 = \left[\dfrac{(1)((1) + 1)}{2}\right]^2 

Evaluate left-hand when n = 1:

 1^3 + 2^3 + \dots + (1)^3 = 1 

Evaluate right-hand when n = 1:

 \left[\dfrac{(1)((1) + 1)}{2}\right]^2 

 = \left[\dfrac{(1)(2)}{2}\right]^2 

 = \left[\dfrac{2}{2}\right]^2 

 = [1]^2 

 = 1 

Both the left and right hand sides of P(1) are true. Therefore P(1) is true.

Inductive Step:

Let k be any integer where k \geq 1.

Suppose P(k). That is:

 1^3 + 2^3 + \dots + k^3 = \left[\dfrac{k(k + 1)}{2}\right]^2 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 1^3 + 2^3 + \dots + (k + 1)^3 = \left[\dfrac{(k + 1)((k + 1) + 1)}{2}\right]^2 

Evaluate left-hand:

 1^3 + 2^3 + \dots + (k + 1)^3 

 = [1^3 + 2^3 + \dots + k^3] + (k + 1)^3 

By inductive hypothesis:

 = \left[\dfrac{k(k + 1)}{2}\right]^2 + (k + 1)^3 

 = \dfrac{k^2(k + 1)^2}{4} + (k + 1)^3 

 = \dfrac{k^2(k + 1)^2}{4} + \frac{4(k + 1)^3}{4} 

 = \dfrac{k^2(k + 1)^2 + 4(k + 1)^3}{4} 

 = \dfrac{k^2(k + 1)^2 + 4(k + 1)^2(k + 1)}{4} 

 = \dfrac{(k + 1)^2[k^2 + 4(k + 1)]}{4} 

 = \dfrac{(k + 1)^2[k^2 + 4k + 4]}{4} 

 = \dfrac{(k + 1)^2(k + 2)^2}{4} 

 = \left[\dfrac{(k + 1)(k + 2)}{2}\right]^2 

Evaluate right-hand:

 \left[\dfrac{(k + 1)((k + 1) + 1)}{2}\right]^2 

 = \left[\dfrac{(k + 1)(k + 2)}{2}\right]^2 

Both the left and right hand sides of P(k + 1) are equal. Therefore P(k + 1) is true.

Q.E.D.

12. \dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \dots + \dfrac{1}{n(n + 1)} = \dfrac{n}{n + 1}, for every integer n \geq 1.

Proof (by mathematical induction):

Let P(n) be the equation:

 \dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \dots + \dfrac{1}{n(n + 1)} = \dfrac{n}{n + 1} 

Basis Step:

Prove P(1), that is:

 \dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \dots + \dfrac{1}{(1)((1) + 1)} = \dfrac{(1)}{(1) + 1} 

Evaluate left-hand when n = 1:

 \dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \dots + \dfrac{1}{(1)((1) + 1)} = \frac{1}{2} 

Evaluate right-hand when n = 1:

 \dfrac{(1)}{(1) + 1} 

 = \dfrac{1}{2} 

The left and right hand sides of P(1) are equal. Therefore P(1) is true.

Inductive Step:

Let k be any integer where k \geq 1.

Suppose P(k). That is:

 \dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \dots + \dfrac{1}{k(k + 1)} = \dfrac{k}{k + 1} 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 \dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \dots + \dfrac{1}{(k + 1)((k + 1) + 1)} = \dfrac{(k + 1)}{(k + 1) + 1} 

Alternatively:

 \dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \dots + \dfrac{1}{(k + 1)(k + 2)} = \dfrac{k + 1}{k + 2} 

Evaluate left-hand:

 \dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \dots + \dfrac{1}{(k + 1)(k + 2)} 

 = \left[\dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \dots + \frac{1}{k(k + 1)}\right] + \dfrac{1}{(k + 1)(k + 2)} 

By the inductive hypothesis:

 = \dfrac{k}{k + 1} + \dfrac{1}{(k + 1)(k + 2)} 

 = \dfrac{k(k + 2)}{(k + 1)(k + 2)} + \dfrac{1}{(k + 1)(k + 2)} 

 = \dfrac{k(k + 2) + 1}{(k + 1)(k + 2)} 

 = \dfrac{k^2 + 2k + 1}{(k + 1)(k + 2)} 

 = \dfrac{(k + 1)(k + 1)}{(k + 1)(k + 2)} 

 = \dfrac{k + 1}{k + 2} 

Evaluate right-hand:

 \dfrac{k + 1}{k + 2} 

Both the left and right hand sides of P(k + 1) are equal. Therefore P(k + 1) is true.

Q.E.D.

13. \sum_{i = 1}^{n - 1}{i(i + 1)} = \dfrac{n(n - 1)(n + 1)}{3}, for every integer n \geq 2.

Let P(n) be the equation:

 \sum_{i = 1}^{n - 1}{i(i + 1)} = \dfrac{n(n - 1)(n + 1)}{3} 

Basis Step:

Prove P(2). That is:

 \sum_{i = 1}^{(2) - 1}{i(i + 1)} = \dfrac{(2)((2) - 1)((2) + 1)}{3} 

Alternatively:

 \sum_{i = 1}^{1}{i(i + 1)} = \dfrac{(2)(1)(3)}{3} 

 \sum_{i = 1}^{1}{i(i + 1)} = 2 

Evaluate left-hand when n = 2:

 \sum_{i = 1}^{1}{i(i + 1)} 

 = (1)(1 + 1) = 2 

The left and right hand sides of P(2) are equal. Therefore P(2) is true.

Inductive Step:

Let k be any integer where k \geq 2.

Suppose P(k). That is:

 \sum_{i = 1}^{k - 1}{i(i + 1)} = \dfrac{k(k - 1)(k + 1)}{3} 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 \sum_{i = 1}^{(k + 1) - 1}{i(i + 1)} = \dfrac{(k + 1)((k + 1) - 1)((k + 1) + 1)}{3} 

Alternatively:

 \sum_{i = 1}^{k}{i(i + 1)} = \dfrac{(k + 1)(k)(k + 2)}{3} 

 \sum_{i = 1}^{k}{i(i + 1)} = \dfrac{k(k + 1)(k + 2)}{3} 

Evaluate left-hand:

 \sum_{i = 1}^{k}{i(i + 1)} 

 = \left[\sum_{i = 1}^{k - 1}{i(i + 1)}\right] + k(k + 1) 

By the inductive hypothesis:

 = \dfrac{k(k - 1)(k + 1)}{3} + k(k + 1) 

 = \dfrac{k(k - 1)(k + 1)}{3} + \frac{3k(k + 1)}{3} 

 = \dfrac{k(k - 1)(k + 1) + 3k(k + 1)}{3} 

 = \dfrac{k(k + 1)((k - 1) + 3)}{3} 

 = \dfrac{k(k + 1)(k + 2)}{3} 

Evaluate right-hand:

 \dfrac{k(k + 1)(k + 2)}{3} 

The left and right hand sides of P(k + 1) are equal. Therefore P(k + 1) is true.

Q.E.D.

14. \sum_{i = 1}^{n + 1}{i \cdot 2^i} = n \cdot 2^{n + 2} + 2, for every integer n \geq 0.

Proof (by mathematical induction):

Let P(n) be the equation:

 \sum_{i = 1}^{n + 1}{i \cdot 2^i} = n \cdot 2^{n + 2} + 2 

Basis Step:

Prove P(0). That is:

 \sum_{i = 1}^{(0) + 1}{i \cdot 2^i} = (0) \cdot 2^{(0) + 2} + 2 

Alternatively:

 \sum_{i = 1}^{1}{i \cdot 2^i} = (0) \cdot 2^{2} + 2 

 \sum_{i = 1}^{1}{i \cdot 2^i} = 0 + 2 

 \sum_{i = 1}^{1}{i \cdot 2^i} = 2 

Evaluate left-hand when n = 0:

 \sum_{i = 1}^{1}{i \cdot 2^i} 

 = (1) \cdot 2^(1) 

 = 2 

Both the left and right hand sides of P(0) are equal. Therefore P(0) is true.

Inductive Step:

Let k be any integer where k \geq 0.

Suppose P(k). That is:

 \sum_{i = 1}^{k + 1}{i \cdot 2^i} = k \cdot 2^{k + 2} + 2 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 \sum_{i = 1}^{(k + 1) + 1}{i \cdot 2^i} = (k + 1) \cdot 2^{(k + 1) + 2} + 2 

Alternatively:

 \sum_{i = 1}^{k + 2}{i \cdot 2^i} = (k + 1) \cdot 2^{k + 3} + 2 

Evaluate left-hand:

 \sum_{i = 1}^{k + 2}{i \cdot 2^i} 

 = \left[\sum_{i = 1}^{k + 1}{i \cdot 2^i}\right] + (k + 2) \cdot 2^{k + 2} 

By the inductive hypothesis:

 = k \cdot 2^{k + 2} + 2 + (k + 2) \cdot 2^{k + 2} 

 = k(2^{k + 2}) + 2 + (k + 2)(2^{k + 2}) 

 = (2^{k + 2})(k + (k + 2)) + 2 

 = (2^{k + 2})(2k + 2) + 2 

 = 2(2^{k + 2})(k + 1) + 2 

 = (2^{k + 3})(k + 1) + 2 

 = (k + 1) \cdot 2^{k + 3} + 2 

Evaluate right-hand:

 (k + 1) \cdot 2^{k + 3} + 2 

The left and right hand sides of P(k + 1) are equal. Therefore P(k + 1) is true.

Q.E.D.

15. \sum_{i = 1}^{n}{i(i!)} = (n + 1)! - 1, for every integer n \geq 1.

Proof (by mathematical induction):

Let P(n) be the equation:

 \sum_{i = 1}^{n}{i(i!)} = (n + 1)! - 1 

Basis Step:

Prove P(1). That is:

 \sum_{i = 1}^{(1)}{i(i!)} = ((1) + 1)! - 1 

Evaluate left-hand side:

 \sum_{i = 1}^{1}{i(i!)} 

 = 1(1!) = 1 

Evaluate right-hand side:

 ((1) + 1)! - 1 

 = (2)! - 1 

 = (2 \cdot 1) - 1 

 = 2 - 1 

 = 1 

Both sides of P(1) are equal. Therefore P(1) is true.

Inductive Step:

Let k be any integer where k \geq 1.

Suppose P(k). That is:

 \sum_{i = 1}^{k}{i(i!)} = (k + 1)! - 1 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 \sum_{i = 1}^{(k + 1)}{i(i!)} = ((k + 1) + 1)! - 1 

Alternatively:

 \sum_{i = 1}^{k + 1}{i(i!)} = (k + 2)! - 1 

Evaluate left-hand:

 \sum_{i = 1}^{k + 1}{i(i!)} 

 = \left[\sum_{i = 1}^{k}{i(i!)}\right] + (k + 1)(k + 1)! 

By the inductive hypothesis:

 = (k + 1)! - 1 + (k + 1)(k + 1)! 

 = (k + 1)! + (k + 1)(k + 1)! - 1 

 = (k + 1)!(1 + (k + 1)) - 1 

 = (k + 1)!(k + 2) - 1 

 = (k + 2)! - 1 

Evaluate right-hand:

 (k + 2)! - 1 

Both sides of P(k + 1) are equal. Therefore P(k + 1) is true.

Q.E.D.

16. \left(1 - \dfrac{1}{2^2}\right)\left(1 - \dfrac{1}{3^2}\right) \dots \left(1 - \dfrac{1}{n^2}\right) = \dfrac{n + 1}{2n}, for every integer n \geq 2.

Proof (by mathematical induction):

Let P(n) be the equation:

 \left(1 - \dfrac{1}{2^2}\right)\left(1 - \dfrac{1}{3^2}\right) \dots \left(1 - \dfrac{1}{n^2}\right) = \dfrac{n + 1}{2n} 

Basis Step:

Prove P(2). That is:

 \left(1 - \dfrac{1}{2^2}\right)\left(1 - \dfrac{1}{3^2}\right) \dots \left(1 - \dfrac{1}{(2)^2}\right) = \dfrac{(2) + 1}{2(2)} 

Alternatively:

 \left(1 - \dfrac{1}{2^2}\right)\left(1 - \dfrac{1}{3^2}\right) \dots \left(1 - \dfrac{1}{4}\right) = \dfrac{3}{4} 

Evaluate left-hand side when n = 2:

 \left(1 - \dfrac{1}{2^2}\right)\left(1 - \dfrac{1}{3^2}\right) \dots \left(1 - \dfrac{1}{4}\right) 

 = \frac{3}{4} 

Both sides of P(2) are equal. Therefore P(2) is true.

Inductive Step:

Let k be any integer where k \geq 2.

Suppose P(k). That is:

 \left(1 - \dfrac{1}{2^2}\right)\left(1 - \dfrac{1}{3^2}\right) \dots \left(1 - \dfrac{1}{k^2}\right) = \dfrac{k + 1}{2k} 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 \left(1 - \dfrac{1}{2^2}\right)\left(1 - \dfrac{1}{3^2}\right) \dots \left(1 - \dfrac{1}{(k + 1)^2}\right) = \dfrac{(k + 1) + 1}{2(k + 1)} 

Alternatively:

 \left(1 - \dfrac{1}{2^2}\right)\left(1 - \dfrac{1}{3^2}\right) \dots \left(1 - \dfrac{1}{(k + 1)^2}\right) = \dfrac{k + 2}{2k + 2} 

Evaluate left-hand:

 \left(1 - \dfrac{1}{2^2}\right)\left(1 - \dfrac{1}{3^2}\right) \dots \left(1 - \dfrac{1}{(k + 1)^2}\right) 

 = \left[\left(1 - \dfrac{1}{2^2}\right)\left(1 - \dfrac{1}{3^2}\right) \dots \left(1 - \frac{1}{k^2}\right)\right]\left(1 - \dfrac{1}{(k + 1)^2}\right) 

By the inductive hypothesis:

 = \left(\frac{k + 1}{2k}\right)\left(1 - \dfrac{1}{(k + 1)^2}\right) 

 = \left(\frac{k + 1}{2k}\right)\left(\frac{(k + 1)^2}{(k + 1)^2} - \dfrac{1}{(k + 1)^2}\right) 

 = \left(\frac{k + 1}{2k}\right)\left(\dfrac{(k + 1)^2 - 1}{(k + 1)^2}\right) 

 = \frac{(k + 1)((k + 1)^2 - 1)}{2k(k + 1)^2} 

 = \frac{(k + 1)^3 - (k + 1)}{2k(k + 1)^2} 

 = \frac{(k + 1)^2 - 1}{2k(k + 1)} 

 = \frac{(k + 1)(k + 1) - 1}{2k^2 + 2k} 

 = \frac{k^2 + 2k + 1 - 1}{2k^2 + 2k} 

 = \frac{k^2 + 2k}{2k^2 + 2k} 

 = \frac{k(k + 2)}{k(2k + 2)} 

 = \frac{k + 2}{2k + 2} 

Evaluate right-hand:

Both sides of P(k + 1) are equal. Therefore P(k + 1) is true.

Q.E.D.

 \dfrac{k + 2}{2k + 2} 

17. \prod_{i = 0}^{n}{\left(\dfrac{1}{2i + 1} \cdot \dfrac{1}{2i + 2}\right)} = \dfrac{1}{(2n + 2)!}, for every integer n \geq 0.

Proof (by mathematical induction):

Let P(n) be the equation:

 \prod_{i = 0}^{n}{\left(\dfrac{1}{2i + 1} \cdot \dfrac{1}{2i + 2}\right)} = \dfrac{1}{(2n + 2)!} 

Basis Step:

Prove P(0). That is:

 \prod_{i = 0}^{(0)}{\left(\dfrac{1}{2i + 1} \cdot \dfrac{1}{2i + 2}\right)} = \dfrac{1}{(2(0) + 2)!} 

Alternatively:

 \prod_{i = 0}^{(0)}{\left(\dfrac{1}{2i + 1} \cdot \dfrac{1}{2i + 2}\right)} = \dfrac{1}{2!} 

 \prod_{i = 0}^{(0)}{\left(\dfrac{1}{2i + 1} \cdot \dfrac{1}{2i + 2}\right)} = \dfrac{1}{2} 

Evaluate left-hand when n = 0:

 \prod_{i = 0}^{(0)}{\left(\dfrac{1}{2i + 1} \cdot \dfrac{1}{2i + 2}\right)} 

 = \frac{1}{2} 

Both sides of P(0) are equal. Therefore P(0) is true.

Inductive Step:

Let k be any integer where k \geq 0.

Suppose P(k). That is:

 \prod_{i = 0}^{k}{\left(\dfrac{1}{2i + 1} \cdot \dfrac{1}{2i + 2}\right)} = \dfrac{1}{(2k + 2)!} 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 \prod_{i = 0}^{(k + 1)}{\left(\dfrac{1}{2i + 1} \cdot \dfrac{1}{2i + 2}\right)} = \dfrac{1}{(2(k + 1) + 2)!} 

Alternatively:

 \prod_{i = 0}^{k + 1}{\left(\dfrac{1}{2i + 1} \cdot \dfrac{1}{2i + 2}\right)} = \dfrac{1}{(2k + 2 + 2)!} 

 \prod_{i = 0}^{k + 1}{\left(\dfrac{1}{2i + 1} \cdot \dfrac{1}{2i + 2}\right)} = \dfrac{1}{(2k + 4)!} 

Evaluate left-hand:

 \prod_{i = 0}^{k + 1}{\left(\dfrac{1}{2i + 1} \cdot \dfrac{1}{2i + 2}\right)} 

 = \left[\prod_{i = 0}^{k}{\left(\dfrac{1}{2i + 1} \cdot \dfrac{1}{2i + 2}\right)}\right] \cdot \left(\frac{1}{2(k + 1) + 1} \cdot \frac{1}{2(k + 1) + 2}\right) 

By the inductive hypothesis:

 = \left(\frac{1}{(2k + 2)!}\right) \cdot \left(\frac{1}{2(k + 1) + 1} \cdot \frac{1}{2(k + 1) + 2}\right) 

 = \left(\frac{1}{(2k + 2)!}\right) \cdot \left(\frac{1}{2k + 2 + 1} \cdot \frac{1}{2k + 2 + 2}\right) 

 = \left(\frac{1}{(2k + 2)!}\right) \cdot \left(\frac{1}{2k + 3} \cdot \frac{1}{2k + 4}\right) 

 = \frac{1}{(2k + 4)!} 

Evaluate right-hand:

 \dfrac{1}{(2k + 4)!} 

Both sides of P(k + 1) are equal. Therefore P(k + 1) is true.

Q.E.D.

18. \prod_{i = 2}^{n}{\left(1 - \dfrac{1}{i}\right)} = \dfrac{1}{n} for every integer n \geq 2.

Hint: See the discussion at the beginning of this section.

Proof (by mathematical induction):

Let P(n) be the equation:

 \prod_{i = 2}^{n}{\left(1 - \dfrac{1}{i}\right)} = \dfrac{1}{n} 

Basis Step:

Prove P(2). That is:

 \prod_{i = 2}^{2}{\left(1 - \dfrac{1}{i}\right)} = \dfrac{1}{2} 

Evaluate left-hand side when n = 2:

 \prod_{i = 2}^{2}{\left(1 - \dfrac{1}{i}\right)} 

 = 1 - \frac{1}{2} 

 = \frac{1}{2} 

Both sides of P(2) are equal. Therefore P(2) is true.

Inductive Step:

Let k be any integer where k \geq 2.

Suppose P(k). That is:

 \prod_{i = 2}^{k}{\left(1 - \dfrac{1}{i}\right)} = \dfrac{1}{k} 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 \prod_{i = 2}^{k + 1}{\left(1 - \dfrac{1}{i}\right)} = \dfrac{1}{k + 1} 

Evaluate left-hand side:

 \prod_{i = 2}^{k + 1}{\left(1 - \dfrac{1}{i}\right)} 

 = \left[\prod_{i = 2}^{k}{\left(1 - \dfrac{1}{i}\right)}\right] \cdot \left(1 - \frac{1}{k + 1}\right) 

By the inductive hypothesis:

 = \dfrac{1}{k} \cdot \left(1 - \frac{1}{k + 1}\right) 

 = \dfrac{1}{k} \cdot \left(\frac{k + 1}{k + 1} - \frac{1}{k + 1}\right) 

 = \dfrac{1}{k} \cdot \left(\frac{(k + 1) - 1}{k + 1}\right) 

 = \dfrac{1}{k} \cdot \left(\frac{k}{k + 1}\right) 

 = \frac{1}{k + 1} 

Evaluate right-hand side:

 \dfrac{1}{k + 1} 

Both sides of P(k + 1) are equal. Therefore P(k + 1) is true.

Q.E.D.

19. (For students who have studied calculus) Use mathematical induction, the product rule from calculus, and the facts that \dfrac{d(x)}{dx} = 1 and that x^{k + 1} = x \cdot x^k to prove that for every integer n \geq 1, \dfrac{d(x^n)}{dx} = nx^{n - 1}.

Proof (by mathematical induction):

Let P(n) be the equation:

 \frac{d(x^n)}{dx} = nx^{n - 1} 

Basis Step:

Prove P(1). That is:

 \frac{d(x^{(1)})}{dx} = (1)x^{(1) - 1} 

Alternatively:

 \frac{dx}{dx} = 1x^0 

Evaluate the left-hand side when n = 1:

 \frac{dx}{dx} 

By the given fact that \dfrac{dx}{dx} = 1:

 = 1 

Evaluate the right-hand side when n = 1:

 = 1x^0 

 = 1 

Both the left and right hand sides of P(1) are equal. Therefore P(1) is true.

Inductive Step:

Let k be any integer where k \geq 1.

Suppose P(k). That is:

 \frac{d(x^k)}{dx} = kx^{k - 1} 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 \frac{d(x^{(k + 1)})}{dx} = (k + 1)x^{(k + 1) - 1} 

Alternatively:

 \frac{d(x^{(k + 1)})}{dx} = (k + 1)x^k 

Evaluate left-hand side:

 \frac{d(x^{(k + 1)})}{dx} 

 \frac{d(x \cdot x^k)}{dx} 

By the product rule, we can separate this out into:

 \frac{dx}{dx} \cdot x^k + x \cdot \dfrac{d(x^k)}{dx} 

By the given fact that \dfrac{dx}{dx} = 1:

 1 \cdot x^k + x \cdot \dfrac{d(x^k)}{dx} 

By the inductive hypothesis:

 1 \cdot x^k + x \cdot kx^{k - 1}  

 x^k  + x \cdot kx^{k - 1}  

 x^k + kx^{k - 1 + 1}  

 x^k + kx^{k}  

 x^k(1 + k)  

 (k + 1)x^k  

Evaluate right-hand side:

 (k + 1)x^k 

Both the left and right sides of P(k + 1) are equal. Therefore P(k + 1) is true.

Q.E.D.

Use the formula for the sum of the first n integers and/or the formula for the sum of a geometric sequence to evaluate the sums in 20-29 or to write them in closed form.

20. 4 + 8 + 12 + 16 + \dots + 200

 4 + 8 + 12 + 16 + \dots + 200 

 = 4(1 + 2 + 3 + 4 + \dots + 50) 

 = 4\frac{50(51)}{2} 

 = 5100 

21. 5 + 10 + 15 + 20 + \dots + 300

 5 + 10 + 15 + 20 + \dots + 300 

 = 5(1 + 2 + 3 + 4 + \dots 60) 

 = 5\left(\frac{(60)(61)}{2}\right) 

 = 9150 

a. 3 + 4 + 5 + 6 + \dots + 1000

 3 + 4 + 5 + 6 + \dots + 1000 

 = (1 + 2 + 3 + 4 + \dots + 1000) - (1 + 2) 

 = \left(\frac{(1000)(1001)}{2}\right) - 3 

 = 500497 

b. 3 + 4 + 5 + 6 + \dots + m

 3 + 4 + 5 + 6 + \dots + m 

 = (1 + 2 + 3 + 4+ \dots + m) - (1 + 2) 

 = \left(\frac{(m)(m + 1)}{2}\right) - 3 

 = \frac{m^2 + m}{2} - 3 

 = \frac{m^2 + m}{2} - \frac{6}{2} 

 = \frac{m^2 + m - 6}{2} 

a. 7 + 8 + 9 + 10 + \dots + 600

 7 + 8 + 9 + 10 + \dots + 600 

 = (1 + 2 + 3 + 4 + \dots + 600) - (1 + 2 + 3 + 4 + 5 + 6) 

 = \left(\frac{(600)(601)}{2}\right) - 21 

 = 180279 

b. 7 + 8 + 9 + 10 + \dots + k

 7 + 8 + 9 + 10 + \dots + k 

 = (1 + 2 + 3 + 4 + \dots + k) - (1 + 2 + 3 + 4 + 5 + 6) 

 = \left(\frac{(k)(k + 1)}{2}\right) - 21 

 = \frac{k^2 + k}{2} - 21 

 = \frac{k^2 + k - 42}{2} 

24. 1 + 2 + 3 + \dots + (k - 1), where k is any integer with k \geq 2.

 1 + 2 + 3 + \dots + (k - 1) 

 = \frac{(k - 1)((k - 1) + 1)}{2} 

 = \frac{(k - 1)(k)}{2} 

 = \frac{k^2 - k}{2} 

a. 1 + 2 + 2^2 + \dots + 2^{25}

 1 + 2 + 2^2 + \dots + 2^{25} 

 = \frac{2^{25 + 1} - 1}{2^{25} - 1} 

 = \frac{2^{26} - 1}{2 - 1} 

 = 67108863 

b. 2 + 2^2 + 2^3 + \dots + 2^{26}

 2 + 2^2 + 2^3 + \dots + 2^{26} 

 k 2(1 + 2 + 2^2 + \dots + 2^{25}) 

By part a:

 = 2(67108863) 

 = 134217726 

c. 2 + 2^2 + 2^3 + \dots + 2^n

 2 + 2^2 + 2^3 + \dots + 2^n 

 2(1 + 2 + 2^2 + \dots + 2^{n - 1}) 

 2\left(\frac{2^{(n - 1) + 1} - 1}{2 - 1}\right) 

 2\left(\frac{2^n - 1}{1}\right) 

 2(2^n - 1) 

 2^{n + 1} - 2 

26. 3 + 3^2 + 3^3 + \dots + 3^n, where n is any integer with n \geq 1.

 3 + 3^2 + 3^3 + \dots + 3^n 

 3(1 + 3 + 3^2 + \dots + 3^{n - 1}) 

 3\left(\frac{3^{(n - 1) + 1} - 1}{3 - 1}\right) 

 3\left(\frac{3^n - 1}{2}\right) 

 \frac{3^{n + 1} - 3}{2} 

27. 5^3 + 5^4 + 5^5 + \dots + 5^k, where k is any integer with k \geq 3.

 5^3 + 5^4 + 5^5 + \dots + 5^k 

 = 5^3(1 + 5 + 5^2 + \dots + 5^{k - 3}) 

 = 5^3\left(\frac{5^{(k - 3) + 1} - 1}{5 - 1}\right) 

 = 5^3\left(\frac{5^{k - 2} - 1}{4}\right) 

 = \frac{5^{k - 2 + 3} - 5^3}{4} 

 = \frac{5^k - 5^3}{4} 

28. 1 + \dfrac{1}{2} + \dfrac{1}{2^2} + \dots + \dfrac{1}{2^n}, where n is any positive integer.

 1 + \dfrac{1}{2} + \dfrac{1}{2^2} + \dots + \dfrac{1}{2^n} 

 = \frac{\left(\dfrac{1}{2}\right)^{n + 1} - 1}{\dfrac{1}{2} - 1} 

 = \frac{\left(\dfrac{1}{2}\right)^{n + 1} - 1}{-\dfrac{1}{2}} 

 = \left[\left(\dfrac{1}{2}\right)^{n + 1} - 1\right](-2) 

 = \left(\dfrac{-2}{2}\right)^{n + 1} + 2 

 = 2 - \left(\dfrac{-2}{2}\right)^{n + 1} 

 = 2 + \dfrac{1}{2^n} 

29. 1 - 2 + 2^2 - 2^3 + \dots + (-1)^n2^n, where n is any positive integer.

 1 - 2 + 2^2 - 2^3 + \dots + (-1)^n2^n 

 = 1 + (-2) + (-2)^2 + (-2)^3 + \dots + (-2)^n 

 = \frac{(-2)^{n + 1} - 1}{(-2) - 1} 

 = \frac{(-2)^{n + 1} - 1}{-3} 

30. Observe that

 \frac{1}{1 \cdot 3} = \frac{1}{3} 

 \frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} = \frac{2}{5} 

 \frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} + \frac{1}{5 \cdot 7} = \frac{3}{7} 

 \frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} + \frac{1}{5 \cdot 7} + \frac{1}{7 \cdot 9} = \frac{4}{9} 

Guess a general formula and prove it by mathematical induction.

General formula:

 \frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} + \frac{1}{5 \cdot 7} + \dots + \frac{1}{(2n - 1)(2n + 1)} = \frac{n}{2n + 1} 

for all integers n \geq 1.

Proof (by mathematical induction):

Let P(n) be the equation:

 \frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} + \frac{1}{5 \cdot 7} + \dots + \frac{1}{(2n - 1)(2n + 1)} = \frac{n}{2n + 1} 

Basis Step:

Prove P(1):

 \frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} + \frac{1}{5 \cdot 7} + \dots + \frac{1}{(2(1) - 1)(2(1) + 1)} = \frac{(1)}{2(1) + 1} 

Evaluate left-hand side when n = 1:

 \frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} + \frac{1}{5 \cdot 7} + \dots + \frac{1}{(2(1) - 1)(2(1) + 1)} 

 = \frac{1}{(2 - 1)(2 + 1)}

 = \frac{1}{(1)(3)}

 = \frac{1}{3} 

Evaluate right-hand side when n = 1:

 \frac{(1)}{2(1) + 1} 

 \frac{1}{2 + 1} 

 \frac{1}{3} 

The left and right hand sides of P(1) are equal. Therefore P(1) is true.

Inductive Step:

Let k be any integer where k \geq 1.

Suppose P(k). That is:

 \frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} + \frac{1}{5 \cdot 7} + \dots + \frac{1}{(2k - 1)(2k + 1)} = \frac{k}{2k + 1} 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 \frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} + \frac{1}{5 \cdot 7} + \dots + \frac{1}{(2(k + 1) - 1)(2(k + 1) + 1)} = \frac{(k + 1)}{2(k + 1) + 1} 

Alternatively:

 \frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} + \frac{1}{5 \cdot 7} + \dots + \frac{1}{(2k + 2 - 1)(2k + 2 + 1)} = \frac{k + 1}{2k + 2 + 1} 

 \frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} + \frac{1}{5 \cdot 7} + \dots + \frac{1}{(2k + 1)(2k + 3)} = \frac{k + 1}{2k + 3} 

Evaluate the left-hand side:

 \frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} + \frac{1}{5 \cdot 7} + \dots + \frac{1}{(2k + 1)(2k + 3)} 

 = \left[\frac{1}{1 \cdot 3} + \frac{1}{3 \cdot 5} + \frac{1}{5 \cdot 7} + \dots + \frac{1}{(2k - 1)(2k + 1)}\right] + \frac{1}{(2k + 1)(2k + 3)} 

By the inductive hypothesis:

 = \frac{k}{2k + 1} + \frac{1}{(2k + 1)(2k + 3)} 

 = \frac{k(2k + 3)}{(2k + 1)(2k + 3)} + \frac{1}{(2k + 1)(2k + 3)} 

 = \frac{k(2k + 3) + 1}{(2k + 1)(2k + 3)} 

 = \frac{2k^2 + 3k + 1}{(2k + 1)(2k + 3)} 

 = \frac{(2k + 1)(k + 1)}{(2k + 1)(2k + 3)} 

 = \frac{k + 1}{2k + 3} 

Evaluate the right-hand side:

 \frac{k + 1}{2k + 3} 

Both sides of P(k + 1) are equal. Therefore P(k + 1) is true.

Q.E.D.

31. Compute values of the product

 \left(1 + \frac{1}{1}\right)\left(1 + \frac{1}{2}\right)\left(1 + \frac{1}{3}\right) \dots \left(1 + \frac{1}{n}\right) 

for small values of n in order to conjecture a general formula for the product. Prove your conjecture by mathematical induction.

32. Observe that

 1 = 1 

 1 - 4 = -(1 + 2) 

 1 - 4 + 9 = 1 + 2 + 3 

 1 - 4 + 9 - 16 = -(1 + 2 + 3 + 4) 

 1 - 4 + 9 - 16 + 25 = 1 + 2 + 3 + 4 + 5 

Guess a general formula and prove it by mathematical induction.

 1 - 4 + 9 - 16 + \dots + (-1)^{n - 1}(n^2) = (-1)^{n - 1}(1 + 2 + 3 + 4 + \dots + n) 

Proof (by mathematical induction):

Let P(n) be the equation:

 1 - 4 + 9 - 16 + \dots + (-1)^{n - 1}(n^2) = (-1)^{n - 1}(1 + 2 + 3 + 4 + \dots + n) 

for all integers n \geq 1.

Basis Step:

Prove P(1). That is:

 1 - 4 + 9 - 16 + \dots + (-1)^{(1) - 1}((1)^2) = (-1)^{(1) - 1}(1 + 2 + 3 + 4 + \dots + (1)) 

Evaluate left-hand side when n = 1:

 1 - 4 + 9 - 16 + \dots + (-1)^{(1) - 1}((1)^2) 

 = (-1)^{0}(1^2) 

 = 1(1) 

 = 1 

Evaluate right-hand side when n = 1:

 (-1)^{(1) - 1}(1 + 2 + 3 + 4 + \dots + (1)) 

 = 1 

Both sides of P(1) are equal. Therefore P(1) is true.

Inductive Step:

Let k be any integer where k \geq 1.

Suppose P(k). That is:

 1 - 4 + 9 - 16 + \dots + (-1)^{k - 1}(k^2) = (-1)^{k - 1}(1 + 2 + 3 + 4 + \dots + k) 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 1 - 4 + 9 - 16 + \dots + (-1)^{(k + 1) - 1}((k + 1)^2) = (-1)^{(k + 1) - 1}(1 + 2 + 3 + 4 + \dots + (k + 1)) 

Alternatively:

 1 - 4 + 9 - 16 + \dots + (-1)^{k}((k + 1)^2) = (-1)^{k}(1 + 2 + 3 + 4 + \dots + (k + 1)) 

Evaluate left-hand:

 1 - 4 + 9 - 16 + \dots + (-1)^{k}((k + 1)^2) 

 = \left[1 - 4 + 9 - 16 + \dots + (-1)^{k - 1}(k^2)\right] + (-1)^{k}((k + 1)^2) 

By the inductive hypothesis:

 = (-1)^{k - 1}(1 + 2 + 3 + 4 + \dots + k) + (-1)^{k}((k + 1)^2) 

 = (-1)^{k - 1}\left[(1 + 2 + 3 + 4 + \dots + k) - (k + 1)^2\right] 

By 5.2.1:

 = (-1)^{k - 1}\left[\frac{k(k + 1)}{2} - (k + 1)^2\right] 

 = (-1)^{k - 1}\left[(k + 1)\left(\frac{k}{2} - (k + 1)\right)\right] 

 = (-1)^{k - 1}\left[(k + 1)\left(\frac{k}{2} - \frac{2(k + 1)}{2}\right)\right] 

 = (-1)^{k - 1}\left[(k + 1)\left(\frac{k - 2(k + 1)}{2}\right)\right] 

 = (-1)^{k - 1}\left[(k + 1)\left(\frac{k - 2k - 2)}{2}\right)\right] 

 = (-1)^{k - 1}\left[(k + 1)\left(\frac{-k - 2)}{2}\right)\right] 

 = (-1)^{k - 1}\left[(-1)(k + 1)\left(\frac{k + 2}{2}\right)\right] 

 = (-1)^{k - 1}\left[(-1)\left(\frac{(k + 1)(k + 2)}{2}\right)\right] 

 = (-1)^{k}\left(\frac{(k + 1)(k + 2)}{2}\right) 

By 5.2.1:

 = (-1)^{k}(1 + 2 + 3 + 4 + \dots + (k + 1)) 

Evaluate right-hand:

 (-1)^{k}(1 + 2 + 3 + 4 + \dots + (k + 1)) 

Both sides of P(k + 1) are equal. Therefore P(k + 1) is true.

Q.E.D.

33. Find a formula in n, a, m, and d for the sum (a + md) + (a + (m + 1)d) + (a + (m + 2)d) + \dots + (a + (m + n)d), where m and n are integers, n \geq 0, and a and d are real numbers. Justify your answer.

 a + (a + d) + (a + 2d) + \dots (a + nd) = (n + 1)a + d\left(\frac{n(n + 1)}{2}\right) 

34. Find a formula in a, r, m, and n for the sum

 ar^m + ar^{m + 1} + ar^{m + 2} + \dots + ar^{m + n} 

where m and n are integers, n \geq 0, and a and r are real numbers. Justify your answer.

 ar^m + ar^{m + 1} + ar^{m + 2} + \dots + ar^{m + n} = ar^m\left(\frac{r^{n + 1} - 1}{r - 1}\right) 

By factoring out the ar^m, this just becomes a geometric series:

 ar^m(1 + r + r^2 + r^3 + \dots r^n) 

And by 5.2.2, we can substitute that series out with:

 ar^m\left(\frac{r^{n + 1} - 1}{r - 1}\right) 

35. You have two parents, four grandparents, eight great-grandparents, and so forth.

a. If all your ancestors were distinct, what would be the total number of your ancestors for the past 40 generations (counting your parents' generation as number one)? (Hint: Use the formula for the sum of a geometric sequence.)

The geometric sequence for this is:

 1 + 2 + 2^2 + 2^3 + \dots + 2^n 

So, by 5.2.2, this is:

 \frac{2^{n + 1} - 1}{2 - 1} 

Where n is the number of generations. Plugging in 39 (since we count as the first generation) returns:

 \frac{2^{39 + 1} - 1}{2 - 1} 

 = \frac{2^{40} - 1}{1} 

 = 2^{40} - 1 

 = 1099511627775 

b. Assuming that each generation represents 25 years, how long is 40 generations?

 25 \cdot 1099511627775 

 \approx 2.748779069 \cdot 10^{13} \text{ years} 

c. The total number of people who have ever lived is approximately 10 billion, which equals 10^{10} people. Compare this fact with the answer to part (a). What can you deduce?

When demarcated for easier reading, part a's answer reads as:

 = 1,099,511,627,775 

Which is 1 trillion, 99 billion, 511 million, 627 thousand, 775 people. Since this exceeds the approximate total number of people who have ever lived. We can deduce that some(probably many) of my ancestors must have been related to one another.

Find the mistakes in the proof fragments in 36-38.

Theorem:

For any integer n \geq 1,

 1^2 + 2^2 + \dots + n^2 = \frac{n(n + 1)(2n + 1)}{6} 

"Proof (by mathematical induction):

Certainly the theorem is true for n = 1 because 1^2 = 1 and \dfrac{1(1 + 1)(2 \cdot 1 + 1)}{6} = 1 . So the basis step is true. For the inductive step, suppose that k is any integer with k \geq 1, k^2 = \dfrac{k(k + 1)(2k + 1)}{6}. We must show that (k + 1)^2 = \dfrac{(k + 1)((k + 1) + 1)(2(k + 1) + 1)}{6}."

In the inductive step, the inductive hypothesis reads:

 k^2 = \frac{k(k + 1)(2k + 1)}{6} 

But it should read:

 1^2 + 2^2 + \dots + k^2 = \frac{k(k + 1)(2k + 1)}{6} 

This error cascades into their proof, which reads:

 (k + 1)^2 = \frac{(k + 1)((k + 1) + 1)(2(k + 1) + 1)}{6} 

But instead should read:

 1^2 + 2^2 + \dots + (k + 1)^2 = \frac{(k + 1)((k + 1) + 1)(2(k + 1) + 1)}{6} 

Theorem:

For any integer n \geq 0,

 1 + 2 + 2^2 + \dots + 2^n = 2^{n + 1} - 1 

"Proof (by mathematical induction):

Let the property P(n) be

 1 + 2 + 2^2 + \dots + 2^n = 2^{n + 1} - 1 

Show that P(0) is true:

The left-hand side of P(0) is 1 + 2 + 2^2 + \dots + 2^0 = 1 and the right-hand side is 2^{0 + 1} - 1 = 2 - 1 = 1 also. So P(0) is true."

The left-hand side evaluation should instead read:

The left-hand side of P(0) is 2^0 = 1 since when n = 0, only the first term is evaluated..

Theorem:

For any integer n \geq 1,

 \sum_{i = 1}^{n}{i(i!)} = (n + 1)! - 1 

"Proof (by mathematical induction):

Let the property P(n) be

 \sum_{i = 1}^{n}{i(i!)} = (n + 1)! - 1 

Show that P(1) is true:

When n = 1,

 \sum_{i = 1}^{i}{i(i!)} = (1 + 1)! - 1 

So

 1(1!) = 2! - 1

and

 1 = 1 

Thus P(1) is true."

The author of this proof fragment incorrectly rewrites the upper limit as i instead of 1. They write:

 \sum_{i = 1}^{i}{i(i!)} = (1 + 1)! - 1 

When it should be:

 \sum_{i = 1}^{1}{i(i!)} = (1 + 1)! - 1 

Then, they should evaluate each side independently, but instead they simply evaluate each together, which is incorrect. Instead the basis step should be written as:

Evaluate the left-hand side when n = 1:

 \sum_{i = 1}^{1}{i(i!)} 

 = 1(1!) 

 = 1(1) 

 = 1 

Evaluate the right-hand side when n = 1:

 (1 + 1)! - 1 

 = (2)! - 1 

 = (2 \cdot 1) - 1 

 = 2 - 1 

 = 1 

Both sides of P(1) are equal. Therefore P(1) is true.

39. Use Theorem 5.2.1 to prove that if m and n are any positive integers and m is odd, then \sum_{k = 0}^{m - 1}{(n + k)} is divisible by m. Does the conclusion hold if m is even? Justify your answer.

Omitted.

40. Use Theorem 5.2.1 and the result of exercise 10 to prove that if p is any prime number with p \geq 5, then the sum of the squares of any p consecutive integers is divisible by p.

Omitted.

---

Exercise Set 5.3

Page 320

1. Use mathematical induction (and the proof of proposition 5.3.1 as a model) to show that any amount of money of at least 14¢ can be made up using 3¢ and 8¢ coins.

Proof (by mathematical induction):

Let P(n) be the sentence:

$n$¢ can be obtained using $3$¢ and $8$¢ coins.

Basis Step:

Prove P(14):

P(14) is true because $14$¢ can be obtained using one $8$¢ coin and two $3$¢ coins.

Inductive Step:

Let k be any integer where k \geq 14.

Suppose P(k) is true. That is:

$k$¢ can be obtained using $3$¢ and $8$¢ coins.

Prove P(k + 1). That is:

$k + 1$¢ can be obtained using $3$¢ and $8$¢ coins.

Case 1 (there is a $8$¢ coin among those used to make up $k$¢):

In this case, replace the $8$¢ coin with three $3$¢ coins. The result will be $k + 1$¢.

Case 2 (there is not a $8$¢ coin among those used to make up $k$¢):

In this case, because k \geq 14, at least 5 $3$¢ coins must have been used. So remove five $3$¢ coins and replace them with two $8$¢ coins. The result will be $k + 1$¢.

Therefore in either case $(k + 1)$¢ can be obtained using $3$¢ and $8$¢ coins.

Q.E.D.

2. Use mathematical induction to show that any postage of at least 12¢ can be obtained using 3¢ and 7¢ stamps.

Proof (by mathematical induction):

Let P(n) be the sentence:

$n$¢ postage can be obtained using $3$¢ and $7$¢ stamps.

Basis Step:

Prove P(12). That is:

$12$¢ postage can be obtained using $3$¢ and $7$¢ stamps.

$12$¢ can be obtained using four $3$¢ stamps. Therefore P(12) is true.

Inductive Step:

Let k be any integer where k \geq 12.

Suppose P(k). That is:

$k$¢ postage can be obtained using $3$¢ and $7$¢ stamps.

Prove P(k + 1). That is:

$(k + 1)$¢ postage can be obtained using $3$¢ and $7$¢ stamps.

Case 1 (at least one 2 $3$¢ stamps are used to make up $k$¢):

Replace the two $3$¢ stamps with a $7$¢ stamp. This results in $(k + 1)$¢.

Case 2 (there are 1 or 0 $3$¢ stamps among those used to make up $k$¢):

Replace two $7$¢ stamps with five $3$¢ stamps. This results in $(k + 1)$¢.

Therefore, in both cases (k + 1) postage can be obtained using $3$¢ and $7$¢ stamps.

Q.E.D.

3. Stamps are sold in packages containing either 5 stamps or 8 stamps.

a. Show that a person can obtain 5, 8, 10, 13, 15, 16, 20, 21, 24, or 25 stamps by buying a collection of 5-stamp packages and 8-stamp packages.

• 5 stamps can be obtained by purchasing one 5 stamp package.

• 8 stamps can be obtained by purchasing one 8 stamp package.

• 10 stamps can be obtained by purchasing two 5 stamp packages.

• 13 stamps can be obtained by purchasing one 5 stamp package and one 8 stamp package.

• 15 stamps can be obtained by purchasing three 5 stamp packages.

• 16 stamps can be obtained by purchasing two 8 stamp packages.

• 20 stamps can be obtained by purchasing four 5 stamp packages.

• 21 stamps can be obtained by purchasing two 8 stamp packages and one 5 stamp package.

• 24 stamps can be obtained by purchasing three 8 stamp packages.

• 25 stamps can be obtained by purchasing five 5 stamp packages.

b. Use mathematical induction to show that any quantity of at least 28 stamps can be obtained by buying a collection of 5-stamp packages and 8-stamp packages.

Proof (by mathematical induction):

Let P(n) be the sentence:

n stamps can be obtained by buying a collection of 5-stamp packages and 8-stamp packages.

Basis Step:

Prove P(28). That is:

28 stamps can be obtained by buying a collection of 5-stamp packages and 8-stamp packages.

28 stamps can be obtained by buying four 5-stamp packages and one 8-stamp package.

Therefore P(28) is true.

Inductive Step:

Let k be any integer where k \geq 28.

Suppose P(k). That is:

k stamps can be obtained by buying a collection of 5-stamp packages and 8-stamp packages.

Prove P(k + 1). That is:

(k + 1) stamps can be obtained by buying a collection of 5-stamp packages and 8-stamp packages.

Case 1 (at least three 5-stamp packages are used in obtaining k stamps):

Replace three 5-stamp packages with two 8-stamp packages. This results in (k + 1) stamps.

Case 2 (at most two 5-stamp packages are used in obtaining k stamps):

If there at most two 5-stamp packages, that means that 28-10=18 must be made up of 8-stamp packages. So at least 3 8-stamp packages must be used to exceed the 28 minimum.

Replace three 8-stamp packages with 5 5-stamp packages. This results in (k + 1) stamps.

Therefore in both cases (k + 1) stamps can be obtained by buying a collection of 5-stamp packages and 8-stamp packages.

Q.E.D.

4. For each positive integer n, let P(n) be the sentence that describes the following divisibility property:

 5^n - 1 \text{ is divisible by } 4 

a. Write P(0). Is P(0) true?

 5^0 - 1 = 1 - 1 = 0 

P(0) is true, as 0 = 0 \cdot 4.

b. Write P(k).

 P(k) = 5^k - 1 \text{ is divisible by } 4 

c. Write P(k + 1).

 P(k + 1) = 5^{k + 1} - 1 \text{ is divisible by } 4 

d. In a proof by mathematical induction that this divisibility property holds for every integer n \geq 0, what must be shown in the inductive step?

It must be shown that supposing that 5^k - 1 is divisible by 4 for some integer k \geq 0, that therefore 5^{k + 1} - 1 is divisible by 4.

5. For each positive integer n, let P(n) be the inequality

 2^n < (n + 1)! 

a. Write P(2). Is P(2) true?

 P(2) = 2^2 < (2 + 1)! 

 P(2) = 4 < (3)! 

 P(2) = 4 < (3 \cdot 2 \cdot 1) 

 P(2) = 4 < 6 

Yes, P(2) is true because 4 is less than 6.

b. Write P(k).

 P(k) = 2^k < (k + 1)! 

c. Write P(k + 1).

 P(k + 1) = 2^{k + 1} < ((k + 1) + 1)! 

Alternatively:

 P(k + 1) = 2^{k + 1} < (k + 2)! 

d. In a proof by mathematical induction that this inequality holds for every integer n \geq 2, what must be shown in the inductive step?

It must be shown that supposing 2^k < (k + 1)! is true for any integer k \geq 2, that therefore 2^{k + 1} < (k + 2)! is true.

6. For each positive integer n, let P(n) be the sentence

Any checkerboard with dimensions 2 \times 3n can be completely covered with L-shaped trominoes.

a. Write P(1). Is P(1) true?

Any checkerboard with dimensions 2 \times 3(1) can be completely covered with L-shaped trominoes.

Yes, this is true, a 2 \times 3 dimension checkerboard can be completely covered with L-shaped trominoes (2 in fact.)

b. Write P(k).

Any checkerboard with dimensions 2 \times 3k can be completely covered with L-shaped trominoes.

c. Write P(k + 1).

Any checkerboard with dimensions 2 \times 3(k + 1) can be completely covered with L-shaped trominoes.

d. In a proof by mathematical induction that P(n) is true for each integer n \geq 1, what must be shown in the inductive step?

It must be shown that supposing any checkerboard with dimensions 2 \times 3k can be completely covered with L-shaped trominoes for any integer k \geq 1, that therefore any checkerboard with dimensions 2 \times 3(k + 1) can be completely covered with L-shaped trominoes.

7. For each positive integer n, let P(n) be the sentence

In any round-robin tournament involving n teams, the teams can be labeled T_1, T_2, T_3, \dots, T_n, so that T_i beats T_{i + 1} for every i = 1, 2, \dots, n.

a. Write P(2). Is P(2) true?

In any round-robin tournament involving 2 teams, the teams can be labeled T_1, T_2, so that T_i beats T_{i + 1} for every i = 1, 2.

This is true, in a round-robin tournament involving only 2 teams, one can label the teams such that T_2 beats T_1.

b. Write P(k).

In any round-robin tournament involving k teams, the teams can be labeled T_1, T_2, T_3, \dots, T_k, so that T_i beats T_{i + 1} for every i = 1, 2, \dots, k.

c. Write P(k + 1).

In any round-robin tournament involving (k + 1) teams, the teams can be labeled T_1, T_2, T_3, \dots, T_{k + 1}, so that T_i beats T_{i + 1} for every i = 1, 2, \dots, (k + 1).

d. In a proof by mathematical induction that P(n) is true for each integer n \geq 2, what must be shown in the inductive step?

It must be shown that supposing in any round-robin tournament involving k teams, the teams can be labeled T_1, T_2, T_3, \dots T_k, so that T_i beats T_{i + 1} for every i = 1, 2, \dots k for any integer k \geq 2, then therefore in any round-robin tournament involving (k + 1) teams, the teams can be labeled T_1, T_2, T_3, \dots T_{k + 1} so that T_i beats T_{i + 1} for every i = 1, 2, \dots (k + 1).

Prove each statement in 8-23 by mathematical induction.

8. 5^n - 1 is divisible by 4, for every integer n \geq 0.

Proof (by mathematical induction):

Let P(n) be the sentence:

 5^n - 1 \text{ is divisible by } 4 

Basis Step:

Prove P(0). That is:

 5^0 - 1 \text{ is divisible by } 4 

 1 - 1 \text{ is divisible by } 4 

 0 \text{ is divisible by } 4 

This sentence is true as 0 = 0 \cdot 4, which shows that 0 is divisible by 4 by the definition of divisibility.

Therefore P(0) is true.

Inductive Step:

Let k be any integer where k \geq 0.

Suppose P(k). That is:

 5^k - 1 \text{ is divisible by } 4 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 5^{k + 1} - 1 \text{ is divisible by } 4 

 5^{k + 1} - 1 

 = 5^k \cdot 5 - 1 

 = 5^k \cdot (4 + 1) - 1 

 = 5^k \cdot 4 + 5^k - 1 

Since we know by the inductive hypothesis that 5^k - 1 is divisible by 4. By the definition of divisibility:

 5^k - 1 = 4r 

for some integer r. Our equation now becomes:

 = 5^k \cdot 4 + 4r 

 = 4(5^k + r) 

Now, we know that 5^k + r is an integer by the sum and product of integers. Therefore, by the definition of divisibility, 5^{k + 1} - 1 is divisible by 4.

Q.E.D.

9. 7^n - 1 is divisible by 6, for every integer n \geq 0.

Proof (by mathematical induction):

Let P(n) be the sentence:

 7^n - 1 \text{ is divisible by } 6 

Basis Step:

Prove P(0). That is:

 7^0 - 1 \text{ is divisible by } 6 

 7^0 - 1 

 = 1 - 1 

 = 0 

0 is divisible by 6 because 0 = 0 \cdot 6.

Therefore P(0) is true.

Inductive Step:

Let k be any integer where k \geq 0.

Suppose P(k). That is:

 7^k - 1 \text{ is divisible by } 6 

Prove P(k + 1). That is:

 7^{k + 1} - 1 \text{ is divisible by } 6 

 7^{k + 1} - 1 

 = 7^k \cdot 7 - 1 

 = 7^k \cdot (6 + 1) - 1 

 = 7^k \cdot 6 + (7^k - 1) 

By the inductive hypothesis and by the definition of divisibility:

 = 7^k \cdot 6 + 6r 

for some integer r.

 = 6(7^k + r) 

Now, we know that 7^k + r is an integer by the sum and product of integers. Therefore, by the definition of divisibility, 7^{k + 1} - 1 is divisible by 6.

Q.E.D.

10. n^3 - 7n + 3 is divisible by 3, for each integer n \geq 0.

Proof (by mathematical induction):

Let P(n) be the sentence:

 n^3 - 7n + 3 \text{ is divisible by } 3 

Basis Step:

Prove P(0). That is:

 (0)^3 - 7(0) + 3 \text{ is divisible by } 3 

 (0)^3 - 7(0) + 3 

 = 0 - 0 + 3 

 = 3 

By the definition of divisibility, 3 \mid 3, as 3 = 1 \cdot 3.

Therefore, P(0) is true.

Inductive Step:

Let k be any integer where k \geq 0.

Suppose P(k). That is:

 k^3 - 7k + 3 \text{ is divisible by } 3 

Prove P(k + 1). That is:

 (k + 1)^3 - 7(k + 1) + 3 \text{ is divisible by } 3 

 (k + 1)^3 - 7(k + 1) + 3 

 = (k + 1)(k + 1)(k + 1) - 7k - 7 + 3 

 = (k^2 + 2k + 1)(k + 1) - 7k - 7 + 3 

 = (k^2(k + 1) + 2k(k + 1) + 1(k + 1)) - 7k - 7 + 3 

 = (k^3 + k^2 + 2k^2 + 2k + k + 1) - 7k - 7 + 3 

 = (k^3 + 3k^2 + 3k + 1) - 7k - 7 + 3 

 = (k^3 - 7k + 3) + 3k^2 + 3k + 1 - 7 

 = (k^3 - 7k + 3) + 3k^2 + 3k - 6 

By the inductive hypothesis and definition of divisibility:

 = (3r) + 3k^2 + 3k - 6 

for some integer r.

 = 3(r + k^2 + k - 2) 

Now, we know that r + k^2 + k - 2 is an integer by the product and sum of integers. Thus, by the definition of divisibility, (k + 1)^3 - 7(k + 1) + 3 is divisible by 3.

Therefore P(k + 1) is true.

Q.E.D.

11. 3^{2n} - 1 is divisible by 8, for every integer n \geq 0.

Proof (by mathematical induction):

Let P(n) be the sentence:

 3^{2n} - 1 \text{ is divisible by } 8 

Basis Step:

Prove P(0). That is:

 3^{2(0)} - 1 \text{ is divisible by } 8 

 3^{2(0)} - 1 

 = 3^0 - 1 

 = 1 - 1 

 = 0 

0 is divisible by 8 as 0 = 0 \cdot 8.

Therefore P(0) is true.

Inductive Step:

Let k be any integer where k \geq 0.

Suppose P(k). That is:

 3^{2k} - 1 \text{ is divisible by } 8 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 3^{2(k + 1)} - 1 \text{ is divisible by } 8 

 3^{2(k + 1)} - 1 

 = 3^{2k + 2} - 1 

 = 3^{2k} \cdot 3^2 - 1 

 = 3^{2k} \cdot 9 - 1 

 = 3^{2k} \cdot (8 + 1) - 1 

 = 3^{2k} \cdot 8 + (3^{2k} - 1) 

By the inductive hypothesis and the definition of divisibility:

 = 3^{2k} \cdot 8 + 8r 

for some integer r.

 = 8(3^{2k} + r) 

Now, 3^{2k} + r is an integer by the sum and product of integers. Thus 3^{2(k + 1)} - 1 is divisible by 8 by the definition of divisibility.

Therefore P(k + 1) is true.

Q.E.D.

12. For any integer n \geq 0, 7^n - 2^n is divisible by 5.

Proof (by mathematical induction):

Let P(n) be the sentence:

 7^n - 2^n \text{ is divisible by } 5 

Basis Step:

Prove P(0). That is:

 7^0 - 2^0 \text{ is divisible by } 5 

 7^0 - 2^0 

 = 1 - 1 

 = 0 

0 is divisible by 5 as 0 = 0 \cdot 5.

Therefore P(0) is true.

Inductive Step:

Let k be any integer where k \geq 0.

Suppose P(k). That is:

 7^k - 2^k \text{ is divisible by } 5 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 7^{k + 1} - 2^{k + 1} \text{ is divisible by } 5 

 7^{k + 1} - 2^{k + 1} 

 = 7^k \cdot 7^1 - 2^k \cdot 2^1 

 = 7^k \cdot (5 + 2) - 2^k \cdot 2^1 

 = 7^k \cdot 5 + (2)7^k - 2^k \cdot 2^1 

 = 7^k \cdot 5 + 2(7^k - 2^k) 

By the inductive hypothesis and the definition of divisibility:

 = 7^k \cdot 5 + 2(5r) 

For some integer r.

 = 5(7^k + 2r) 

Now, 7^k + 2r is an integer by the sum and product of integers. Thus 7^{k + 1} - 2^{k + 1} is divisible by 5 by the definition of divisibility.

Therefore P(k + 1) is true.

Q.E.D.

13. For any integer n \geq 0, x^n -y^n is divisible by x - y, where x and y are any integers with x \neq y.

Proof (by mathematical induction):

Suppose x and y are any integers with x \neq y.

Let P(n) be the sentence:

 x^n - y^n \text{ is divisible by } x - y 

Basis Step:

Prove P(0). That is:

 x^0 - y^0 \text{ is divisible by } x - y 

 x^0 - y^0 

 = 1 - 1 

 = 0 

0 is divisible by (x - y) as 0 = 0 \cdot (x - y).

Therefore P(0) is true.

Inductive Step:

Let k be any integer where k \geq 0.

Suppose P(k). That is:

 x^k - y^k \text{ is divisible by } x - y 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 x^{k + 1} - y^{k + 1} \text{ is divisible by } x - y 

 x^{k + 1} - y^{k + 1} 

 = x^k(x) - y^k(y) 

 = x^k(x) - xy^k + xy^k - y^k(y) 

 = x(x^k - y^k) + y^k(x - y) 

By the inductive hypothesis:

 = x(r(x - y)) + y^k(x - y) 

for some integer r.

 = (x - y)(xr + y^k) 

We know xr + y^k is an integer by the sum and product of integers. By the definition of divisibility, x^{k + 1} - y^{k + 1} is divisible by x - y.

Therefore P(k + 1) is true.

Q.E.D.

14. n^3 - n is divisible by 6, for each integer n \geq 0.

Proof (by mathematical induction):

Let P(n) be the sentence:

 n^3 - n \text{ is divisible by } 6 

Basis Step:

Prove P(0). That is:

 0^3 - 0 \text{ is divisible by } 6 

 0^3 - 0 

 = 0 - 0 

 = 0 

0 is divisible by 6 because 0 = 0 \cdot 6.

Therefore P(0) is true.

Inductive Step:

Let k be any integer where k \geq 0.

Suppose P(k). That is:

 k^3 - k \text{ is divisible by } 6 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 (k + 1)^3 - (k + 1) \text{ is divisible by } 6 

 (k + 1)^3 - (k + 1) 

 = (k + 1)(k + 1)(k + 1) - (k + 1) 

 = (k^2 + 2k + 1)(k + 1) - (k + 1) 

 = (k^3 + k^2 + 2k^2 + 2k + k + 1) - (k + 1) 

 = (k^3 + 3k^2 + 3k + 1) - (k + 1) 

 = k^3 + 3k^2 + 3k + 1 - k - 1 

 = k^3 + 3k^2 + 2k 

 = (k^3 - k) + 3k^2 + 3k 

 = (k^3 - k) + 3k(k + 1) 

By the inductive hypothesis and definition of divisibility:

 = 6r + 3k(k + 1) 

for some integer r.

By Theorem 4.5.2, the product of any two consecutive integers must be even.

 = 6r + 3(2m) 

for some integer m.

 = 6r + 6m 

 = 6(r + m) 

Now, r + m is an integer by the sum of integers.

Therefore (k + 1)^3 - (k + 1) is divisible by 6 by the definition of divisibility.

Therefore P(k + 1) is true.

Q.E.D.

15. n(n^2 + 5) is divisible by 6, for each integer n \geq 0.

Proof (by mathematical induction):

Let P(n) be the sentence:

 n(n^2 + 5) \text{ is divisible by } 6 

Basis Step:

Prove P(0). That is:

 0(0^2 + 5) \text{ is divisible by } 6 

 0(0^2 + 5) 

 = 0(0 + 5) 

 = 0(5) 

 = 0 

0 is divisible by 6 as 0 = 0 \cdot 6.

Therefore P(0) is true.

Inductive Step:

Let k be any integer where k \geq 0.

Suppose P(k). That is:

 k(k^2 + 5) \text{ is divisible by } 6 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 (k + 1)((k + 1)^2 + 5) \text{ is divisible by } 6 

 (k + 1)((k + 1)^2 + 5) 

 = (k + 1)((k + 1)(k + 1) + 5) 

 = (k + 1)(k^2 + 2k + 6) 

 = k^3 + k^2 + 2k^2 + 2k + 6k + 6 

 = k^3 + 3k^2 + 8k + 6 

 = k^3 + 3k^2 + 5k + 3k + 6 

 = (k^3 + 5k) + 3k^2 + 3k + 6 

 = k(k^2 + 5) + 3k^2 + 3k + 6 

 = k(k^2 + 5) + 3(k^2 + k + 2) 

By the inductive hypothesis and definition of divisibility:

 = 6r + 3(k^2 + k + 2) 

for some integer r.

 = 6r + 3(k(k + 1) + 2) 

By Theorem 4.5.2 k(k + 1) is always even:

 = 6r + 3(2m + 2) 

for some integer m.

 = 6r + 6m + 6 

 = 6(r + m + 1) 

Now, r + m + 1 is an integer by the sum of integers. Thus (k + 1)((k + 1)^2 + 5) is divisible by 6 by the definition of divisibility.

Therefore P(k + 1) is true.

Q.E.D.

16. 2^n < (n + 1)!, for every integer n \geq 2.

Proof (by mathematical induction):

Let P(n) be the sentence:

 2^n < (n + 1)! 

Basis Step:

Prove P(2). That is:

 2^(2) < (2 + 1)! 

 4 < (3)! 

 4 < (3 \cdot 2 \cdot 1) 

 4 < 6 

4 is less than 6.

Therefore P(2) is true.

Inductive Step:

Let k be any integer where k \geq 2.

Suppose P(k). That is:

 2^k < (k + 1)! 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 2^{k + 1} < ((k + 1) + 1)! 

Alternatively:

 2^{k + 1} < (k + 2)! 

By the inductive hypothesis and the laws of exponents:

 = 2^{k} \cdot 2 < 2(k + 1)! 

Since k \geq 2, then 2 < k + 2, and so:

 2(k + 1)! < (k + 2)(k + 1)! = (k + 2)! 

Combining these inequalities shows:

 2^{k + 1} < (k + 2)! 

As was to be shown.

Q.E.D.

17. 1 + 3n \leq 4^n, for every integer n \geq 0.

Proof (by mathematical induction):

Let P(n) be the inequality:

 1 + 3n \leq 4^n 

Basis Step:

Prove P(0). That is:

 1 + 3(0) \leq 4^0 

 = 1 + 0 \leq 1 

 = 1 \leq 1 

Since 1 = 1, 1 \leq 1 is a true statement.

Therefore P(0) is true.

Inductive Step:

Let k be any integer where k \geq 0.

Suppose P(k). That is:

 1 + 3k \leq 4^k 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 1 + 3(k + 1) \leq 4^{k + 1} 

 (1 + 3k) + 3 \leq 4^k \cdot 4 

By the inductive hypothesis:

 (1 + 3k) + 3 \leq 4^k + 3 

Now show:

 4^k + 3 \leq 4^{k + 1} 

Since:

 4^{k + 1} = 4^k \cdot 4 

it is enough to show:

 3 \leq 3 \cdot 4^k 

which is true for all k \geq 0.

So:

 1 + 3(k + 1) \leq 4^k + 3 \leq 4^{k + 1} 

 1 + 3(k + 1) \leq 4^{k + 1} 

Q.E.D.

18. 5^n + 9 < 6^n, for each integer n \geq 2.

Proof (by mathematical induction):

Let P(n) be the inequality:

 5^n + 9 < 6^n 

Basis Step:

Prove P(2). That is:

 5^2 + 9 < 6^2 

 25 + 9 < 36 

 34 < 36 

Since 34 is less than 36, this inequality is true.

Therefore P(2) is true.

Inductive Step:

Let k be any integer where k \geq 2.

Suppose P(k). That is:

 5^k + 9 < 6^k 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 5^{k + 1} + 9 < 6^{k + 1} 

If we multiply the inductive hypothesis by 5:

 5(5^k + 9) < 5(6^k) 

 5^{k + 1} + 45 < 5(6^k) 

 5^{k + 1} + 45 < 5(6^k) < 6^{k + 1} 

 5^{k + 1} + 45 < 5(6^k) < 6^k \cdot 6 = 6^{k + 1} 

Note that:

 5^{k + 1} + 9 < 5^{k + 1} + 45 < 5(6^k) < 6^k \cdot 6 = 6^{k + 1} 

Therefore:

 5^{k + 1} + 9 < 6^{k + 1} 

As was to be shown.

Q.E.D.

19. n^2 < 2^n, for every integer n \geq 5.

Proof (by mathematical induction):

Let P(n) be the inequality:

 n^2 < 2^n 

Basis Step:

Prove P(5). That is:

 5^2 < 2^5 

 25 < 32 

Since 25 is less than 32, this is a true statement.

Therefore P(5) is true.

Inductive Step:

Let k be any integer where k \geq 5.

Suppose P(k). That is:

 k^2 < 2^k 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 (k + 1)^2 < 2^{k + 1} 

Now, expanding out the left-hand side:

 (k + 1)^2 = k^2 + 2k + 1 

Consider the inductive hypothesis:

 k^2 < 2^k 

It follows that:

 k^2 + 2k + 1 < 2^k + 2k + 1 

By proposition 5.3.2, 2k + 1 < 2^k since k \geq 5 \geq 3.

Hence:

 (k + 1)^2 = k^2 + 2k + 1 < 2^k + 2k + 1 < 2^k + 2^k = 2^{k + 1} 

 (k + 1)^2 < 2^{k + 1} 

As was to be shown.

Q.E.D.

20. 2^n < (n + 2)!, for each integer n \geq 0.

Proof (by mathematical induction):

Let P(n) be the inequality:

 2^n < (n + 2)! 

Basis Step:

Prove P(0). That is:

 2^0 < (0 + 2)! 

 1 < (2)! 

 1 < 2 

Since 1 is less than 2. This is a true statement.

Therefore P(0) is true.

Inductive Step:

Let k be any integer such that k \geq 0.

Suppose P(k). That is:

 2^k < (k + 2)! 

Prove P(k + 1). That is:

 2^{k + 1} < ((k + 1) + 2)! 

Alternatively:

 2^{k + 1} < (k + 3)! 

Expanding out the left-hand side:

 2^{k + 1} = 2^k \cdot 2 

Consider the inductive hypothesis:

 2^k < (k + 2)! 

Multiple both sides by 2:

 2(2^k) < 2(k + 2)! 

 2^{k + 1} < 2(k + 2)! 

Now, expanding out the right-hand side:

 (k + 3)! = (k + 3)(k + 2)! 

Since k \geq 0, it follows that k + 3 \geq 3 \geq 2. Putting out inequalities together then, we get:

 2^{k + 1} < 2(k + 2)! < (k + 3)(k + 2)! = (k + 3)! 

And now simplified:

 2^{k + 1} < (k + 3)! 

As was to be shown.

Q.E.D.

21. \sqrt{n} < \dfrac{1}{\sqrt{1}} + \dfrac{1}{\sqrt{2}} + \dots + \dfrac{1}{\sqrt{n}}, for every integer n \geq 2.

Proof (by mathematical induction):

Let P(n) be the inequality:

 \sqrt{n} < \dfrac{1}{\sqrt{1}} + \dfrac{1}{\sqrt{2}} + \dots + \dfrac{1}{\sqrt{n}} 

Basis Step:

Prove P(2). That is:

 \sqrt{2} < \dfrac{1}{\sqrt{1}} + \dfrac{1}{\sqrt{2}} + \dots + \dfrac{1}{\sqrt{2}} 

\dots \dfrac{1}{\sqrt{2}} just ends at term, \dfrac{1}{\sqrt{2}}.

 \sqrt{2} < \dfrac{1}{\sqrt{1}} + \dfrac{1}{\sqrt{2}} 

 \sqrt{2} < 1 + \dfrac{1}{\sqrt{2}} 

 \sqrt{2} < \frac{\sqrt{2}}{\sqrt{2}} + \dfrac{1}{\sqrt{2}} 

 \sqrt{2} < \dfrac{\sqrt{2} + 1}{\sqrt{2}} 

 (\sqrt{2})(\sqrt{2}) < \left(\dfrac{\sqrt{2} + 1}{\sqrt{2}}\right)(\sqrt{2}) 

 2 < \sqrt{2} + 1 \approx 2.414213562 

This statement is true. Therefore P(2) is true.

Inductive Step:

Let k be any integer where k \geq 2.

Suppose P(k). That is:

 \sqrt{k} < \dfrac{1}{\sqrt{1}} + \dfrac{1}{\sqrt{2}} + \dots + \dfrac{1}{\sqrt{k}} 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 \sqrt{k + 1} < \dfrac{1}{\sqrt{1}} + \dfrac{1}{\sqrt{2}} + \dots + \dfrac{1}{\sqrt{k + 1}} 

From the inductive hypothesis:

 \sqrt{k} < \dfrac{1}{\sqrt{1}} + \dfrac{1}{\sqrt{2}} + \dots + \dfrac{1}{\sqrt{k}} 

Add \dfrac{1}{\sqrt{k + 1}} to both sides:

 \sqrt{k} + \frac{1}{\sqrt{k + 1}} < \dfrac{1}{\sqrt{1}} + \dfrac{1}{\sqrt{2}} + \dots + \dfrac{1}{\sqrt{k}} + \frac{1}{\sqrt{k + 1}} 

From here, it is enough to show:

 \sqrt{k + 1} \leq \sqrt{k} + \frac{1}{\sqrt{k + 1}} 

 \sqrt{k + 1} - \sqrt{k} \leq \frac{1}{\sqrt{k + 1}} 

 \left(\sqrt{k + 1} - \sqrt{k}\right)\left(\frac{\sqrt{k + 1} + \sqrt{k}}{\sqrt{k + 1} + \sqrt{k}}\right) \leq \frac{1}{\sqrt{k + 1}} 

 \frac{(k + 1) - k}{\sqrt{k + 1} + \sqrt{k}} \leq \frac{1}{\sqrt{k + 1}} 

 \frac{1}{\sqrt{k + 1} + \sqrt{k}} \leq \frac{1}{\sqrt{k + 1}} 

Since \sqrt{k + 1} + \sqrt{k} > \sqrt{k + 1}, this inequality holds.

Simplified, our inequality becomes:

 \sqrt{k + 1} < \sqrt{k} + \frac{1}{\sqrt{k + 1}} < \dfrac{1}{\sqrt{1}} + \dfrac{1}{\sqrt{2}} + \dots + \dfrac{1}{\sqrt{k + 1}} 

 \sqrt{k + 1} < \dfrac{1}{\sqrt{1}} + \dfrac{1}{\sqrt{2}} + \dots + \dfrac{1}{\sqrt{k + 1}} 

As was to be shown.

Q.E.D.

22. 1 + nx \leq (1 + x)^n, for every real number x > -1 and every integer n \geq 2.

Proof (by mathematical induction):

Suppose x is any real number where x > -1.

Let P(n) be the sentence:

 1 + nx \leq (1 + x)^n 

Basis Step:

Prove P(2). That is:

 1 + 2x \leq (1 + x)^2 

 1 + 2x \leq 1 + 2x + x^2 

 0 \leq x^2 

This inequality always holds.

Therefore P(2) is true.

Inductive Step:

Let k be any integer where k \geq 2.

Suppose P(k). That is:

 1 + kx \leq (1 + x)^k 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 1 + (k + 1)x \leq (1 + x)^{k + 1} 

Consider the inductive hypothesis:

 1 + kx \leq (1 + x)^k 

Multiply each side by (1 + x):

 (1 + x)(1 + kx) \leq ((1 + x)^k)(1 + x) 

 1 + x + kx + kx^2 \leq (1 + x)^{k + 1} 

Now it is enough to show that the left hand side of P(k + 1) is less than or equal to the left-hand side of (1 + x)(P(k)):

 1 + (k + 1)x \leq 1 + x + kx + kx^2 

 1 + kx + x  \leq 1 + x + kx + kx^2 

 1 + x + kx  \leq 1 + x + kx + kx^2 

 0 \leq kx^2 

Since k \geq 2, this inequality will always hold.

Simplified, our inequality is:

 1 + (k + 1)x \leq 1 + x + kx + kx^2 \leq (1 + x)^{k + 1} 

 1 + (k + 1)x \leq (1 + x)^{k + 1} 

As was to be shown.

Q.E.D.

a. n^3 > 2n + 1, for each integer n \geq 2.

Proof (by mathematical induction):

Let P(n) be the inequality:

 n^3 > 2n + 1 

Basis Step:

Prove P(2). That is:

 (2)^3 > 2(2) + 1 

 8 > 4 + 1 

 8 > 5 

Since 8 is greater than 5, this statement is true.

Therefore P(2) is true.

Inductive Step:

Let k be any integer where k \geq 2.

Suppose P(k). That is:

 k^3 > 2k + 1 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 (k + 1)^3 > 2(k + 1) + 1 

Alternatively:

 (k + 1)^3 > 2k + 2 + 1 

 (k + 1)^3 > 2k + 3 

Consider the inductive hypothesis:

 k^3 > 2k + 1 

Add 2 to both sides:

 k^3 + 2 > 2k + 1 + 2 

 k^3 + 2 > 2k + 3 

Now it is enough to prove that the left-hand side of this inequality is less than the left-hand side of the P(k + 1) inequality:

 (k + 1)^3 > k^3 + 2 

 (k + 1)(k + 1)(k + 1) > k^3 + 2 

 (k^2 + 2k + 1)(k + 1) > k^3 + 2 

 k^3 + k^2 + 2k^2 + 2k + k + 1 > k^3 + 2 

 k^3 + 3k^2 + 3k + 1 > k^3 + 2 

 3k^2 + 3k > 1 

Since k \geq 2, this inequality will always hold.

Simplified:

 (k + 1)^3 > k^3 + 2 > 2k + 3 

 (k + 1)^3 > 2k + 3 

As was to be shown.

Q.E.D.

b. n! > n^2, for each integer n \geq 4.

Proof (by mathematical induction):

Let P(n) be the inequality:

 n! > n^2 

Basis Step:

Prove P(4). That is:

 4! > 4^2 

 (4 \cdot 3 \cdot 2 \cdot 1) > 16 

 24 > 16 

Since 24 is greater than 16, this statement is true.

Therefore P(4) is true.

Inductive Step:

Let k be any integer where k \geq 4.

Suppose P(k). That is:

 k! > k^2 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 (k + 1)! > (k + 1)^2 

Take the inductive hypothesis:

 k! > k^2 

And multiply each side by (k + 1):

 (k + 1)k! > k^2(k + 1) 

 (k + 1)! > k^2(k + 1) 

Now it is enough to show:

 k^2(k + 1) > (k + 1)^2 

 k^2 > k + 1 

And this inequality holds for all k \geq 4.

Simplified:

 (k + 1)! > k^2(k + 1) > (k + 1)^2 

 (k + 1)! > (k + 1)^2 

As was to be shown.

Q.E.D.

24. A sequence a_1, a_2, a_3, \dots is defined by letting a_1 = 3 and a_k = 7a_{k - 1} for each integer k \geq 2. Show that a_n = 3 \cdot 7^{n - 1} for every integer n \geq 1.

Proof (by mathematical induction):

Let P(n) be the statement:

 a_n = 3 \cdot 7^{n - 1} 

Basis Step:

Prove P(1). That is:

 a_1 = 3 \cdot 7^{1 - 1} 

 = 3 \cdot 7^{0} 

 = 3 \cdot 1 

 = 3 

Since a_1 = 3 is defined in the problem statement, this equality is true.

Therefore P(1) is true.

_Inductive Step:

Let k be any integer such that k \geq 1.

Suppose P(k). That is:

 a_k = 3 \cdot 7^{k - 1} 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 a_{k + 1} = 3 \cdot 7^{(k + 1) - 1} 

Alternatively:

 a_{k + 1} = 3 \cdot 7^k 

By the definition of the given sequence:

 a_{k + 1} = 7a_k 

By the inductive hypothesis:

 = 7(3 \cdot 7^{k - 1}) 

By the laws of exponents:

 = 3 \cdot 7^k 

And this is the right-hand side of the equality to be shown.

Q.E.D.

25. A sequence b_0, b_1, b_2, \dots is defined by letting b_0 = 5 and b_k = 4 + b_{k - 1} for each integer k \geq 1. Show that b_n > 4n for every integer n \geq 0.

Proof (by mathematical induction):

Let P(n) be the inequality:

 b_n > 4n 

Basis Step:

Prove P(0). That is:

 b_0 > 4(0) 

 5 > 4(0) 

 5 > 0 

This inequality holds. Therefore P(0) is true.

Inductive Step:

Let k be any integer where k \geq 0.

Suppose P(k). That is:

 b_k > 4k 

This is the inductive hypothesis.

Prove P(k + 1). That is:

 b_{k + 1} > 4(k + 1) 

By the definition of the sequence:

 b_{k + 1} = 4 + b_k 

By the inductive hypothesis:

 > 4 + 4k 

 > 4(1 + k) 

 > 4(k + 1) 

Q.E.D.

26. A sequence c_0, c_1, c_2, \dots is defined by letting c_0 = 3 and c_k = (c_{k - 1})^2 for every integer k \geq 1. Show that c_n = 3^{2n} for each integer n \geq 0.

Proof (by mathematical induction):

Let P(n) be the equality:

 c_n = 3^{2n} 

Basis Step:

Prove P(0). That is:

 c_0 = 3^{2(0)} 

 c_0 = 3^{0} 

 c_0 = 1 

Stopping here. It is likely Epp has a typo, she means c_n = 3^{2^n}, not c_n = 3^{2n}.

27. A sequence d_1, d_2, d_3, \dots is defined by letting d_1 = 2 and d_k = \dfrac{d_{k - 1}}{k} for each integer k \geq 2. Show that for every integer n \geq 1, d_n = \dfrac{2}{n!}.

Proof (by mathematical induction):

Let P(n) be the equation:

 d_n = \frac{2}{n!} 

Basis Step:

Prove P(1). That is:

 d_1 = \frac{2}{1!} 

 d_1 = \frac{2}{1} 

 d_1 = 2 

Since the problem statement states that d_1 = 2, this matches our equality.

Therefore P(1) is true.

Inductive Step:

Let k be any integer such that k \geq 1.

Suppose P(k), that is:

 d_k = \frac{2}{k!} 

This is the inductive hypothesis.

Prove P(k + 1), that is:

 d_{k + 1} = \frac{2}{(k + 1)!} 

By the given sequence:

 d_{k + 1} = \frac{d_k}{k + 1} 

By the inductive hypothesis:

 = \frac{2}{(k + 1)k!} 

 = \frac{2}{(k + 1)!} 

Q.E.D.

28. Prove that for every integer n \geq 1,

 \frac{1}{3} = \frac{1 + 3 + 5 + \dots + (2n - 1)}{(2n + 1) + (2n + 3) + \dots + (2n + (2n - 1))} 

Proof (by mathematical induction):

Let P(n) be the equality:

 \frac{1}{3} = \frac{1 + 3 + 5 + \dots + (2n - 1)}{(2n + 1) + (2n + 3) + \dots + (2n + (2n - 1))} 

Basis Step:

Prove P(1), that is:

 \frac{1}{3} = \frac{1 + 3 + 5 + \dots + (2(1) - 1)}{(2(1) + 1) + (2(1) + 3) + \dots + (2(1) + (2(1) - 1))} 

 \frac{1}{3} = \frac{1 + 3 + 5 + \dots + (2 - 1)}{(2 + 1) + (2 + 3) + \dots + (2 + (2 - 1))} 

 \frac{1}{3} = \frac{1 + 3 + 5 + \dots + 1}{(2 + 1) + (2 + 3) + \dots + (2 + 1)} 

 \frac{1}{3} = \frac{1}{(2 + 1) + (2 + 3) + \dots + 3} 

 \frac{1}{3} = \frac{1}{3} 

Therefore P(1) is true.

Inductive Step:

Let k be any integer where k \geq 1.

Suppose P(k), that is:

 \frac{1}{3} = \frac{1 + 3 + 5 + \dots + (2k - 1)}{(2k + 1) + (2k + 3) + \dots + (2k + (2k - 1))} 

This is the inductive hypothesis.

Prove P(k + 1), that is:

 \frac{1}{3} = \frac{1 + 3 + 5 + \dots + (2(k + 1) - 1)}{(2(k + 1) + 1) + (2(k + 1) + 3) + \dots + (2(k + 1) + (2(k + 1) - 1))} 

Starting from the inductive hypothesis:

 \frac{1}{3} = \frac{1 + 3 + 5 + \dots + (2k - 1)}{(2k + 1) + (2k + 3) + \dots + (2k + (2k - 1))} 

Omitted.

Exercises 29 and 30 use the definition of string and string length from page 13 in Section 1.4. Recursive definitions for these terms are given in section 5.9.

29. A set L consists of strings obtained by juxtaposing one or more of abb, bab, and bba. Use mathematical induction to prove that for every integer n \geq 1, if a string s in L has a length 3n, then s contains an even number of b's.

Proof (by mathematical induction):

Suppose a set L consists of strings by juxtaposing one or more of abb, bab, and bba.

Let P(n) be the sentence:

If a string s in L has length 3n, then s contains an even number of b's.

Basis Step:

Prove P(1), that is:

If a string s in L has length 3(1), then s contains an even number of b's.

Since:

 L = \{\text{abb}, \text{bab}, \text{bba}\} 

All three string s in L have a length of 3 and all of them have an even number of b's.

Therefore P(1) is true.

Inductive Step:

Let k be any integer where k \geq 1.

Suppose P(k), that is:

If a string s in L has length 3k, then s contains an even number of b's.

This is the inductive hypothesis.

Prove P(k + 1), that is:

If a string s in L has length 3(k + 1), then s contains an even number of b's.

Now 3(k + 1) = 3k + 3 and the strings in L are obtained by juxtaposing strings already in L with one of abb, bab, or bba. Thus, either the initial or the final three characters in s are abb, bab, or bba. Moreoever, the other 3k characters in s are also in L by definition of L, and so, by the inductive hypothesis, the other 3k characters in s contain an even number, say m, of b's. Because each of abb, bab, and bba contains 2 b's, the total number of b's in s is m + 2, which is a sum of even integers and hence is even.

Q.E.D.

30. A set S consists of strings obtained by juxtaposing one or more copies of 1110 and 0111. Use mathematical induction to prove that for every integer n \geq 1, if a string s in S has a length 4n, then the number of 1's in s is a multiple of 3.

Proof (by mathematical induction):

Suppose a set S contains strings obtained by juxtaposing one or more copies of 1110 and 0111.

Let P(n) be the sentence:

If a string s in S has length 4n, then the number of $1$'s in s is a multiple of 3.

Basis Step:

Prove P(1), that is:

If a string s in S has length 4(1), then the number of $1$'s in s is a multiple of 3.

Since S consists only of strings obtained by juxtaposing 1110 and 0111, then at a minimum, the strings in S must have a length of 4. This means that the only two strings in S that have a length of 4 are 1110 and 0111. The number of $1$'s in s is a multiple of 3 in both cases.

Therefore P(1) is true.

Inductive Step:

Let k be any integer where k \geq 1.

Suppose P(k), that is:

If a string s in S has length 4k, then the number of $1$'s in s is a multiple of 3.

This is the inductive hypothesis.

Prove P(k + 1), that is:

If a string s in S has length 4(k + 1), then the number of $1$'s in s is a multiple of 3.

Now 4(k + 1) = 4k + 4 and the strings in S are obtained by juxtaposing strings already in S with one of 1110 or 0111. Thus, the number of $1$'s is a multiple of 3 in both cases. Moreover, the other 4k digits in s are also in S by the definition of S, and so, by inductive hypothesis, the other 4k characters in s contain an odd number, say m of $1$'s. Because each of 1110 and 0111 contain 3 $1$'s, the total number of $1$'s in s is m + 1, which is the sum of odd integers and hence is odd.

Q.E.D.

31. Use mathematical induction to give an alternative proof for the statement proved in Example 4.9.9:

For any positive integer n, a complete graph on n vertices has \dfrac{n(n - 1)}{2} edges. Hint: Let P(n) be the sentence, "the number of edges in a complete graph on n vertices is \dfrac{n(n - 1)}{2}."

Omitted.

32. Some 5 \times 5 checkerboards with one square removed can be completely covered by L-shaped trominoes, whereas other 5 \times 5 checkerboards cannot. Find examples of both kinds of checkerboards. Justify your answers.

Omitted.

33. Consider a 4 \times 6 checkerboard. Draw a covering of the board by L-shaped trominoes.

Omitted.

a. Use mathematical induction to prove that for each integer n \geq 1, any checkerboard with dimensions 2 \times 3n can be completely covered with L-shaped trominoes.

Omitted.

b. Let n be any integer greater than or equal to 1. Use the result of part (a) to prove by mathematical induction that for every integer m, any checkerboard with dimensions 2m \times 3n can be completely covered with L-shaped trominoes.

Omitted.

35. Let m and n be any integers that are greater than or equal to 1.

a. Prove that a necessary condition for an m \times n checkerboard to be completely coverable by L-shaped trominoes is that mn be divisible by 3.

Omitted.

b. Prove that having be divisible by 3 is not a sufficient condition for an m \times n checkerboard to be completely covered by L-shaped trominoes.

Omitted.

36. In a round-robin tournament each team plays every other team exactly once with ties not allowed. If the teams are labeled T_1, T_2, \dots, T_n, then the outcome of such a tournament can be represented by a directed graph, in which the teams are represented as dots and an arrow is drawn from one dot to another if, and only if, the following team represented by the first dot beats the team represented by the second dot. For example, the following directed graph shows one outcome of a round-robin tournament involving five teams, A, B, C, D, and E.

See Page 322 for image.

Use mathematical induction to show that in any round-robin tournament involving n teams, where n \geq 2, it is possible to label the teams T_1, T_2, \dots, T_n so that T_i beats T_{i + 1} for all i = 1, 2, \dots n - 1,. (For instance, one such labeling in the example above is T_1 = 1, T_2 = B, T_3 = C, T_4 = E, T_5 = D.) (Hint: Given k + 1 teams, pick one - say T' - and apply the inductive hypothesis to the remaining teams to obtain an ordering T_1, T_2, \dots, T_k. Consider three cases: T' beats T_1, T' loses to the first m teams (where 1 \leq m \leq k - 1) and beats the $(m + 1)$st team, and T' loses to all the other teams.)

Omitted.

37. On the outside rim of a circular disk the integers from 1 through 30 are painted in random order. Show that no matter what this order is, there must be three successive integers whose sum is at least 45.

Omitted.

38. Suppose that n a's and n b's are distributed around the outside of a circle. Use mathematical induction to prove that for any integer n \geq 1, given any such arrangement, it is possible to find a starting point so that if you travel around the circle in a clock-wise direction, the number of a's you pass is never less than the number of b's you have passed. For example, in the diagram shown below, you could start at the a with an asterisk.

See Page 322 for image.

Omitted.

39. For a polygon to be convex means that given any two points on or inside the polygon, the line joining the points lies entirely inside the polygon. Use mathematical induction to prove that for every integer n \geq 3, the angles of any $n$-sided convex polygon add up to 180(n - 2) degrees.

Omitted.

a. Prove that in an 8 \times 8 checkerboard with alternating black and white squares, if the squares in the top right and bottom left corners are removed the remaining board cannot be covered with dominoes. (Hint: Mathematical induction is not needed for this proof.)

Omitted.

b. Use mathematical induction to prove that for each positive integer n, if a 2n \times 2n checkerboard with alternating black and white squares has one white square and one black square removed anywhere on the board, the remaining squares can be covered with dominoes.

Omitted.

41. A group of people are positioned so that the distance between any two people is different from the distance between any other two people. Suppose that the group contains an odd number of people and each person sends a message to their nearest neighbor. Use mathematical induction to prove that at least one person does not receive a message from anyone. [This exercise is inspired by the article "Odd Pie Fights" by L. Carmony, The Mathematics Teacher, 72(1), 1979, 61-64.]

Omitted.

42. Show that for any integer n, it is possible to find a group of n people who are all positioned so that the distance between any two people is different from the distance between any other two people, so that each person sends a message to their nearest neighbor, and so that every person in the group receives a message from another person in the group.

Omitted.

43. Define a game as follows: You begin with an urn that contains a mixture of white and black balls, and during the game you have access to as many additional white and black balls as you might need. In each move you remove two balls from the urn without looking at their colors. If the balls are the same color, you put in one black ball. If the balls are different colors, you put the white ball back into the urn and keep the black ball out. Because each move reduces the number of balls in the urn by one, the game will end with a single ball in the urn. If you know how many white balls and how many black balls are initially in the urn, can you predict the color of the ball at the end of the game? [This exercise is based on one described in "Why correctness must be a mathematical concern" by E.W. Djikstra, www.cs.utexas.edu/users/EWD/transcriptions/EWD07xx/EWD720.html.]

a. Map out all possibilities for playing the game starting with two balls in the urn, then three balls, and then four balls. For each case keep track of the number of white and black balls you start with and the color of the ball at the end of the game.

Omitted.

b. Does the number of white balls seem to be predictive? Does the number of black balls seem to be predictive? Make a conjecture about the color of the ball at the end of the game given the numbers of white and black balls at the beginning.

Omitted.

c. Use mathematical induction to prove the conjecture you made in part (b).

Omitted.

44. Let P(n) be the following sentence: Given any graph G with n vertices satisfying the condition that every vertex of G has degree at most M, then the vertices of G can be colored with at most M + 1 colors in such a way that no two adjacent vertices have the same color. Use mathematical induction to prove this statement is true for every integer n \geq 1.

In order for a proof by mathematical induction to be valid, the basis statement must be true for n = a and the argument of the inductive step must be correct for every integer k \geq a. IN 45 and 46 find the mistakes in the "proofs" by mathematical induction.

Omitted.

"Theorem:" For any integer n \geq 1, all the numbers in a set of n numbers are equal to each other.

"Proof (by mathematical induction): It is obviously true that all the numbers in a set consisting of just one number are equal to each other, so the basis step is true. For the inductive step, let A = \{a_1, a_2, \dots, a_k, a_{k + 1}\} be any set of k + 1 numbers. Form two subsets each of size k:

 B = \{a_1, a_2, a_3, \dots, a_k\} \text{ and } 

 C = \{a_1, a_3, a_4, \dots, a_{k + 1}} 

(B consists of all the numbers in A except a_{k + 1}, and C consists of all the numbers in A except a_2.) By inductive hypothesis, all the numbers in B equal a_1 and all the numbers in C equal a_1 (since both sets have only k numbers). But every number in A is in B or C, so all the numbers in A equal a_1; hence all are equal to each other."

Omitted.

"Theorem:" For every integer n \geq 1, 3^n - 2 is even.

"Proof (by mathematical induction): Suppose the theorem is true for an integer k, where k \geq 1. That is, suppose that 3^k - 2 is even. We must show that 3^{k + 1} - 2 is even. Observe that

 3^{k + 1} - 2 = 3^k \cdot 3 - 2 = 3^k(1 + 2) - 2 

 = (3^k - 2) + 3^k \cdot 2 

Now 3^k - 2 is even by inductive hypothesis and 3^k \cdot 2 is even by inspection. Hence the sum of the two quantities is even (by Theorem 4.1.1). It follows that 3^{k + 1} - 2 is even, which is what we needed to show."

Omitted.

---

Exercise Set 5.4

Page 333

1. Suppose a_1, a_2, a_3, \dots is a sequence defined as follows:

 a_1 = 1, a_2 = 3, a_k = a_{k - 2} + 2a_{k - 1} 

for each integer k \geq 3.

Prove that a_n is odd for every integer n \geq 1.

2. Suppose b_1, b_2, b_3, \dots is a sequence defined as follows:

 b_1 = 4, b_2 = 12, b_k = b_{k - 2} + b_{k - 1} 

for each integer k \geq 3.

Prove that b_n is divisible by 4 for every integer n \geq 1.

3. Suppose that c_0, c_1, c_2, \dots is a sequence defined as follows:

 c_0 = 2, c_1 = 2, c_2 = 6, c_k = 3c_{k - 3} 

for every integer k \geq 3.

Prove that c_n is even for each integer n \geq 0.

4. Suppose that d_1, d_2, d_3, \dots is sequence defined as follows:

 d_1 = \frac{9}{10}, d_2 = \frac{10}{11}, d_k = d_{k - 1} \cdot d_{k - 2} 

for every integer k \geq 3.

Prove that 0 < d_n \leq 1 for each integer n \geq 1.

5. Suppose that e_0, e_1, e_2, \dots is a sequence defined as follows:

 e_0 = 12, e_1 = 29, e_k, = 5e_{k - 1} - 6e_{k - 2} 

for each integer k \geq 2.

Prove that e_n = 5 \cdot 3^n + 7 \cdot 2^n for every integer n \geq 0.

6. Suppose that f_0, f_1, f_2, \dots is a sequence defined as follows:

 f_0 = 5, f_1 = 16, f_k = 7f_{k - 1} - 10f_{k - 2} 

for every integer k \geq 2.

Prove that f_n = 3 \cdot 2^n + 2 \cdot 5^n for each integer n \geq 0.

7. Suppose that g_1, g_2, g_3, \dots is a sequence defined as follows:

 g_1 = 3, g_2 = 5, g_k = 3g_{k - 1} - 2g_{k - 2} 

for each integer k \geq 3.

Prove that g_n = 2^n + 1 for every integer n \geq 1.

8. Suppose that h_0, h_1, h_2, \dots is a sequence defined as follows:

 h_0 = 1, h_1 = 2, h_2 = 3, h_k = h_{k - 1} + h_{k - 2} + h_{k - 3} 

for each integer k \geq 3.

a. Prove that h_n \leq 3^n for every integer n \geq 0.

b. Suppose that s is any real number such that s^3 \geq s^2 + s + 1. (This implies that 2 > s > 1.83.) Prove that h_n \leq s^n for every integer n \geq 2.

9. Define a sequence a_1, a_2, a_3, \dots as follows: a_1 = 1, a_2 = 3, and a_k = a_{k - 1} + a_{k - 2} for every integer k \geq 3. (This sequence is known as the Lucas sequence.) Use strong mathematical induction to prove that a_n \leq \left(\dfrac{7}{4}\right)^n for every integer n \geq 1.

10. The introductory example solved with ordinary mathematical induction in Section 5.3 can also be solved using strong mathematical induction. Let P(n) be "any $n$¢ can be obtained using a combination of $3$¢ and $5$¢ coins." Use strong mathematical induction to prove that P(n) is true for every integer n \geq 8.

11. You begin solving a jigsaw puzzle by finding two pieces that match and fitting them together. Every subsequent step of the solution consists of fitting together two blocks, each of which is made up of one or more pieces that have previously been assembled. Use strong mathematical induction to prove that for every integer n \geq 1, the number of steps required to put together all n pieces of a jigsaw puzzle is n - 1.

12. The sides of a circular track contain a sequence of n cans of gasoline. For each integer n \geq 1, the total amount in the cans is sufficient to enable a certain car to make one complete circuit of the track. In addition, all the gasoline could fit into the car's gas tank at one time. Use mathematical induction to prove that it is possible to find an initial location for placing the car so that it will be able to traverse the entire track by using the various amounts of gasoline in the cans that it encounters along the way.

13. Use strong mathematical induction to prove the existence part of the unique factorization of integers theorem (Theorem 4.4.5). In other words, prove that every integer greater than 1 is either a prime number of a product of prime numbers.

14. Any product of two or more integers is a result of successive multiplications of two integers at a time. For instance, here are a few of the ways in which a_1a_2a_3a_4 might be computed: (a_1a_2)(a_3a_4) or (((a_1a_2)a_3)a_4) or a_1((a_2a_3)a_4). Use strong mathematical induction to prove that any product of two or more odd integers is odd.

15. Define the "sum" of one integer to be that integer, and use strong mathematical induction to prove that for every integer n \geq 1, any sum of n even integers is even.

16. Use strong mathematical induction to prove that for every integer n \geq 2, if n is even, then any sum of n odd integers is even, and if n is odd, then any sum of n odd integers is odd.

17. Compute 4^1, 4^2, 4^3, 4^4, 4^5, 4^6, 4^7, and 4^8. Make a conjecture about the units digit of 4^n where n is a positive integer. Use strong mathematical induction to prove your conjecture.

18. Compute 9^0, 9^1, 9^2, 9^3, 9^4, and 9^5. Make a conjecture about the units digit of 9^n where n is a positive integer. Use strong mathematical induction to prove your conjecture.

19. Suppose that a_1, a_2, a_3, \dots is a sequence defined as follows:

a_1 = 1 a_k = 2 \cdot a_{\frac{k}{2}}

for every integer k \geq 2.

Prove that a_n \leq n for each integer n \geq 1.

20. Suppose that b_1, b_2, b_3, \dots is a sequence defined as follows:

b_1 = 0, b_2 = 3, b_k = 5 \cdot b_{\frac{k}{2}} + 6

for every integer k \geq 3.

Prove that b_n is divisible by 3 for each integer n \geq 1.

21. Suppose that c_1, c_2, c_3, \dots is a sequence defined as follows:

 c_0 = 1, c_1 = 1, c_k = c_{\frac{k}{2}} + c_{\frac{k}{2}} 

for every integer k \geq 2.

Prove that c_n = n for each integer n \geq 1.

22. One version of the game NIM starts with two piles of objects such as coins, stones, or matchsticks. In each turn a player is required to remove from one to three objects from one of the piles. The two players take turns doing this until both piles are empty. The loser is the first player who can't make a move. Use strong mathematical induction to show that if both piles contain the same number of objects at the start of the game, the player who goes second can always win.

23. Define a game G as follows: Begin with a pile of n stones and 0 points. In the first move split the pile into two possibly unequal sub-piles, multiply the number of stones in one sub-pile times the number of stones in the other sub-pile, and add the product to your score. In the second move, split each of the newly created piles into a pair of possibly unequal sub-piles, multiply the number of stones in each sub-pile times the number of stones in the paired sub-pile, and add the new products to your score. Continue by successively splitting each newly created pile of stones that has at least two stones into a pair of sub-piles, multiplying the number of stones in each sub-pile times the number of stones in the paired sub-pile, and adding the new products to your score. The game G ends when no pile contains more than one stone.

a. Play G starting with 10 stones and using the following initial moves. In move 1 split the pile of 10 stones into two sub-piles with 3 and 7 stones respectively, compute 3 \cdot 7 = 21, and find that your score is 21. In move 2 split the pile of 3 stones into two sub-piles, with 1 and 2 stones respectively, and split the pile of 7 stones into two sub-piles, with 4 and 3 stones respectively, compute 1 \cdot 2 = 2 and 4 \cdot 3 = 12, and find that your score is 21 + 2 + 12 = 35. In move 3 split the pile of 4 stones into two sub-piles, each with 2 stones, and split the pile of 3 tones into two sub-piles, with 1 and 2 stones respectively, and find your new score. Continue splitting piles and computing your score until no pile has more than one stone. Show your final score along with a record of the numbers of stones in the piles you created with your moves.

b. Play G again starting with 10 stones, but use a different initial move from the one in part (a). Show your final score along with a record of the numbers of stones in the piles you created with your moves.

c. Show that you can use strong mathematical induction to prove that for every integer n \geq 1, given the set-up of game G, no matter how you split the piles in the various moves, your final score is \dfrac{n(n - 1)}{2}. The basis step may look a little strange because a pile consisting of one stone cannot be split into any sub-piles. Another way to say this is that it can only be split into zero piles, and that gives an answer that agrees with the general formula for the final score.

24. Imagine a situation in which eight people, numbered consecutively 1-8, are arranged in a circle. Starting from person #1, every second person in the circle is eliminated. The elimination process continues until only one person remains. In the first round the people numbered 2, 4, 6, and 8 are eliminated, in the second round the people numbered 3 and 7 are eliminated, and in the third round person #5 is eliminated, so after the third round only person #1 remains, as shown on the next page.

See page 336 for image.

a. Given a set of sixteen people arranged in a circle and numbered, consecutively 1-16, list the numbers of the people who are eliminated in each round if every second person is eliminated and the elimination process continues until only one person remains. Assume that the starting point is person #1.

b. Use ordinary mathematical induction to prove that for every integer n \geq 1, given any set of 2^n people arranged in a circle and numbered consecutively 1 through 2^n, if one starts from person #1 and goes repeatedly around the circle successively eliminating every second person, eventually only person #1 will remain.

c. Use the result of part (b) to prove that for any nonnegative integers n and m with 2^n \leq 2^n + m < 2^{n + 1}, if r = 2^n + m, then given any set of r people arranged in a circle and numbered consecutively 1 through r, if one starts from person #1 and goes repeatedly around the circle successively eliminating every second person, eventually only person #(2m + 1) will remain.

25. Find the mistake in the following "proof" that purports to show that every nonnegative integer power of every nonzero real number is 1.

"Proof:

Let r be any nonzero real number and let the property P(n) be the equation r^n = 1.

Show that P(0) is true:

P(0) is true because r^0 = 1 by definition of zeroth power.

Show that for every integer k \geq 0, if P(i) is true for each integer i from 0 through k, then P(k + 1) is also true:

Let k be any integer k \geq 0 and suppose that r^i = 1 for each integer i from 0 through k. This is the inductive hypothesis.

We must show that r^{k + 1} = 1. Now

 r^{k + 1} = r^{k + k - (k - 1)} 

because k + k - (k - 1) = k + k - k + 1 = k + 1

 = \frac{r^k \cdot r^k}{r^{k - 1}} 

by the laws of exponents

 = \frac{1 \cdot 1}{1} 

by inductive hypothesis

 = 1 

Thus r^{k + 1} = 1 [as was to be shown].

[Since we have proved both the basis and the inductive step of the strong mathematical induction, we conclude that the given statement is true.]"

26. Use the well-ordering principle for the integers to prove Theorem 4.4.4: Every integer greater than 1 is divisible by a prime number.

27. Use the well-ordering principle for the integers to prove the existence part of the unique factorization of integers theorem. In other words, prove that every integer greater than 1 is either prime or a product of prime numbers.

a. The Archimedean property for the rational numbers states that for every rational number r, there is an integer n such that n > r. Prove this property.

b. Prove that given any rational number r, the number -r is also rational.

c. Use the results of parts (a) and (b) to prove that given any rational number r, there is an integer m such that m < r.

29. Use the results of exercise 28 and the well-ordering principle for the integers to show that given any rational number r, there is an integer m such that m \leq r < m + 1.

30. Use the well-ordering principle to prove that given any integer n \geq 1, there exists an odd integer m and a nonnegative integer k such that n = 2^k \cdot m.

31. Give examples to illustrate the proof of Theorem 5.4.1.

32. Suppose P(n) is a property such that

    1. P(0), P(1), P(2) are all true,

    2. for each integer k \geq 0, if P(k) is true, then P(3k) is true. Must it follow that P(n) is true for every integer n \geq 0? If yes, explain why; if no, give a counterexample.

33. Prove that if a statement can be proved by strong mathematical induction, then it can be proved by ordinary mathematical induction. To do this, let P(n) be a property that is defined for each integer n, and suppose the following two statements are true:

    1. P(a), P(a + 1), P(a + 2) \dots, P(b).

    2. For any integer k \geq b, if P(i) is true for each integer i from a through k, then P(k + 1) is true.

The principle of strong mathematical induction would allow us to conclude immediately that P(n) is true for every integer n \geq a. Can we reach the same conclusion using the principle of ordinary mathematical induction? Yes! To see this, let Q(n) be the property

P(j) is true for each integer j with a \leq j \leq n.

Then use ordinary mathematical induction to show that Q(n) is true for every integer n \geq b. That is, prove:

1. $Q(b)$ is true.

2. For each integer $k \geq b$, if $Q(k)$ is true then $Q(k + 1)$ is true.

34. It is a fact that every integer n \geq 1 can be written in the form

 c_r \cdot 3^r + c_{r - 1} \cdot 3^{r - 1} + \dots + c_2 \cdot 3^2 + c_1 \cdot 3 + c_0 

where c_r = 1 or 2 and c_i = 0, 1, or 2 for each integer i = 0, 1, 2, \dots, r - 1. Sketch a proof of this fact.

35. Use mathematical induction to prove the existence part of the quotient-remainder theorem. In other words, use mathematical induction to prove that given any integer n and any positive integer d, there exists integers q and r such that n = dq + r and 0 \leq r < d.

36. Prove that if a statement can be proved using ordinary mathematical induction, then it can be proved by the well-ordering principle.

37. Use the principle of ordinary mathematical induction to prove the well-ordering principle for the integers.