CS 3341, Recitation Section, Problem list 1. For Jan 20, 22.

1. Show that a logarithm to one base is always just a constant
   multiple of a logarithm to another base.
   In particular, show that log2(n) = c*log10(n) by finding
   the constant c that works.  (log10 means "log base 10", etc.)

2. Suppose we are comparing implementations of insertion sort and
   merge sort on the same machine. For inputs of size n,
   insertion sort runs in 8n^2 steps while merge sort runs in
   64n lg n steps (lg is log2). For which values of n does insertion
   sort beats merge sort? 
   
3. Prove by mathematical induction that

   1*2 + 2*3 + 3*4 + ... + n*(n+1) = n*(n+1)*(n+2)/3
   
4. Suppose F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2), for n >= 2.
   (So F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, F(6) = 8, ....)
   
   Use induction to prove the following matrix identity:
   
               n
   |  0   1  |         |  F(n-1)   F(n)   |
   |         |     =   |                  |, where n >= 1
   |  1   1  |         |   F(n)   F(n+1)  |
   
   (The above are matrices, and on the left, we are multiplying
   the matrix times itself n times.)
   (Don't forget to do the basis step and the induction step.)