MATH2800 Introduction to Discrete Structures

Second Exam, Tuesday, October 23, 2007.

You may use one sheet of handwritten notes, but no other sources. The exam consists of six questions, and lasts fifty minutes. Please work all six problems. Please show all work clearly and in reasonable detail. Answers without appropriate supporting work or requested explanations may not receive full credit. No calculators are allowed. Please ring your section below:

1. (20 points) Let $f_n$ denote the $n$th Fibonacci number. Thus, $f_0=0$, $f_1=1$, and $f_n=f_{n-1}+f_{n-2}$ for $n\geq 2$. Prove that
   
   $$f_1+f_3+ \ldots + f_{2n-1} = f_{2n}$$
   
   
   when $n$ is a positive integer.

2. (10 points) How many bit strings of length eight either begin 10 or end 010? (Express your answer as an integer.)

3. (20 points) Let $n$ be a positive integer. Prove that
   
   $$\sum_{k=0}^n 3^k \left(\begin{array}{c}n \\ k \end{array} \right) = 4^n.$$
   
   

4. (25 points) Victor's Donuts sells five different types of donuts, namely apple, pumpkin, chocolate, glazed, and jelly. Liz orders a box of six donuts at the drive-thru window.
   1. Assume that at least six donuts of each type are available.
      1. (7 points) In how many ways can the six donuts be chosen? (Express your answer in factorials and/or powers of integers.)
      2. (10 points) What is the probability that Liz ends up with exactly two jelly donuts? (Express your answer in factorials and/or powers of integers.)
   2. (8 points) Now assume there are only four pumpkin donuts left, and there are at least six of each of the other four types. In how many ways can the six donuts be chosen? (Express your answer in factorials and/or powers of integers.)

5. (10 points) A biased coin has probability $\frac{2}{3}$ of heads and $\frac{1}{3}$ of tails. This coin is flipped three times. What is the probability of obtaining an even number of heads? (Express your answer as a fraction whose numerator and denominator are relatively prime.)

6. (15 points) Juan is taking an art class. On any given day the instructor is one of Cecilia, Harold, or Suri. Cecilia is the instructor half the time, and each of the other two is the instructor a quarter of the time. These instructors have different preferences for the class. If Cecilia is teaching then the students draw figures with probability 0.6 and landscapes with probability 0.4. If Harold is teaching then the students draw figures with probability 0.5 and landscapes with probability 0.5. If Suri is teaching then the students draw figures with probability 0.3 and landscapes with probability 0.7. When Juan meets up with Xu one day after class he tells her that they drew figures that day. What is the probability that Cecilia was the instructor that day? (Express your answer as a fraction whose numerator and denominator are relatively prime.)