Hand-In HW 2 due 2/25
Centrality of Generating Functions

1. Compute a₀, a₁, a₂ directly using Taylor's coefficient formula (record your computations). Then use Wolfram Alpham or other software to find the Taylor series up to order 20: f(x) = a₀ + a₁x + ··· + a₂₀x²⁰ + higher terms (include an image with the explicit coefficients, or copy them by hand).
2. In the equation (1−x−x²−x³) ∑_k≥0 a_k x^k = 1, expand the left side and equate the x^k coefficients with those on the right side: 1 + 0x + 0x² + 0x³ + ···. Use this to find a recurrence equation for a_k with k ≥ 3. Use the recurrence to compute a₃, a₄, . . . , a₂₀, and compare with the computer values from Prob 1.
   Extra Credit: Recall the delayed reproduction model for Fibonacci numbers: Start with 1 newborn pair of rabbits at month 1, which mature during month 2, then they reproduce 1 new pair at month 3, and so on for the offspring, with no mortality; then F_k is the number of pairs at month k. Give a similar model for the tribonacci numbers, explaining why it works. Draw an analog of the Fibonacci tree from the previous HW.
3. Here is the graph of the generating function:
   
   To accurately find the vertical asymptote, the roots of the denominator polynomial
   g(x) = 1 − x − x² − x³ = 0,
   recall Newton's Method from calculus: to accurately approximate the solution of an equation g(x) = 0, start with an initial guess x₀, and repeatedly refine it using the recurrence:
   x_k  =  x_k−1 − ^g(x_k−1)⁄_{g' (xk−1)} .
   That is, the tangent line to y = g(x) at (x_k−1, g(x_k−1)) intersects the x-axis at x_k.

   Problems

   • Use Newton's Method to approximate the vertical asymptote x = α of f(x), starting with the initial guess x₀ = 0.5 . Continue until x_k is accurate to 5 decimal places (i.e. the approximation no longer changes in these places). Use a calculator, spreadsheet, or other software, and print out or copy by hand the successive x_k's.
   • Use Wolfram Alpha or a similar system to find the remaining complex-number roots of the denominator: x = β = b + ci and x = γ = b − ci, where i = √(−1): solve 1−x−x²−x³ = 0. Switch to Approximate Form to find these numerically to 5 decimal places.
   • Plot α, β, and γ on the complex number plane. Hint: The real root x = α is closest to the origin x = 0, while x = β, γ are farther away and symmmetric to each other across the real axis.
   • Extra Credit Approximate the complex roots β, γ with Newton's method, using the same recursive formula for complex numbers as for reals. Start with an initial complex number x₀ fairly close to the correct values. (For spreadsheets, complex numbers are handled as text, with special complex operations on them.)
4. Given the roots x = α, β, γ of the denominator, we have
   1 − x − x² − x³  =  (1 − ^x⁄_α)(1 − ^x⁄_β)(1 − ^x⁄_γ),
   and we know there must be a partial fraction decomposition of the form:
   f(x)   =   ^A⁄_{(1 − x/α)} + ^B⁄_{(1 − x/β)} + ^C⁄_{(1 − x/γ)} .
   Problem: Find the coefficient A of the dominant term using the residue method: clear denominators, substitute x = α, and solve for A in terms of α, β, γ, then compute the result numerically using software or other methods.
   Hint: You can compute with complex numbers just as with real numbers: all algebraic laws hold. During the computation, work with the letters α, β, γ. Once you have a simplified algebraic answer, only then substitute the numerical values from the previous problem. Use a few extra decimal places of accuracy for α, β, γ, then round the final answer to 5 places.
5. The first term in the decomposition must be dominant in the Taylor series of f(x) since x = α is the vertical asymptote closest to x = 0. Expand this geometric series to deduce a formula of the form a_k ≈ A r^k, approximating by an exponential sequence with appropriate values of A and r, rounded to 5 decimal places. Compute this formula numerically for n = 0, . . . , 20, and compare to the known values of a₀, . . . , a₂₀ . What accounts for the error?
   Extra Credit: Estimate the error in the approximation a_k ≈ A r^k, assuming exact values of A and r. Is it true that a_k = round(A r^k)? How many decimal places of accuracy would you need for α and A to compute a₁₀₀ exactly? Which is more compuationally efficient to find large a_n exactly, the exponential approximation or the recurrence formula?
6. Expand f(x) as:
   f(x)   =   ¹⁄_{(1 − (x+x²+x³))}   =   ∑_ℓ≥0 (x + x² + x³)^ℓ,
   and translate this algebraic expression into a logical choice algorithm. That is, find a family of combinatorial objects A = A₀ ∪ A₁ ∪ A₂ ∪ ··· such that a_k = |A_k|, counting the objects of size k.
   After defining your combinatorial interpretation, illustrate it by listing the 7 objects corresponding to a₄ = 7.
   Hint: x + x² + x³ can be interpreted as choosing the number 1 or 2 or 3.