CMSC250, Spring 2004 Homework 8 Answers

Due Wednesday, March 31 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.

1. Prove $$\forall n \in {\bf {Z}}^+ \ \sum_{i=1}^n \left\lceil \frac{i}{2} \right\rceil > \frac{(n-1)(n+2)}{4}$$.
   • Answer:

     Base Case:

     $(n=1)$
     (LHS) $$\sum_{i=1}^1 \left\lceil \frac{i}{2} \right\rceil = \left\lceil 1/2 \right\rceil = 1$$
     (RHS) $$\frac{(n-1)(n+2)}{4} = \frac{(1-1)(1+2)}{4} = 0$$
     $1>0 \quad \surd$

     Inductive Hypothesis:

     $(n=k)$
     $$\sum_{i=1}^k \left\lceil \frac{i}{2} \right\rceil > \frac{(k-1)(k+2)}{4}$$

     Inductive Step:

     $(n=k+1)$

     Show:

     $$\sum_{i=1}^{k+1} \left\lceil \frac{i}{2} \right\rceil > \frac{((k+1)-1)((k+1)+2)}{4} = \frac{k(k+3)}{4}$$

     Proof:

     $$\sum_{i=1}^{k+1} \left\lceil \frac{i}{2} \right\rceil = \sum_{i=1}^{k} \left\lceil \frac{i}{2} \right\rceil + \sum_{i=k... ...} \left\lceil \frac{i}{2} \right\rceil + \left\lceil \frac{k+1}{2} \right\rceil$$

     $$> \frac{(k-1)(k+2)}{4} + \left\lceil \frac{k+1}{2} \right\rceil$$ (by IH)

     
     

     By the definition of ceiling, we know $\left\lceil \frac{k+1}{2} \right\rceil - 1 < \frac{k+1}{2} \leq \left\lceil \frac{k+1}{2} \right\rceil$.

     
     
     Specifically, by reversing one of the inequalities, we know $\left\lceil \frac{k+1}{2} \right\rceil \geq \frac{k+1}{2}$.

     
     
     So we can substitute $\frac{k+1}{2}$ for $\left\lceil \frac{k+1}{2} \right\rceil$.

     $$\sum_{i=1}^{k+1} \left\lceil \frac{i}{2} \right\rceil > \frac{(k-1)(k+2)}{4} + \frac{k+1}{2} = \frac{(k-1)(k+2)}{4} + \frac{2+2}{4}$$

     $$> \frac{k^2 + k -2 +2k + 2}{4} = \frac{k^2 + 3k}{4} = \frac{k(k+3)}{4} \quad \surd$$

     
     

2. Prove $$\forall n \in {\bf {Z}}^+ \ 8 \mid \left(2^{3n+1} \right)$$.
   • Answer: Let $n$ be an arbitrary positive integer.
     $2^{3n+1} = 2^3 \cdot 2^{3n-2} = 8 \cdot 2^{3n-2}$.
     Since $3n-2$ is nonnegative (since $n \geq 1$),
     $2^{3n-2}$ is an integer since the integers are closed under multiplication.
     Therefore, by the definition of divides,
     $8 \mid \left(2^{3p+1}\right)$.

3. Prove $$\forall n \in {\bf {Z}}^+ \ 8 \mid \left(3^{2n}+7 \right)$$.
   • Answer:

     Base Case:

     $(n=1)$
     $3^{2(1)} + 7 = 9+7 = 16$, and $8 \mid 16. \quad \surd$

     Inductive Hypothesis:

     $(n=k)$
     $$8 \mid \left( 3^{2k} + 7 \right)$$

     Inductive Step:

     $(n=k+1)$

     Show:

     $$8 \mid \left( 3^{2(k+1)} + 7 \right)$$

     Proof:

     
     $3^{2(k+1)} + 7= 3^{2k+2} + 7 = 9 \cdot 3^{2k} + 7$
     Now add a convenient form of zero to the right side:
     $3^{2(k+1)} + 7 = 9 \cdot 3^{2k} + 7 + [ 8\cdot 7 - 8 \cdot 7]$
     $3^{2(k+1)} + 7 = 9 \cdot 3^{2k} + 9 \cdot 7 - 8 \cdot 7$
     $3^{2(k+1)} + 7 = 9 \left( 3^{2k} + 7 \right) - 8 \cdot 7$

     By the IH, we know $$8 \mid (3^{2k} + 7)$$.
     By the definition of divides, $\exists p \in {\bf {Z}}$ such that $8p = 3^{2k} + 7$.

     $3^{2(k+1)} + 7 = 9 \left( 8p \right) - 8 \cdot 7 = 8 ( 9p-7 )$.
     Since $9p-7 \in {\bf {Z}}$ by closure of the integers under addition and multiplication,
     $8 \mid \left( 3^{2(k+1)} + 7 \right)$.

     Alternate Proof:

     Here's another way of doing the ``proof'' part.
     $3^{2(k+1)} + 7= 3^{2k+2} + 7 = 9 \cdot 3^{2k} + 7$

     By the IH, we know $$8 \mid (3^{2k} + 7)$$.
     By the definition of divides, $\exists p \in {\bf {Z}}$ such that $8p = 3^{2k} + 7$.
     So $3^{2k} = 8p - 7$ by algebra.

     $3^{2(k+1)} + 7 = 9 \cdot 3^{2k} + 7 = 9 \left( 8p-7 \right) + 7 = 72p - 63 + 7 = 72p-56 = 8(9p-7)$. Since $9p-7 \in {\bf {Z}}$ by closure of the integers under addition and multiplication,
     $8 \mid \left( 3^{2(k+1)} + 7 \right)$.

4. Prove $$\forall n \in {\bf {Z}}^+ \ 8 \mid \left( 2^{3n+1} + 3^{2n} - 1 \right)$$.
   • Answer: We give three different solutions to this problem. The first one doesn't even use induction!

     Solution 1:
     Let $n$ be an arbitrary positive integer.
     Realize that $2^{3n+1} + 3^{2n} - 1 = 2^{3n+1} + 3^{2n} - 1 + (8-8) = 2^{3n+1} + 3^{2n} + 7 - 8$.
     Since $n \in {\bf {Z}}^+$, we can use question 2 and state $8 \mid (2^{3n+1})$.
     Since $n \in {\bf {Z}}^+$, we can use question 3 and state $8 \mid (3^{2n}+7)$.
     Therefore, $\exists p, q \in {\bf {Z}}$ such that $8p = 2^{3n+1}$ and $8q = 3^{2n}+7$ by definition of divides.
     Then $2^{3n+1} + 3^{2n} + 7 - 8 = 8p + 8q - 8 = 8(p + q - 1)$ by substitution.
     Since $p + q - 1 \in {\bf {Z}}$ by closure of ${\bf {Z}}$ under addition,
     $8 \mid \left( 2^{3n+1} + 3^{2n} - 1 \right)$ by definition of divides.

     Solution 2:

     Base Case:

     $(n=1)$
     $2^4 +3^2-1 = 24$, and $8 \mid 24. \quad \surd$

     Inductive Hypothesis:

     $(n=k)$
     $$8 \mid \left( 2^{3k+1} + 3^{2k} - 1 \right)$$

     Inductive Step:

     $(n=k+1)$

     Show:

     $8 \mid \left( 2^{3(k+1)+1} + 3^{2(k+1)} - 1 \right)$

     Proof:

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

     $$= 2^{3k+1 + 3} + 3^{2k+2} - 1$$

     $$= 2^3 \cdot 2^{3k+1} + 3^2 \cdot 3^{2k} - 1$$

     $$= 8 \cdot 2^{3k+1} + 9 \cdot 3^{2k} - 1$$

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

     $$= 9 \cdot 2^{3k+1} + 9 \cdot 3^{2k} - 9 - 2^{3k+1} +8$$

     $$= 9 \left( 2^{3k+1} + 3^{2k} - 1 \right) - 2^{3k+1} +8$$

     $$8 \mid \left( 2^{3k+1} + 3^{2k} - 1 \right) \exists p \in {\bf {Z}} 2^{3k+1} + 3^{2k} - 1 = 8p$$

     $$= 9(8p) - 2^{3k+1} + 8$$ by substitution

     $$k \in {\bf {Z}}^+ 8 \mid 2^{3k+1} \exists \ell \in {\bf {Z}} 2^{3k+1} = 8\ell$$

     $$= 9(8p) - 8\ell + 8$$ by substitution

     $$= 8(9p - \ell +1)$$

     
     

     Since $9p - \ell +1 \in {\bf {Z}}$ by closure of ${\bf {Z}}$ under multiplication, subtraction, and addition,
     $8 \mid \left( 2^{3(k+1)+1} + 3^{2(k+1)} - 1 \right)$ by definition of divides.

     Solution 3: Do the same induction process up until the ``Proof'' part...

     Proof:

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

     $$= 2^{3k+1 + 3} + 3^{2k+2} - 1$$

     $$= 2^3 \cdot 2^{3k+1} + 3^2 \cdot 3^{2k} - 1$$

     $$= 8 \cdot 2^{3k+1} + 9 \cdot 3^{2k} - 1$$

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

     $$= 8 \cdot 2^{3k+1} + 8 \cdot 3^{2k} - 8 + 3^{2k} + 7$$

     $$= 8 \left( 2^{3k+1} + 3^{2k} - 1 \right) - 3^{2k} + 7$$

     $$8 \mid \left( 2^{3k+1} + 3^{2k} - 1 \right) \exists p \in {\bf {Z}} 2^{3k+1} + 3^{2k} - 1 = 8p$$

     $$= 8(8p) + 3^{2k} + 7$$ by substitution

     $$k \in {\bf {Z}}^+ 8 \mid 3^{2k} + 7 \exists \ell \in {\bf {Z}} 3^{2k} + 7 = 8\ell$$

     $$= 8(8p) + 8\ell$$ by substitution

     $$= 8(8p + \ell)$$

     
     

     Since $8p + \ell \in {\bf {Z}}$ by closure of ${\bf {Z}}$ under multiplication and addition,
     $8 \mid \left( 2^{3(k+1)+1} + 3^{2(k+1)} - 1 \right)$ by definition of divides.

5. Let $a_0 = 2$, $a_1 = 7$, and $\forall n \in {\bf {Z}}^{>1} \ a_n = 3a_{n-1} - 2a_{n-2}$. Prove $\forall n \in {\bf {Z}}^{\text{nonneg}} \ a_n \equiv_5 2$.
   • Answer:

     Base Case:

     $(n=0, 1)$
     $a_0 = 2 \equiv_5 2 \quad \surd \qquad a_1=7\equiv_5 2 \quad \surd$

     Inductive Hypothesis:

     $\forall i \in {\bf {Z}}\ 0 \leq i < k$
     $a_i \equiv_5 2$

     Inductive Step:

     $(n=k)$

     Show:

     $a_k \equiv_5 2$

     Proof:

     Assume $k >1$, since the base cases cover the other possibilities.
     Since $k >1$, $a_k = 3a_{k-1} - 2a_{k-2}$.
     Since $0 \leq k-1 < k$ and $0 \leq k-2 < k$, we can invoke the inductive hypothesis on $a_{k-1}$ and $a_{k-2}$: $a_{k-1} \equiv_5 2$ and $a_{k-2} \equiv_5 2$.
     Then $\exists p, q \in {\bf {Z}}$ such that $a_{k-1} = 5p+2$ and $a_{k-2}=5q+2$ by definitions of divides and equivalence in a mod.
     $a_k = 3a_{k-1} - 2a_{k-2} = 3(5p+2) - 2(5q+2)$ by substitution.
     $a_k = 15p + 6 - 10q - 4 = 15p + 10q +2$ by algebra.
     Then $a_k-2 = 5(3p+2q)$ by algebra.
     Since $3p+2q \in {\bf {Z}}$ by closure of the integers under multiplication and addition,
     $5 \mid a_k - 2$ by definition of divides.
     $a_k \equiv_5 2$ by definition of equivalence in a mod.

6. Let $c_0 = 0$, $c_1 = 1$, and $\forall n \in {\bf {Z}}^{>1} \ c_n = c_{\left\lfloor \frac{n}{2} \right\rfloor } + c_{\left\lfloor \frac{n}{3} \right\rfloor }$.

   Prove $\forall n \in {\bf {Z}}^{\geq 0} \ c_n \leq n$.

   • Answer:

     Base Case:

     $(n=0, 1)$
     $c_0 = 0 \leq 0 \quad \surd \qquad c_1 = 1 \leq 1 \quad \surd$

     Inductive Hypothesis:

     $\forall i \in {\bf {Z}}\ 0 \leq i < k$
     $c_i \leq i$

     Inductive Step:

     $(n=k)$

     Show:

     $c_k \leq k$

     Proof:

     Assume $k >1$, since the base cases cover the other possibilities.
     Since $k >1$, $c_k = c_{\left\lfloor \frac{k}{2} \right\rfloor } + c_{\left\lfloor \frac{k}{3} \right\rfloor }$.
     Since $0 \leq \left\lfloor \frac{k}{2} \right\rfloor < k$ and $0 \leq \left\lfloor \frac{k}{3} \right\rfloor < k$, we can invoke the inductive hypothesis on $c_{\left\lfloor \frac{k}{2} \right\rfloor }$ and $c_{\left\lfloor \frac{k}{3} \right\rfloor }$: $c_{\left\lfloor \frac{k}{2} \right\rfloor } \leq \left\lfloor k/2 \right\rfloor$ and $c_{\left\lfloor \frac{k}{3} \right\rfloor } \leq \left\lfloor k/3 \right\rfloor$.
     Therefore, $c_k = c_{\left\lfloor \frac{k}{2} \right\rfloor } + c_{\left\lfloor \frac{k}{3... ...\rfloor } \leq \left\lfloor k/2 \right\rfloor + \left\lfloor k/3 \right\rfloor$ by substitution.
     Now we want to show that $\left\lfloor k/2 \right\rfloor + \left\lfloor k/3 \right\rfloor \leq k$, so let's assume the opposite and derive a contradiction.

     
     
     Assume: $\left\lfloor k/2 \right\rfloor + \left\lfloor k/3 \right\rfloor > k$
     By the definition of floor, $k/2 \geq \left\lfloor k/2 \right\rfloor$ and $k/3 \geq \left\lfloor k/3 \right\rfloor$.
     Then $k/2 + k/3 > k$ by substitution.
     Since $k/2 + k/3 = (5/6)k$ by algebra, $(5/6)k > k$ by substitution.
     Solving for $k$, we get $k < 0$, which is a contradiction, since $k \in {\bf {Z}}^{\geq 0}$.

     
     

     So now we know $\left\lfloor k/2 \right\rfloor + \left\lfloor k/3 \right\rfloor \leq k$, and from before, we know that $c_k \leq \left\lfloor k/2 \right\rfloor + \left\lfloor k/3 \right\rfloor$.
     By the transitivity of $\leq$, we conclude that $c_k \leq k$.

7. Prove $$\forall n \in {\bf {Z}}^$$nonneg$\ \sum_{i=0}^n \left( \left(2n-i \right) 2^i \right) = (n+1) \left( 2^{n+1}-2\right)$.
   • Answer:

     Base Case:

     $(n=0)$
     (LHS) $$\sum_{i=0}^0 \left( \left(2(0)-i \right) 2^i \right) = \left( \left(2(0)-0 \right) 2^0 \right) = 0$$
     (RHS) $(0+1)(2^{0+1}-2) = 2-2 = 0$
     $0 = 0$

     Inductive Hypothesis:

     $(n=k)$
     $$\sum_{i=0}^k \left( \left(2k-i \right) 2^i \right) = (k+1) \left( 2^{k+1}-2\right)$$

     Inductive Step:

     $(n=k+1)$

     Show:

     $$\sum_{i=0}^{k+1} \left( \left(2(k+1)-i \right) 2^i \right) = ((k+1)+1) \left( 2^{(k+1)+1}-2\right)$$

     Proof:

     $$\sum_{i=0}^{k+1} \left( \left(2(k+1)-i \right) 2^i \right) = \sum_{i=0}^k \left( \left(2(k+1)-i \right) 2^i \right) + \sum_{i=k+1}^{k+1} \left( \left(2(k+1)-i \right) 2^i \right)$$

     $$= \sum_{i=0}^k \left( \left(2k+2-i \right) 2^i \right) + (2(k+1)-(k+1))2^{k+1}$$

     $$= \sum_{i=0}^k \left( \left(2k-i \right) 2^i + 2(2^i) \right) + (k+1)2^{k+1}$$

     $$= \sum_{i=0}^k \left( \left(2k-i \right) 2^i \right) + 2\sum_{i=0}^k \left( 2^i \right) + (k+1)2^{k+1}$$

     $$= (k+1) \left( 2^{k+1}-2\right)+ 2\sum_{i=0}^k \left( 2^i \right) + (k+1)2^{k+1}$$ (by IH)

     $$= (k+1) \left( 2^{k+1}-2\right)+ 2\left[ 2^{k+1}-1\right] + (k+1)2^{k+1}$$ (by sum of a geometric sequence)

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

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

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

     
     

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002 (1.62)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -nonavigation -antialias_text -antialias hw8ans

The translation was initiated by Phillip Kirlin on 2004-03-31

Web Accessibility