Non-Programming Exercises:

1. Text, Exercise 2.2-2.

2. Text, Exercise 2.2-3 a. b., and d. [Just give the answer, without proof.]

3. Give a Big-Theta bound (that is, above and below) for the "mystery" program of Assignment 1 (problem 6). [Just an answer, not a proof.]

4. Suppose the n Fibonacci numbers are defined by
   F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2), for n >= 2

   Prove by mathematical induction that the following formula is true for all n >= 0:

   
       n
     +---
      \    F(i)  =  F(n+2) - 1
      /
     +---
     i = 0
   

5. Stirling's approximation to n! is (text, page 57)
   St(n) = sqrt(2 pi n)(n/e)ⁿ

   Use a program to check out how good this approximation is. Specifically, compare the ratio St(n)/n! for  n = 1, 2, 3, 4, 5, 10, 15, 20, 25, 50, 100, 150. [Hint: calculate everything as a double, since you can't represent anything bigger than 12! = 479001600 as an int. In either Java or C/C++ you will want to use the pow function. In C on a Sun, don't forget to compile with a -lm option because of the math functions. The program is especially easy to write in Java, with functions and constants: Math.pow, Math.PI, Math.E, and Math.sqrt. Your program should produce four columns, with n, n!, St(n), and St(n)/n! in the columns, roughly as shown below. You must include a source listing and the results of a run of the program.]

   
   n       n!      St(n)                   St(n)/n!
   -----------------------------------------------------------
   1       1.0     0.9221370088957891      0.9221370088957891
   2       2.0     1.9190043514889832      0.9595021757444916
   3       6.0     5.836209591345864       0.972701598557644
   

6. A better formula is adds an extra correction Factor to multiply times the basic formula
   Correction Factor: (1 + 1/(12 n) + 1/(288 n²) - 139/(51840 n³) - 571/(2488320 n⁴) + ...)

   In the program for item 1 above, use the first two terms of the Correction Factor to get more accurate results, that is, just multiply by (1.0 + 1.0/(12.0*n)) (ignoring the three higher terms) and see how much better the approximation is. (Print the same results as in 1.)

7. Check out the formulas for F(n) from the text (page 80) by writing a short program to calculate the formula. Specifically, set
   p = (1/2)(1 + sqrt(5)), q = (1/2)(1 - sqrt(5))

   Then

   F(n) = (pⁿ - qⁿ)/sqrt(5)

   Test this formula out by writing a program that will input an integer n and will calculate and print the three quantities:

   •  pⁿ/sqrt(5)
   •  qⁿ/sqrt(5)
   •  (pⁿ - qⁿ)/sqrt(5)

   Test the program at least with n = 1, 2, 3, 4, 5, 10, 15, 20, 25, 50, 100, 150.