Homework 6#

Due: Thursday, October 8, 2026 23:59 Submit: Gradescope, through Blackboard’s assignment area.

Please write your homework by hand. Start each exercise on a new page, scan your work to a legible PDF, and clearly mark the pages associated with every exercise. Show the algebra used to obtain each generating function or closed formula.

1. (From a generating function to a recurrence)#

Points: 10

The ordinary generating function of a sequence is

  1. 4 points. Determine initial data , , and . Show your calculations. Explain which terms you disregard.

  2. 6 points. Determine the recurrence satisfied by , including its valid index range, and use it to compute and . Explain your derivation.

2. (From a recurrence to a generating function)#

Points: 10

Let be defined by Let .

  1. 10 points. Multiply the recurrence by and sum over all . Rewrite every sum in terms of and the standard series Solve the resulting equation for and give your answer as a single rational function.

3. (Solving a homogeneous recurrence)#

Points: 10

Solve the recurrence Your solution must include the characteristic polynomial, its roots, the general form of a solution to the recurrence, and the use of the two initial conditions to determine the constants. Check your closed formula at against a direct recurrence calculation.

4. (A nonhomogeneous recurrence with two driving terms)#

Points: 10

Solve the recurrence

  1. 4 points. Treat and as separate driving terms. For each driving term, write an appropriate trial form for a particular solution. Explain why the trial for needs an extra factor of .

  2. 4 points. Substitute both trial forms into the recurrence and determine their unknown coefficients. Add the two particular solutions to the general homogeneous solution.

  3. 2 points. Write down the general formula for the homogeneous solution.

  4. 4 points. Use the initial conditions to determine the remaining constants. Check your final formula at against a direct recurrence calculation.