CMSC 250 Homework 8 Spring 2003

Due Wed March 29 at the beginning of your discussion section.

You must write the solutions to the problems single-sided on your own lined paper, with all sheets stapled together, and with all answers written in sequential order or you will lose points. For each of the following statements say whether it is TRUE or FALSE. If true, use mathematical induction to prove it. If false, give a specific counter example.

1. $\forall n \in Z^{\geq 1},\,\,\sum_{i=1}^{n}(2i+1)=(n+1)^{2}-1.$ TRUE. Proof (by mathematical induction)
   Base Case: (n=1)
   LHS: $\sum_{i=1}^{n}(2i+1) ~=~ 2*1 + 1 ~=~ 3$
   RHS: $(n+1)^{2}-1 ~=~ (1+1)^{2}-1 ~=~ 3$
   LHS = RHS since $3 ~=~ 3$.
   Inductive Hypothesis:
   Assume true for $n-1$. $\sum_{i=1}^{n-1}(2i+1) ~=~ ((n-1)+1)^{2}-1 ~=~ n^2-1.$
   Inductive Step:
   
   $$\begin{eqnarray*} \sum_{i=1}^{n}(2i+1) & ~=~ & \sum_{i=1}^{n-1}(2i+1) ~+~ 2n+1... ...a} \\ & ~=~ & (n+1)^2 -1 ~+~ 2n+1 ~~~~~~~~~~\mbox{by algebra} \end{eqnarray*}$$
   
   
   
   
   
   QED
2. $\forall n\in Z^{\geq 1}, 7\vert 2^{3n} - 1$. TRUE. Proof (by mathematical induction)
   Base Case: (n=1)
   $2^{3n}-1 ~=~ 2^{3*1}-1 ~=~ 7$.
   $7\vert 7$.
   Inductive Hypothesis:
   Assume true for $n-1$. Then $7\vert 2^{3(n-1)} - 1$. Inductive Step:
   Since $7\vert 2^{3(n-1)} - 1$, there exists $k \in Z$ such that $2^{3(n-1)} - 1 ~=~ 7k$.
   $$\begin{eqnarray*} 2^{3n}-1 & ~=~ & 2^3*2^{3(n-1)}-1 ~~~~~~~~~~\mbox{by algebra}... ...ebra} \\ & ~=~ & 2^3(7k) + 7 ~~~~~~~~~~\mbox{by substitution} \end{eqnarray*}$$
   
   
   
   
   
   QED
3. $\forall n \in Z^{+},\,\,\sum_{i=1}^n\frac{1}{i(i+1)} = \frac{n}{n+1}$ TRUE. Base Case: (n=1)
   LHS: $\sum_{i=1}^n\frac{1}{i(i+1)} ~=~ \sum_{i=1}^1\frac{1}{i(i+1)} ~=~ \frac{1}{1(1+1)} ~=~ \frac{1}{2)}.$
   RHS: $\frac{n}{n+1} ~=~ \frac{1}{1+1} ~=~ \frac{1}{2}$
   LHS = RHS since $\frac{1}{2} ~=~ \frac{1}{2}$. Inductive Hypothesis:
   Assume true for $n$. Then $\sum_{i=1}^n\frac{1}{i(i+1)} = \frac{n}{n+1}$. Inductive Step:
   
   $$\begin{eqnarray*} \sum_{i=1}^{n+1}\frac{1}{i(i+1)} & ~=~ & \sum_{i=1}^{n}\fr... ... \\ & ~=~ & \frac{n + 1}{(n+1)+1} ~~~~~~~~~~\mbox{by algebra} \end{eqnarray*}$$
   
   
   
   
   
   QED
4. $\forall n\in Z^{\geq 2}, 3\vert 4^{n} + 1$. FALSE. Proof (by counterexample)
   $n =2:$
   $4^{n} + 1 ~=~ 4^2 + 1 ~=~ 17$.
   $3 \not \vert 17$.
   QED
5. $\forall n \in Z^{\geq 3}, \,\,\,n^2\geq 2n+3$ TRUE. Proof (by mathematical induction)
   Base Case: (n=3)
   LHS: $n^2 ~=~ 3^2 ~=~ 9$
   RHS: $2n+3 ~=~ 2*3+3 ~=~ 9$
   LHS $\geq$ RHS since $9 ~\geq~ 9$.
   Inductive Hypothesis:
   Assume true for $n-1$. Then $(n-1)^2 \geq 2(n-1)+3$. Inductive Step:
   
   $$\begin{eqnarray*} n^2 & ~=~ & n^2 - 2n + 1 + 2n - 1 ~~~~~~~~~~\mbox{by algebra}... ... & ~\geq~ & 2n + 3 ~~~~~~~~~~\mbox{since $2n > 3$\ for $n > 3$} \end{eqnarray*}$$
   
   
   
   
   
   QED
6. $\forall n \in Z^{\geq 0}, \,\,\, 2(n+2) \leq (n+2)^2$ TRUE. Proof (by mathematical induction)
   Base Case: (n=0)
   LHS: $2(n+2) ~=~ 2(0+2) ~=~ 4$
   RHS: $(n+2)^2 ~=~ (0+2)^2 ~=~ 4$
   LHS $\leq$ RHS since $4 ~\leq~ 4$.
   Inductive Hypothesis:
   Assume true for $n-1$. Then $2((n-1)+2) \leq ((n-1)+2)^2$ or $2(n+1) \leq ((n+1)^2$. Inductive Step:
   We reverse the inequality.
   $$\begin{eqnarray*} (n+2)^2 & ~=~ & n^2 + 4n + 4 ~~~~~~~~~~\mbox{by algebra} \\ ... ... algebra} \\ & ~\geq~ & 2(n + 2) ~~~~~~~~~~\mbox{since $n>0$} \end{eqnarray*}$$
   
   
   
   
   
   QED
7. $\forall n \in Z^{\geq 2},\,\,\, \sum_{k=2}^n \frac{1}{k-1} = \frac{n}{2}$ FALSE. Let $n=4$.
   LHS: $\sum_{k=2}^n \frac{1}{k-1} ~=~ \sum_{k=2}^4 \frac{1}{k-1} ~=~ 1 + 1/2 + 1/3 ~=~ 11/6$.
   RHS: $\frac{4}{2} ~=~ 2$.
   LHS $\neq$ RHS since $11/6 ~\neq~ 2$.
   
8. $\forall n \in Z^{\geq 0},\,\,\, 2 \vert (n+2)!$ TRUE. Proof (by mathematical induction)
   Base Case: (n=0)
   $(n+2)! ~=~ (0+2)! ~=~ 2! ~=~ 2$.
   $2\vert 2$.
   Inductive Hypothesis:
   Assume true for $n-1$. Then $2 \vert ((n-1)+2)!$ or $2 \vert (n+1)!$. Inductive Step:
   Since $2 \vert (n+1)!$ (by IH), there exists $k \in Z$ such that $(n+1)! ~=~ 2k$ (by definition of divides).
   Thus $(n+1)! ~=~ 2k$.
   Thus $(n+2)(n+1)! ~=~ (n+2)2k$.
   Thus $(n+2)! ~=~ 2(n+2)k$.
   Since $Z$ is closed under addition and multiplication, $(n+2)k$ is an integer.
   So $2\vert(n+2)!$ by definition of divides.
   QED

Web Accessibility