2013 January 14,

Assignment E

CS 202-00, Carleton College, Winter 2013

Prof. Joshua R. Davis, , Goodsell 204, x4473

A. Show, for all n ≥ 1, that the sum of the first n odd natural numbers is n2.

B. Define the nth Fibonacci number Fn by F0 = 0, F1 = 1, and, for all n ≥ 2, Fn = Fn - 1 + Fn - 2. In this problem, we will show that 1.5n < Fn < 1.66...n for large n.

  1. Prove for all n ≥ 0 that Fn < (5 / 3)n.
  2. Write a computer program to help you find a number N such that (3 / 2)N < FN. (Show the program and its output, and make a note indicating how the output shows us what N is.)
  3. Using your number N, prove for all n ≥ N that (3 / 2)n < Fn.

C. You cannot make exactly 15 cents by combining any number of dimes and quarters. But you can make any multiple of 5 cents greater than 15 cents — 20 cents, 25 cents, 30 cents, etc. Prove it.

D. Recall from calculus that every function f (except for some nasty functions, that we will ignore) has a derivative. The derivative is another function, denoted f ', with this meaning: At any point x, the value f '(x) is the slope of the graph of f at that x. For example, the function f(x) = x graphs as a straight line with slope 1, and the derivative is f '(x) = 1 for all x. A key fact of derivatives is the product rule: for any two functions f and g, (f g)' = f ' g + f g'. Using the product rule, prove for all n ≥ 1 that the derivative of f(x) = xn is f '(x) = n xn - 1.