- #1
QuietMind
- 42
- 2
Homework Statement
Taking derivatives of generating functions is another useful operation. This is done termwise, that is, if
F(x) = f0 + f1x + f2x2 + f3x3 + · · · ,
then
F' (x) ::= f1 + 2f2x + 3f3x2 + · · · .
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 Rk(x) and Sk(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 Rk and Sk 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 let's 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?