CMSC250, Spring 2004 Homework 7 Answers

Due Wednesday, March 17 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. Simplify this expression: $$\ln\left[ \prod_{i=1}^n e^{f(i)} \right]$$.
   • Answer:

     $$\ln\left[ \prod_{i=1}^n e^{f(i)} \right] = \ln\left[ e^{f(1)} \cdot e^{f(2)} \cdots e^{f(n)} \right]$$

     $$= \ln e^{f(1)} + \ln e^{f(2)} + \cdots + \ln e^{f(n)}$$

     $$= {f(1)} + {f(2)} + \cdots + {f(n)}$$

     $$= \sum_{i=1}^n f(i)$$

     
     

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

     Base Case:

     $(n=1)$
     (LHS) $$\sum_{i=1}^1 (2i)(2i-1) = (2)(2-1) = 2$$
     (RHS) $$\frac{1(1+1)(4-1)}{3} = \frac{2(3)}{3} = 2$$
     $2=2 \quad \surd$

     Inductive Hypothesis:

     $(n=k)$
     $$\sum_{i=1}^k (2i)(2i-1) = \frac{k(k+1)(4k-1)}{3}$$

     Inductive Step:

     $(n=k+1)$

     Show:

     $$\sum_{i=1}^{k+1} (2i)(2i-1) = \frac{(k+1)((k+1)+1)(4(k+1)-1)}{3}$$

     Proof:

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

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

     $$= \frac{k(k+1)(4k-1)}{3} + 2(k+1)(2k+1)$$ (by the IH)

     $$= \frac{k(k+1)(4k-1)}{3} + \frac{6(k+1)(2k+1)}{3}$$

     $$= \frac{(k+1)\left[ k(4k-1) + 6(2k+1) \right]}{3}$$

     $$= \frac{(k+1)\left[ 4k^2 + 11k + 6 \right]}{3}$$

     $$= \frac{(k+1)(k+2)(4k+3)}{3}$$

     $$= \frac{(k+1)((k+1)+1)(4(k+1)-1)}{3} \quad \surd$$

     
     

3. Prove $$\forall n \in {\bf {Z}}^+ \ \sum_{i=1}^n (4i-3) = n(2n-1)$$.
   • Answer:

     Base Case:

     $(n=1)$
     (LHS) $$\sum_{i=1}^1 (4i-3) = 4(1)-3 = 1$$
     (RHS) $$n(2n-1) = 1(2-1) = 1$$
     $1=1 \quad \surd$

     Inductive Hypothesis:

     $(n=k)$
     $$\sum_{i=1}^k (4i-3) = k(2k-1)$$

     Inductive Step:

     $(n=k+1)$

     Show:

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

     Proof:

     $$\sum_{i=1}^{k+1} (4i-3) = \sum_{i=1}^{k} (4i-3) + \sum_{i=k+1}^{k+1} (4i-3)$$

     $$= \sum_{i=1}^{k} (4i-3) + (4(k+1)-3)$$

     $$= k(2k-1) + 4(k+1)-3$$ (by the IH)

     $$= 2k^2 -k +4k+4-3 = 2k^2+3k+1$$

     $$= (k+1)(2k+1) = (k+1)(2(k+1)-1) \surd$$

     
     

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

     Base Case:

     $(n=1)$
     (LHS) $$\prod_{i=1}^1 2^{i} = 2$$
     (RHS) $$2^{\left(\frac{1}{2} + \frac{1}{2}\right)} = 2^1 = 2$$
     $2=2 \quad \surd$

     Inductive Hypothesis:

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

     Inductive Step:

     $(n=k+1)$

     Show:

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

     Proof:

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

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

     $$= 2^{\frac{k}{2} + \frac{k^2}{2} + k + 1} = 2^{\frac{k + k^2 + 2k + 2}{2}}$$

     $$= 2^{\frac{\left(k + 1\right) + \left( k^2 + 2k + 1 \right)}{2}} =2^{\left(\frac{k+1}{2} + \frac{(k+1)^2}{2}\right)} \quad \surd$$

     
     

5. Recall the recursive definition of the Fibonacci sequence:

   $$F_1 = 1$$

   $$F_2 = 1$$

   $$F_k = F_{k-1} + F_{k-2} k > 2.$$

   
   

   Let's perform a change of variable on the third line to get $F_{m+2} = F_{m} + F_{m+1}$ for $m > 0$, and $F_{n+3} = F_{n+1} + F_{n+2}$ for $n \geq 0$.

   Prove these interesting facts about this sequence:

   1. $$\forall n \in {\bf {Z}}^{+} \ \sum_{k=1}^{n} F_k = F_{n+2} - 1$$
      • Answer:

        Base Case:

        $(n=1)$
        (LHS) $$\sum_{k=1}^{1} F_k = F_1 = 1$$
        (RHS) $$F_{1+2} - 1 = F_3 - 1 = 2-1 = 1$$
        $1=1 \quad \surd$

        Inductive Hypothesis:

        $(n=p)$
        $$\sum_{k=1}^{p} F_k = F_{p+2} - 1$$

        Inductive Step:

        $(n=p+1)$

        Show:

        $$\sum_{k=1}^{p+1} F_k = F_{p+3} - 1$$

        Proof:

        $$\sum_{k=1}^{p+1} F_k = \sum_{k=1}^{p} F_k + \sum_{k=p+1}^{p+1} F_k = \sum_{k=1}^{p} F_k + F_{p+1}$$

        $$= F_{p+2} - 1 + F_{p+1}$$ (by the IH)

        $$= F_{p+1} + F_{p+2} - 1$$

        $$= F_{p+3} - 1$$ (by the definition of the Fib. seq.)

        
        

   2. $$\forall n \in {\bf {Z}}^{+} \ \sum_{k=1}^{n} F_k^2 = F_{n} \cdot F_{n+1}$$.
      • Answer:

        Base Case:

        $(n=1)$
        (LHS) $$\sum_{k=1}^{1} F_k^2 = F_1^2 = 1$$
        (RHS) $$F_{1} \cdot F_{1+1} = F_1\cdot F_2 = 1\cdot 1 = 1$$
        $1=1 \quad \surd$

        Inductive Hypothesis:

        $(n=p)$
        $$\sum_{k=1}^{p} F_k^2 = F_{p} \cdot F_{p+1}$$

        Inductive Step:

        $(n=p+1)$

        Show:

        $$\sum_{k=1}^{p+1} F_k^2 = F_{p+1} \cdot F_{p+2}$$

        Proof:

        $$\sum_{k=1}^{p+1} F_k^2 = \sum_{k=1}^{p} F_k^2 + \sum_{k=p+1}^{p+1} F_k^2 = \sum_{k=1}^{p} F_k^2 + F_{p+1}^2$$

        $$= F_p \cdot F_{p+1} + F_{p+1}^2$$ (by the IH)

        $$= F_{p+1}\left( F_p + F_{p+1} \right)$$

        $$= F_{p+1} \cdot F_{p+2} \quad \surd$$ (by the definition of the Fib. seq.)

        
        

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 hw7ans

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

Web Accessibility