Module 8 Homework Problems

Prove the following statements by induction.

1. “For all \(n\geq 0,\ \sum_{i=0}^n 3^i=\frac{3^{n+1}-1}{2}\)”
2. “For all \(n\geq 0,\ \sum_{i=0}^n 4^i=\frac{4^{n+1}-1}{3}\)”
3. Let \(r\) be some unknown real number except \(1\). Prove “For all \(n\geq 1,\ \sum_{i=0}^n r^i=\frac{r^{n+1}-1}{r-1}\)”
4. Why did we need to make the exception for \(r=1\) in the last problem? (In other words, what happens in the equation if \(r=1\))?

Note that the equation in problem #3 gives you a formula that you can use to almost instantly calculate the sum of a (terminating) geometric sequence. Use this observation to calculate the following:

5. \(\sum_{i=0}^{20} 5^i\).
6. \(\sum_{i=0}^{20} \left(\frac{1}{2}\right)^i\)
7. \(\sum_{i=0}^{10} \frac{1}{2^i}\).
8. (Bonus +5) \(\sum_{i=2}^{20} 5^i\). (note that this sum “starts later”. This needs to be taken into account!)
9. (Bonus +10) \(\sum_{i=10}^{20} 2^i\).

Prove the following statements by induction

10. “For all \(n\geq 1\), \(\sum_{i=1}^n i^2=\frac{n(n+1)(n+2)}{6}\).”
11. “For all \(n\geq 2\), \(\sum_{i=1}^{n-1} i(i+1)=\frac{n(n-1)(n+1)}{3}\).”
12. “For all \(n\geq 0,\ 4\vert (5^n-1)\)”
13. “For all \(n\geq 0, 10\vert (11^{n}-1)\)”
14. (Bonus +20) Let \(p\) be a prime number. Prove that “for all \(n\geq 0,\ (p-1)\vert (p^n-1)\).”
15. (Bonus: +15) “For all \(n\geq 1\), \(6\vert (n(n^2+5))\)” (Hint: expand/FOIL everything and see if you can get things in the form \(k^3+5k+3k^2+3k+6\) and group the first two and last three terms, and factor it.  Then make an argument why \(k^2+k+2\) must be even no matter what \(k\) is.)
16. “For all \(n\geq 3\), \(4^{n-1}>n^2\)”
17. (Bonus +10) “For all \(n \geq 0\), \(4^n-1\geq 3n\)” (Hint: works similar to 13)