CMSC250, Spring 2004 Homework 8

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.

Prove $\displaystyle \forall n \in {\bf {Z}}^+ \ \sum_{i=1}^n \left\lceil \frac{i}{2} \right\rceil > \frac{(n-1)(n+2)}{4}$ .
Prove $\displaystyle \forall n \in {\bf {Z}}^+ \ 8 \mid \left(2^{3n+1} \right)$ .
Hint: You do not need to use induction on this one.
Prove $\displaystyle \forall n \in {\bf {Z}}^+ \ 8 \mid \left(3^{2n}+7 \right)$ .
Prove $\displaystyle \forall n \in {\bf {Z}}^+ \ 8 \mid \left( 2^{3n+1} + 3^{2n} - 1 \right)$ .
Hint: You may use the facts already proved true in problems 2 and/or 3 to prove the statement in problem 4.
Let , , 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$ .
Let , , 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$ .
Prove $\displaystyle \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)$ .