CS206 -Discrete Mathematics II
Instructor: Chitoor V.Srinivasan
PROBLEM SET 2b SOLUTIONS

  1. Assume, there was   tex2html_wrap_inline45   units of the isotope at the hour  n. Then the amount of isotope left at the hour  n+1  will be   tex2html_wrap_inline51 . Hence we get the recurrence equation,   tex2html_wrap_inline53 and the initial condition will specify what   tex2html_wrap_inline55   was.

  2. Let   tex2html_wrap_inline57   be the number of bacteria after  n  hours, where   tex2html_wrap_inline61 . Then,   tex2html_wrap_inline63  , since the number of New bacteria after  n  hours is   tex2html_wrap_inline67   and the number of Old bacteria after  n  hours is the same as the number of new bacteria after  n-1  hours which is   tex2html_wrap_inline73  . Initial conditions should specify   tex2html_wrap_inline75   and that   tex2html_wrap_inline77 .

  3. Let   tex2html_wrap_inline79   be the number of ways of climbing  n  steps. Then, by the conditions of the problem,   tex2html_wrap_inline83 , since the person could have reached step  n  either by directly jumping to it from step  n-3,  or by jumping to it from step  n-2  or by stepping on to it from step  n-1. The initial conditions are,   tex2html_wrap_inline93   and   tex2html_wrap_inline95 .

  4. Let B(n) be the number of length n bit sequences with an even number of zeroes. Such a bit sequence can be broken up into the first n-1 bits plus the last bit. The last bit is either a 0 or a 1.
    Case 1: The last bit is a 1. Then the preceeding n-1 bits contain an even number of zeroes and hence, there are B(n-1) such sequences.
    Case 2: The last bit is a 0. Then the preceding n-1 bits contain an odd number of zeroes. However, for any k the number of length k bit sequences with an odd number of zeroes equals the number of length k bit sequences with an even number of zeroes (can you prove this?). Thus, there are B(n-1) preceding sequences in this case.
    Thus, B(n) = B(n-1) + B(n-1) = 2 * B(n-1).

  5. (a). Let f(m) be the number of different ways the driver can pay n = 5m cents using only nickels and dimes. Then f(0) = f(1) = 1, and f(m) = f(m-1) + f(m-2) since the last coin dropped by the driver could be either a nickel or a dime. This is the fibbonaci series.

    (b). The answer is   tex2html_wrap_inline97   for  m = 9.   tex2html_wrap_inline101   and   tex2html_wrap_inline103 .

  6. First note that the Fibonacci numbers satisfy the given initial conditions. By repeated application of Fibonacci expansion, we have,   tex2html_wrap_inline105 = tex2html_wrap_inline107 = tex2html_wrap_inline109 = tex2html_wrap_inline111 . Hence the Fibonacci numbers satisfy the recurrence relation and the initial conditions.

    Show that   tex2html_wrap_inline113   is divisible by 5 for tex2html_wrap_inline115 . By mathematical induction.
    Base: n=1.   tex2html_wrap_inline117 is divisible by 5.
    Induction: Suppose   tex2html_wrap_inline113   is divisible by 5.
    tex2html_wrap_inline121 by the above recurrence.   tex2html_wrap_inline123 is a multiple of 5 and hence is divisible by 5. tex2html_wrap_inline125 is divisible by 5 by the induction hypothesis. Hence, the resulting expression is divisible by 5 and so is   tex2html_wrap_inline127 .