## Mathematical Induction

The following is the list of problems for Chapter 10 of the Book of Proof (page 169). There is a forum open at the end, so you can ask questions. It is a great way to interact with the instructor and with other students in your class, should you need some assistance with any question. Please, do not post solutions.

Prove the following statements with either induction, strong induction or proof by smaller counterexample.

1. For every integer $$n \in \mathbb{N},$$ it follows that $$1 + 2 + 3 + 4 + \dotsb + n = \frac{n^2+n}{2}.$$
2. For every integer $$n \in \mathbb{N},$$ it follows that $$1^2 + 2^2 + 3^2 + 4^2 + \dotsb + n^2 = \frac{n(n+1)(2n+1)}{6}.$$
3. For every integer $$n \in \mathbb{N},$$ it follows that $$1^3 + 2^3 + 3^3 + 4^3 + \dotsb + n^3 = \frac{n^2(n+1)^2}{4}.$$
4. If $$n \in \mathbb{N},$$ then $$1\cdot 2 + 2\cdot 3 + 3\cdot 4 + 4\cdot 5 + \dotsb + n(n+1) = \frac{n(n+1)(n+2)}{3}.$$
5. If $$n \in \mathbb{N},$$ then $$2^1 + 2^2 + 2^3 + \dotsb + 2^n = 2^{n+1}-2.$$
6. For every natural number $$n,$$ it follows that $$\sum_{k=1}^n (8k-5) = 4n^2-n.$$
7. If $$n \in \mathbb{N},$$ then $$1\cdot 3 + 2\cdot 4 + 3\cdot 5 + 4\cdot 6 + \dotsb + n(n+2) = \frac{n(n+1)(2n+7)}{6}.$$
8. If $$n \in \mathbb{N},$$ then $$\frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!} + \dotsb + \frac{n}{(n+1)!} = 1 - \frac{1}{(n+1)!}.$$
9. For any integer $$n \geq 0,$$ it follows that $$24 \vert (5^{2n}-1).$$
10. For any integer $$n \geq 0,$$ it follows that $$3 \vert (5^{2n}-1).$$
11. For any integer $$n \geq 0,$$ it follows that $$3 \vert (n^3+5n+6).$$
12. For any integer $$n \geq 0,$$ it follows that $$9 \vert (4^{3n}+8).$$
13. For any integer $$n \geq 0.$$ it follows that $$6 \vert (n^3-n).$$
14. Suppose that $$a \in \mathbb{Z}.$$ Prove that $$5 \vert 2^n a$$ implies $$5 \vert a$$ for any $$n \in \mathbb{N}.$$
15. If $$n \in \mathbb{N},$$ then $$\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \frac{1}{3\cdot 4} + \frac{1}{4\cdot 5} + dotsb + \frac{1}{n(n+1)} = 1 - \frac{1}{n+1}.$$
16. For every natural number $$n,$$ it follows that $$2^n +1 \leq 3^n.$$
17. Suppose $$A_1, A_2, \dotsc, A_n$$ are sets in some universal set $$U,$$ and $$n \geq 2.$$ Prove that $$(A_1 \cap A_2 \cap \dotsb \cap A_n)^\complement = A_1^\complement \cup A_2^\complement \cup \dotsb \cup A_n^\complement.$$
18. Suppose $$A_1, A_2, \dotsc, A_n$$ are sets in some universal set $$U,$$ and $$n \geq 2.$$ Prove that $$(A_1 \cup A_2 \cup \dotsb \cup A_n)^\complement = A_1^\complement \cap A_2^\complement \cap \dotsb \cap A_n^\complement.$$
19. Prove that $$\frac{1}{1} + \frac{1}{4} + \frac{1}{9} + \dotsb + \frac{1}{n^2} \leq 2 - \frac{1}{n}.$$
20. Prove that $$(1+2+3+\dotsb+n)^2 = 1^3 + 2^3 + 3^3 + \dotsb + n^3$$ for every $$n \in \mathbb{N}.$$
21. If $$n \in \mathbb{N},$$ then $$\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \dotsb + \frac{1}{2^n -1} + \frac{1}{2^n} \geq 1 + \frac{n}{2}.$$
22. If $$n \in \mathbb{N},$$ then $$\big( 1-\frac{1}{2} \big) \big( 1-\frac{1}{4} \big) \big( 1-\frac{1}{8} \big) \big( 1-\frac{1}{16} \big) \dotsb \big( 1-\frac{1}{2^n} \big) \geq \frac{1}{4} + \frac{1}{2^{n+1}}.$$
23. Use mathematical induction to prove the binomial theorem (use equation (3.2) on page 78.)
24. Prove that $$\sum_{k=1}^n k \binom{n}{k} = n 2^{n=1}$$ for each natural number $$n.$$
25. Concerning the Fibonacci sequence, prove that $$F_1 + F_2 + F_3 + F_4 + \dotsb + F_n = F_{n+2}-1.$$
26. Concerning the Fibonacci sequence, prove that $$\sum_{k=1}^n F_k^2 = F_n F_{n+1}.$$
27. Concerning the Fibonacci sequence, prove that $$F_1 + F_3 + F_5 + F_7 + \dotsb + F_{2n-1} = F_{2n}.$$
28. Concerning the Fibonacci sequence, prove that $$F_2 + F_4 + F_6 + F_8 + \dotsb + F_{2n} = F_{2n+1}-1.$$
29. In this problem $$n \in \mathbb{N}$$ and $$F_n$$ is the $$n$$th Fibonacci number. Prove that $$\binom{n}{0} + \binom{n-1}{1} + \binom{n-2}{2} + \binom{n-3}{3} + \dotsb + \binom{0}{n} = F_{n+1}.$$
30. Here $$F_n$$ is the $$n$$th Fibonacci number. Prove that $$F_n = \frac{\phi_1^n - \phi_2^n}{\sqrt{5}},$$ where $$\phi_1 = \frac{1+\sqrt{5}}{2}$$ and $$\phi_2 = \frac{1-\sqrt{5}}{2}.$$
31. Prove that $$\sum_{k=0}^n \binom{k}{r} = \binom{n+1}{r+1},$$ where $$1 \leq r \leq n.$$
32. Prove that the number of $$n$$-digit binary numbers that have no consecutive 1’s is the Fibonacci number $$F_{n+2}.$$
33. Suppose $$n$$ straight lines lie on a plane in such a way that no two of the lines are parallel, and no three of the lines intersect at a single point. Show that this arrangement divides the plane into $$\frac{n^2+n+2}{2}$$ regions.
34. Prove that $$3^1 + 3^2 + 3^3 + 3^4 + \dotsb + 3^n = \frac{3^{n+1}-3}{2}$$ for every $$n \in \mathbb{N}.$$
35. Prove that if $$n,k \in \mathbb{N},$$ and $$n$$ is even and $$k$$ is odd, then $$\binom{n}{k}$$ is even.
36. Prove that if $$n = 2^k-1$$ for some $$k \in \mathbb{N},$$ then every entry in the $$n$$th row of Pascal’s triangle is odd.
37. Prove that if $$m,n \in \mathbb{N},$$ then $$\sum_{k=0}^n k \binom{m+k}{m} = n \binom{m+n+1}{m+1} - \binom{m+n+1}{m+2}.$$
38. Prove that if $$n$$ is a positive integer, then $$\binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \dotsb + \binom{n}{n}^2 = \binom{2n}{n}.$$
39. Prove that if $$n$$ is a positive integer, then $$\binom{n+0}{0} + \binom{n+1}{1} + \binom{n+2}{2} + \dotsb + \binom{n+k}{n} = \binom{n+k+1}{k}.$$
40. Prove that $$\sum_{k=0}^p \binom{m}{k} \binom{n}{p-k} = \binom{m+n}{p}$$ for positive integers $$m, n$$ and $$p.$$.
41. Prove that $$\sum_{k=0}^m \binom{m}{k} \binom{n}{p+k} = \binom{m+n}{m+p}$$ for positive integers $$m, n$$ and $$p.$$.