CMSC 250 Fall 2004 -- Homework 7 Answer

Due Wed., Oct. 20 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. Reduce each of the following expressions to a single numeric value:
   1. $$\sum_{j=1}^{5} \frac{(-1)^j}{j}$$
      Answer: $-\frac{47}{60}$
   2. $$\prod_{k=0}^{10} \frac{10-k}{2^k}$$
      Answer: 0
   3. $$\prod_{i=1}^3 \left( \sum_{j=i}^3 i \cdot j \right)$$
      Answer: 540
2. For each of the following, change the sum and/or products into sum or product notation:
   1. $$\frac{1}{2!} + \frac{2}{3!} + \frac{3}{4!} + \cdots + \frac{n}{(n+1)!}$$
      Answer: $$\sum_{i=1}^{n} \frac{i}{(i+1)!}$$
   2. $$n + \frac{n-1}{2!} + \frac{n-2}{3!} + \frac{n-3}{4!} + \cdots + \frac{1}{n!}$$
      Answer: $$\sum_{i=1}^{n} \frac{n-i+1}{i!}$$
3. Prove the following facts for $n \geq 1$:
   1. $11^n - 6$ is divisible by 5.
      Answer: Proof by induction on $n$.
      Base case: ($n=1$)
      $11^1-6 = 11-6 = 5$
      $5\vert 5$
      
      

      Therefore the statement is true when n is 1.
      
      Inductive Hypothesis: ($n=k-1$)
      
      

      $$5 \vert 11^{k-1} - 6$$
      
      
      
      
      

      Inductive Step: ($n=k$)
      Show:
      

      $$5 \vert 11^k - 6$$
      
      
      
      

      Proof:
      

      $$11^k - 6 = 11*11^{k-1}-6 = (10*11^{k-1}) + (11^{k-1}-6) = 5*2*11^{k-1} + (11^{k-1} -6)$$
      
      
      Since $5\vert 11^{k-1} -6$ by the Inductive Hypothesis
      $\exists x \in Z, 11^{k-1} - 6 = 5x$ by the definition of divides
      
      $11^k-6 = 5*2*11^{k-1} + 5x$ by substitution.
      $= 5(2*11^{k-1}+x)$ by distributing out the 5
      Since $2*11^{k-1}+x \in Z$ by closure of Z in addition
      $5 \vert 5(2*11^{k-1}+x)$ by definition of divides
      $5 \vert 11^k -6$ by substitution
      

   2. $$\sum_{k=1}^n k(k-1)(k-2)(k-3) = \frac{(n+1)n(n-1)(n-2)(n-3)}{5}$$
      Answer: Proof by induction on $n$.
      Base case: ($n=1$)
      LHS = $\sum_{k=1}^1 k(k-1)(k-2)(k-3) = 1(1-1)(1-2)(1-3) = 1*0*-1*-2 = 0$
      RHS = $\frac{(1+1)(1)(1-1)(1-2)(1-3)}{5} = \frac{0}{5} = 0$
      Since the LHS = RHS, the statement is true when n = 1
      
      

      Inductive Hypothesis: ($n=m-1$)
      
      

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

      Inductive Step: ($n=m$)
      show:
      
      

      $$\sum_{k=1}^{m-1}k(k-1)(k-2)(k-3) = \frac{((m+1)m((m-1)((m-2)((m-3)}{5}$$
      
      
      
      proof:
      $\sum_{k=1}^m k(k-1)(k-2)(k-3)$
      $= \sum_{k=1}^{m-1} k(k-1)(k-2)(k-3) + \sum_{k=m}^m k(k-1)(k-2)(k-3)$ by splitting the summation
      $= \sum_{k=1}^{m-1} k(k-1)(k-2)(k-3) + m(m-1)(m-2)(m-3)$ by expanding the summation
      $\frac{m(m-1)(m-2)(m-3)(m-4)}{5} + \frac{5\cdot m(m-1)(m-2)(m-3) }{5}$ by the Inductive Hypothesis
      $\frac{m(m-1)(m-2)(m-3)((m-4)+5)}{5}$ by distribution
      $= \frac{(m+1)m(m-1)(m-2)(m-3)}{5}$ by algebra
      
   3. $$\sum_{i=1}^{n} i\cdot i! = (n+1)! -1$$
      Answer: Proof by induction on $n$.
      Base case: ($n=1$)
      LHS: $\sum_{i=1}{1} i \cdot i! = 1 \cdot 1! = 1 \cdot 1 = 1$
      RHS: $(1+1)! -1 = 2! -1 = 2-1 = 1$
      Since LHS = RHS the statement is true when $n=1$.
      
      Inductive Hypothesis: ($n=m-1$)
      
      
      $$\sum_{i=1}^{m-1} i \cdot i! = ((m-1)+1)! -1$$
      
      

      Inductive Step: ($n=m$)
      show:
      

      $$\sum_{i=1}^{m} i \cdot i! = (m+1)! -1$$
      
      

      proof:
      $\sum_{i=1}^{m} i\cdot i!$
      $= \sum_{i=1}^{m-1} i\cdot i! + \sum_{i=m1}^m i \cdot i!$ by splitting the summation
      $= \sum_{i=1}^{m-1} i\cdot i! + m\cdot m!$ by expanding the summation
      $= m! - 1 + m\cdot m!$by the IH
      $= (m+1)m! - 1$ by factorring out the $m!$
      $= (m+1)! -1$ by the definition of factorial
      

4. A convex polygon is a polygon with all interior angles $\leq 180$ degrees. Prove that the sum of the interior angles in any $n$-sided convex polygon is exactly $(n - 2) \cdot 180$ degrees, for all $n \geq 3$. (Reminder: The sum of the interior angles of any triangle is 180 degrees.)
   Answer: Proof by induction on $n$.
   Base case: ($n=3$)
   Given in the reminder. Since a figure where n=3 is a triangle,
   the sum of the interiorangles of a triangle is 180.
   $(3-2)\cdot 180 = 1 \cdot 180 = 180$
   
   Inductive Hypothesis: ($n=m-1$)
   It is true that the sum of the interior angles of a $m-1$-sided polygon is exactly $((m-1)-2) * 180$
   
   

   Inductive Step: ($n=m$)
   show:
   The sum of the interior angles of an $m$-sided polygon is exactly $(m-2)*180$
   
   Proof:
   Observe that the $m$-sided convex polygon can be cut into two convex polygons with one that is $(m-1)$-sided and the other one a triangle (do this by selecting any pair verticies that have exactly one other vertex between them - connect those two with a single straight line segment).
   By the IH, the sum of the interior angles of an $(m-1)$-sided polygon is $((m-1)-2) * 180$.
   The sum of the interior angles of a triangle is 180 as given.
   Sum of interior angles in $m$-sided convex polygon = sum of interior angles in $(m-1)$-sided convex polygon + sum of interior angles in a triangle = $((m-1)-2) *180 + 180$= $(m-3)*180 + 180$ = $(m-2)*180$.

Web Accessibility