# COT 3100 - Quiz 2 *Michael Akinyemi Tue/Thur - 9 AM* ### Problem 1 (10 pts) Prove by induction that $\sum^{n}_{i=1} 2i^2 + 5i + 2 = \frac{4n^3 + 21n^2+29n}{6}$ **Base Case:** Let $n=1$, then: $\sum^{1}_{i=1} 2i^2 + 5i + 2 = 2(1)^2 + 5(1) + 2 = 9$ and $\frac{4n^3 + 21n^2+29n}{6} = \frac{4(1)^3 + 21(1)^2+29(1)}{6}=9$, base case holds. **Inductive Hypothesis:** Accept that $\sum^{k}_{i=1} 2i^2 + 5i + 2 = \frac{4k^3 + 21k^2+29k}{6}$ **Inductive Step:** Show that $\sum^{k+1}_{i=1} 2i^2 + 5i + 2 = \frac{4(k+1)^3 + 21(k+1)^2+29(k+1)}{6}$ Note that: $\frac{4(k+1)^3 + 21(k+1)^2+29(k+1)}{6} = \frac{4(k^3+3k^2+3k+1) + 21(k^2+2k+1) + 29k + 29}{6} = \frac{4k^3+12k^2+12k+4+21k^2+42k+21+29k+29}{6} = \frac{4k^3+33k^2+83k+54}{6}$ $\sum^{k+1}_{i=1} 2i^2 + 5i + 2 = (\sum^{k}_{i=1} 2i^2 + 5i + 2) + 2(k+1)^2 + 5(k+1) + 2$ $=\frac{4k^3+21k^2+29k}{6} + 2(k^2+2k+1) + 5k + 5 + 2$ $=\frac{4k^3+21k^2+29k}{6} + 2k^2+4k+2+5k+5+2$ $=\frac{4k^3+21k^2+29k}{6} + 2k^2+9k+9$ $=\frac{4k^3+21k^2+29k + 12k^2 + 54k + 54}{6}$ $=\frac{4k^3+33k^2+83k+54}{6}$ …as desired. By induction, $\sum^{n}_{i=1} 2i^2 + 5i + 2 = \frac{4n^3 + 21n^2+29n}{6}$ for positive integers $n$. ### Problem 2 (10 pts) Prove by induction that for positive integers $n$, $13 \vert (4^{2n+1} + 3^{n-1})$ **Base Case:** Let $n=1$, then $4^{2n+1}+3^{n-1}=4^3+3^0=65$, which is divisible by $13$, base case holds. **Inductive Hypothesis:** Accept that $13 \vert (4^{2k+1} + 3^{k-1})$ which implies that for some integer $x$, $13x=4^{2k+1}+3^{k-1}$ **Inductive Step:** Show that $13 \vert (4^{2(k+1)+1} + 3^{(k+1)-1})$ From $13 \vert (4^{2k+1} + 3^{k-1})$ it is implied that for some arbitrary positive integer $x$, $13x=4^{2k+1}+3^{k-1}$ By the definition of addition, we have that $13x=4^{2k+1}$ and $13x = 3^{k-1}$ $4^{2(k+1)+1} + 3^{(k+1)-1} = 4^{2k+3} + 3^{(k-1)+1}$ $=4^2(4^{2k+1}) + 3^1(3^{k-1})$ $=4^2(13x) + 3(13x)$ $=13(16x + 3x)$ … which is divisible by 31. By induction, $13 \vert (4^{2n+1} + 3^{n-1})$ for all positive integers $n$.