Math for computer science

1. Prove that f(x) = x3 – 1000x2 + x – 1 is (x3) and O(x3).

2. Prove that 1k + 2k + 3k + … + nk is (nk+1) and O(nk+1), for any fixed k>0.

3. Order the following functions in order of their growth rate. If f(x) is O(g(x)), but g(x) is not O(f(x)), then put f(x) above g(x). If they are each big-O of each other, then place them on the same level.  Beware:  some of these are easy to compare and some are not.

x2 + x3      3x      x!     x/log2x      x2+ 2x      xlog2x      2xlogx     logx2     2x+1 

log2x!      log2x      lnx     2x     x(1+2+…+ x)     loglogx      2x^2     log2x

4. Compute the sum of the infinite series below.

a. 1 + 1/4 + 1/16 + 1/64 + …

b. 1 + 2/4 + 3/16 + 4/64 + …

5. Telescoping Series.

a. Using the identity 1/((k)(k+1)) = 1/k – 1/(k+1), find the value of the infinite sum 1/(1*2) + 1/(2*3) + 1/(3*4) + ….

b. The nth triangle number is defined to be the sum of the first n positive integers. What is the value of the infinite sum of the reciprocals of the triangle numbers.

6. What’s wrong with the following proofs by induction?

a. Every binary string contains identical symbols (either all 0's or all 1's). The proof is by induction on the size of the string. For n=0 all binary strings are empty and therefore identical. Let X = bnbn-1…b1b0 be an arbitrary binary string of length n+1. Let Y = bnbn-1…b1 and Z = bn-1…b1b0. Since both Y and Z are strings of length less than n+1, by induction each contains identical symbols. Since the two strings overlap, X must also contain identical symbols.

b. Any amount of change greater than or equal to twenty can be gotten with a combination of five cent and seven cent coins. The proof is by induction on the amount of change. For twenty cents use four five-cent coins. Let n > 20 be the amount of change. Assume that n = 7x + 5y for some non-negative integers x and y. For any n > 20, either x > 1, or y > 3. If x > 1, then since 3(5) – 2(7) = 1, n+1 = 5(y+3)+7(x–2). If y > 3, then since 3(7) – 4(5) = 1, n+1 = 7(x+3)+5(y–4). In either case, we showed that n+1 = 7u + 5v where u and v are non-negative integers.

7. Prove by induction that:

a.   The nth Fibonacci number equals (1/√5)[(1/2 + √5/2)n – (1/2 – √5/2)n ], where F0 = 0 and F1 = 1.

b.   The sum of the geometric series 1 + a + a2 + … + an equals (1–an+1)/(1–a), where a does not equal one.

c.    21 divides 4n+1 + 5 2n-1