CMSC 250 Fall 2004 -- Homework 8 Answer

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$.
      Answer:

      Base case

      ($n=2$):

      • LHS: $$\prod_{i=2}^{2} \left(1-\frac{1}{i^2}\right) = 1-\frac{1}{2^2} = \frac{3}{4}$$
      • RHS: $$\frac{2+1}{2\cdot 2} = \frac{3}{4}$$
      • Since LHS = RHS the statement is true for $n=2$.

      Inductive hypothesis

      ($n=k-1$):

      $$\prod_{i=2}^{k-1} \left(1-\frac{1}{i^2}\right) = \frac{k}{2(k-1)}$$

      Inductive step

      ($n=k$): Show:

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

      Proof:

      $$\prod_{i=2}^{k} \left(1-\frac{1}{i^2}\right)$$

      $$= \prod_{i=2}^{k-1} \left(1-\frac{1}{i^2}\right)\times\prod_{i=k}^{k} \left(1-\frac{1}{i^2}\right)$$ (by splitting the product)

      $$= \prod_{i=2}^{k-1} \left(1-\frac{1}{i^2}\right) \times \left(1-\frac{1}{k^2}\right)$$ (by expanding the one term product)

      $$= \frac{k}{2(k-1)} \left(1-\frac{1}{k^2}\right)$$ (by IH)

      $$= \frac{k}{2(k-1)} \frac{k^2-1}{k^2}$$ (by finding common denom.)

      $$= \frac{k}{2( k-1)} \frac{(k-1)(k+1)}{k^2}$$ (by factoring the binomial)

      $$= \frac{k+1}{2k}$$ (by cancellation)

      
      

   2. $2^n < (n+1)!$ for $n \geq 2$.
      Answer:

      Base case

      ($n=2$):

      • LHS: $2^2=4$
      • RHS: $(2+1)!=3!=6$
      • Since LHS $<$ RHS the statement is true for $n=2$.

      Inductive hypothesis

      ($n=k$): $2^k < (k+1)!$

      Inductive step

      ($n=k+1$): Show: $2^{k+1} < ((k+1)+1)!$

      Proof:

      $$2^{k+1}$$

      $$= 2\cdot 2^k$$ (by factorring out a 2)

      $$< 2\cdot (k+1)!$$ (by IH)

      $$< (k+2)\cdot (k+1)! \mbox{(since $2<k+2$\ for all values of $k>0$)}$$

      $$= (k+2)!$$ (by def of factorial)

      
      

      Alternative answer to the proof portion:

      Proof:
      Part 1 (find the $b$ value) $2<(k+1)!$ by IH
      $2(2^k)<2(k+1)!$ by multiplyig both side by 2
      $2^{k+1}<2(k+1)!$
      Let $b=2(k+1)!$.
      Part 2 (show that $b\leq ((k+1)+1)!$ in other words that $2(k+1)! \leq ((k+1)+1)!$)
      

      Assume $2(k+1)! > ((k+1)+1)!$
      $2(k+1)!>(k+2)(k+1)!$ by def of factorial
      $2>k+2$ by dividing both sides by $(k+1)!$ - legal because $(k+1)!>0$
      $0>k$ contradiction to the fact that $k \geq 2$

      $2(k+1)! \leq ((k+1)+1)!$ by CCW
      From part 1 we know $2^{k+1}<2(k+1)!$
      So by the transitive property we know $2^{k+1} < ((k+1)+1)!$

   3. $$\sqrt{n} < \sum_{i=1}^{n} \frac{1}{\sqrt{i}}$$ for $n \geq 2$.
      Answer:

      Base case

      $n=2$, $\sqrt{2} < 1 + \frac{1}{\sqrt{2}}$.

      Inductive hypothesis

      ($n=k$): $$\sqrt{k} < \sum_{i=1}^{k} \frac{1}{\sqrt{i}}$$

      Inductive step

      ($n=k+1$): Show: $$\sqrt{k+1} < \sum_{i=1}^{k+1} \frac{1}{\sqrt{i}}$$

      Proof:

      $$\sum_{i=1}^{k+1} \frac{1}{\sqrt{i}}$$

      $$\sum_{i=1}^{k} \frac{1}{\sqrt{i}} + \sum_{i=k+1}^{k+1} \frac{1}{\sqrt{i}}$$ (by splitting the summation)

      $$= \sum_{i=1}^{k} \frac{1}{\sqrt{i}} + \frac{1}{\sqrt{k+1}}$$ (by expanding the one term of the summation)

      $$> \sqrt{k} + \frac{1}{\sqrt{k+1}}$$ (by IH)

      $$= \frac{\sqrt{k(k+1)}+1}{\sqrt{k+1}}$$ (by finding a common denom)

      $$> \frac{k+1}{\sqrt{k+1}} \mbox{(since $\sqrt{k^2+k}>k$\ for all values of $k\geq1$)}$$

      $$= \sqrt{k+1}$$

      
      

      Alternative answer:
      Proof:
      Part 1 (find $b$ value between the other two)
      $\sqrt{k} <\sum_{i=1}^k \frac{1}{\sqrt{i}}$ by IH
      $\sqrt{k} + \sum_{i=k+1}^{k+1} \frac{1}{\sqrt{i}} < \sum_{i=1}^{k} \frac{1}{\sqrt{i}} + \sum_{i=k+1}^{k+1} \frac{1}{\sqrt{i}}$ by adding the same sum to both sides
      $\sqrt{k} + \sum_{i=k+1}^{k+1} \frac{1}{\sqrt{i}} < \sum_{i=1}^{k+1} \frac{1}{\sqrt{i}}$ by combining summations
      $\sqrt{k} + \frac{1}{\sqrt{k+1}} < \sum_{i=1}^{k+1} \frac{1}{\sqrt{i}}$ by expanding the one term of the summation
      Let $b = \sqrt{k} + \frac{1}{\sqrt{k+1}}$.
      Part 2 (show that $\sqrt{k+1}\leq b$ in other words that $\sqrt{k+1}\leq \sqrt{k}+\frac{1}{\sqrt{k+1}}$)
      

      Assume $\sqrt{k+1} >\sqrt{k}+\frac{1}{\sqrt{k+1}}$
      $\sqrt{k+1}-\frac{1}{\sqrt{k+1}} >\sqrt{k}$
      $\frac{k+1-1}{\sqrt{k+1}} >\sqrt{k}$
      $\frac{k}{\sqrt{k+1}} >\sqrt{k}$
      $k >\sqrt{k}\sqrt{k+1}$
      $k >\sqrt{k(k+1)}$
      $k^2 > k^2 + k$
      $0>k$ contradiction

      $\sqrt{k+1}\leq \sqrt{k}+\frac{1}{\sqrt{k+1}}$ by CCW.
      From part 1 we know $\sqrt{k} + \frac{1}{\sqrt{k+1}} < \sum_{j=1}^{k+1} \frac{1}{\sqrt{i}}$
      Therefore by the transitive property we know $\sqrt{k+1} < \sum_{j=1}^{k+1} \frac{1}{\sqrt{i}}$
      

   4. Prove that any sum of two or more rational numbers is rational.
      Answer: $n$ is representing the number of rationals being summed.

      Base case

      ($n=2$): Let $x$ and $y$ be arbitrary in $Q$. $\exists a,b \in Z \quad x = \frac{a}{b} \wedge b\neq 0$
      $\exists c,d \in Z \quad x = \frac{a}{b} \wedge d\neq 0$ by def of rational
      $x+y = \frac{a}{b} + \frac{c}{d} = \frac{ad+bc}{bd}$
      $ad+bc \in Z$ by closure of $Z$ in $+$ and $\times$
      $bd \in Z$ by closure of $Z$ in $\times$
      $bd \neq 0$ since both $b\neq0$ and $d\neq0$
      $\frac{ad+bc}{bd} \in Q$ by def of rational
      $x+y \in Q$ by substitution
      Since $x$ and $y$ were arbitrary rationals, the sum of any two rationsl in rational.

      Inductive hypothesis

      ($n=k$): the sum of $k$ rational numbers is rational.

      Inductive step

      ($n=k+1$): show: the sum of $k+1$ rational numbers is rational.
      Proof: when looking at a sum of $k+1$ rationals, it can be divided into a sum of $k$ rationals and a single raitonal based on the associative property of addition. Since by the IH, the sum of the $k$ raitonal numbers must be a single rational number, the problem is reduced to being the sum of two rational numbers. We know from the base that the sum of two rational numbers is rational. Therefore the sum of $k+1$ rational numbers is rational.

   5. Suppose $a_1,a_2,a_3,...$ is a sequence defined as follows:
      

      $$a_1 = 1,a_2=3$$

      $$a_k=a_{k-2}+2a_{k-1} \mbox{for all integers $k\geq 3$.}$$

      
      
      Prove that $a_n$ is odd for all $n \geq 1$.
      Answer:

      Base case

      ($n=1$): $a_1 = 1$ is odd. ($n=2$): $a_2 = 3$ is odd.

      Inductive hypothesis

      ( $n=i \quad \forall i \in Z \quad 1\leq i\leq k \quad a_i \in Z^{odd}$)

      Inductive step

      ($n=k+1$):

      $$a_{k+1} = a_{k-1} + 2a_k$$

      $$\mbox{($a_{k-1}\in Z^{odd}$\ and $a_{k}\in Z^{odd}$\ by IH, $\exists c,c' \in Z$\ s.t. $a_{k-1}=2c-1,a_k=2c'-1$\ )}$$

      $$= 2c-1 + 2(2c'-1)$$

      $$= 2(c+2c'-1) -1$$

      
      

      which is odd.

   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.
      Answer:

      Base case

      ($n=1$): $2^1 \times 2^1$:

      

      Inductive hypothesis

      ($n=k$): if one square is removed from a $2^k \times 2^k$ checkerboard, the remaining squares can be completely covered by L-trominos.

      Inductive step

      ($n=k+1$): Show: if one square is removed from a $2^{k+1}\times2^{k+1}$ checkerboard, the remaining squares can be covered by L-trominos.

      Proof:

      1. Divide the checkerboard into 4 checkerboards each of size $2^k \times 2^k$, namely upper left (UL), upper right (UR), lower left (LL) and lower right (LR).
      2. Without loss of generality assume that the square removed is in region UL. Then UL can be completely covered by L-trominos by induction hypothesis.
      3. Remove 1 square from the top right of region LL, top left of region LR, and lower left of region UR. Then these regions can be covered by L-trominos by induction hypothesis.
      4. The 3 squares removed in previous step can be covered by an L-tromino.

      Figure: Example

      

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

   $$1-2+2^2-2^3+\cdots+(-1)^n2^n$$

   $$= \sum_{i=0}^{n} (-2)^i$$

   $$\mbox{(Since $\sum_{i=0}^n r^i =\frac{r^{n+1}-1}{r-1}$. See Eg 4.2.3 in textbook.)}$$

   $$= \frac{(-2)^{n+1}-1}{-2-1}$$

   $$= - \frac{(-2)^{n+1}-1}{3}$$

   
   

Web Accessibility