CMSC 250 Fall 2004 -- Homework 8

Due Wed., Oct. 27 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 the following for integer $n$:
   1. $$\prod_{i=2}^{n} \left(1-\frac{1}{i^2}\right) = \frac{n+1}{2n}$$ for $n \geq 2$.
   2. $2^n < (n+1)!$ for $n \geq 2$.
   3. $$\sqrt{n} < \sum_{i=1}^{n} \frac{1}{\sqrt{i}}$$ for $n \geq 2$.
   4. Prove that any sum of two or more rational numbers is rational.
   5. Suppose $a_1,a_2,a_3,...$ is a sequence defined as follows:
      $$\begin{eqnarray*} a_1 = 1,a_2=3 & & \\ a_k=a_{k-2}+2a_{k-1} && \mbox{for all integers $k\geq 3$.} \end{eqnarray*}$$
      
      
      
      
      
      Prove that $a_n$ is odd for all $n \geq 1$.
   6. An L-tromino is composed by three squares and shaped like an L: =1ex
      
      . Use mathematical induction to prove that for any integer $n \geq 1$, if one square is removed from a $2^n\times 2^n$ checkerboard, the remaining squares can be completely covered by L-trominos.

      Figure 1: Example

      
2. Calculate the following: $1-2+2^2-2^3+\cdots+(-1)^n2^n$ where $n>0$.

Web Accessibility