- #1

- 42

- 2

## Homework Statement

Taking derivatives of generating functions is another useful operation. This is done termwise, that is, if

F(x) = f

_{0}+ f

_{1}x + f

_{2}x

^{2}+ f

_{3}x

^{3}+ · · · ,

then

F' (x) ::= f

_{1}+ 2f

_{2}x + 3f

_{3}x

^{2}+ · · · .

For example,

##\frac{1}{(1-x)^2} = (\frac{1}{(1-x)})'= 1 + 2x + 3x^2 +· · · ##

so

H(x) ::= ##\frac{x}{(1-x)^2} = 0 + 1x + 2x^2 + 3x^3 + · · · ##

is the generating function for the sequence of nonegative integers. Therefore

## \frac{1 + x}{ (1 − x)^3} = H' (x) = 1 + 2^2 x + 3^2 x^2 + 4^2x^3 + · · ·## ,

so

##\frac{x^2 + x}{ (1 − x)^3} = xH' (x) = 0 + 1x + 2^2 x^2 + 3^2 x^3 + · · · + n^2 x^n + · · ·##

is the generating function for the nonegative integer squares.

(a) Prove that for all k ∈ N, the generating function for the nonnegative integer kth powers is a quotient of polynomials in x. That is, for all k ∈ N there are polynomials R

_{k}(x) and S

_{k}(x) such that

##[x^n ] (\frac{R_k (x)}{S_k (x)})= n^k##. (2)

Hint: Observe that the derivative of a quotient of polynomials is also a quotient of polynomials. It is not necessary work out explicit formulas for R

_{k}and S

_{k}to prove this part.

(b) Conclude that if f(n) is a function on the nonnegative integers defined recursively in the form

##f(n) = af(n − 1) + bf(n − 2) + cf(n − 3) + p(n)\alpha ^n##

where the a, b, c, ##\alpha## ∈ C and p is a polynomial with complex coefficients, then the generating function for the sequence f(0), f(1), f(2), . . . will be a quotient of polynomials in x, and hence there is a closed form expression for f(n).

Hint: Consider

##\frac {R_k (\alpha x)} {S_k(\alpha x)}##

## Homework Equations

## The Attempt at a Solution

a) I am not quite sure what the brackets

##[x^n]##

mean. I haven't seen them in any other problems, but I'm assuming it's multiplication.

From this expression,

##\frac{x^2 + x}{ (1 − x)^3} = xH' (x) = 0 + 1x + 2^2 x^2 + 3^2 x^3 + · · · + n^2 x^n + · · ·##

any ##n^k## can be reached by taking the derivative of both sides (the LHS remains a quotient of polynomials in x), and then multiplying the both sides by x to prepare for taking another derivative. This process lets the LHS remain a quotient of polynomials in x. This process can be repeated indefinitely until the coefficient of ##x^n## is ##n^k##

b) I am not sure what my first steps should be in this problem. I see that in the hint, they put an ##\alpha## in the argument of each function. Where would this ##\alpha## "propagate" to?