# Function Generation, Expressing in closed forms

## 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)}##

## 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?

Ray Vickson
Homework Helper
Dearly Missed

## 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)}##

## 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.

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?

My guess is that the notation ##[x^n](F(x)## means the coefficient of ##x^n## in the expansion ##F(x) = \sum_{k=0}^{\infty} c_k x^k##. However, that is just a guess, as I have never before seen that notation.

$$\sum_{n=0}^{\infty} n^k x^n = F_k(x) = \frac{S_k(x)}{(1-x)^{k+1}},$$
and then get ##F_{k+1}(x)## by differentiation and multiplication by ##x##, to find a formula for ##S_{k+1}(x)##?

I have no idea what the ##\alpha## is all about, and I see no reason for it.

Your
$$\sum_{n=0}^{\infty} n^k x^n = F_k(x) = \frac{S_k(x)}{(1-x)^{k+1}},$$
and then get ##F_{k+1}(x)## by differentiation and multiplication by ##x##, to find a formula for ##S_{k+1}(x)##?

I have no idea what the ##\alpha## is all about, and I see no reason for it.

This advice is for part b, correct? Are we looking for
##S_k+1 (x)## because that is the closed form expression for f(n)?

Starting with
##\sum_{n=0}^{\infty} n^k x^n = F_k(x) = \frac{S_k(x)}{(1-x)^{k+1}}##
taking the derivative yields

##F_k'(x)=\sum_{n=0}^{\infty} n^{k+1} x^{n-1}= \frac{ (1-x) S_k '(x) + S_k (x) (k+1)}{ (1-x)^{k+2}}##
multiplying by x
##xF_k'(x)=\sum_{n=0}^{\infty} n^{k+1} x^n= \frac{ x(1-x) S_k '(x) + xS_k (x) (k+1)}{ (1-x)^{k+2}} = F_{k+1} (x) = \frac{S_{k+1} (x)}{ (1-x)^{k+2}}##

So
##S_{k+1}= xS_k '(x)(1-x) + x(k+1)S_k (x)##

Ray Vickson
Homework Helper
Dearly Missed
Your

This advice is for part b, correct? Are we looking for
##S_k+1 (x)## because that is the closed form expression for f(n)?

Starting with
##\sum_{n=0}^{\infty} n^k x^n = F_k(x) = \frac{S_k(x)}{(1-x)^{k+1}}##
taking the derivative yields

##F_k'(x)=\sum_{n=0}^{\infty} n^{k+1} x^{n-1}= \frac{ (1-x) S_k '(x) + S_k (x) (k+1)}{ (1-x)^{k+2}}##
multiplying by x
##xF_k'(x)=\sum_{n=0}^{\infty} n^{k+1} x^n= \frac{ x(1-x) S_k '(x) + xS_k (x) (k+1)}{ (1-x)^{k+2}} = F_{k+1} (x) = \frac{S_{k+1} (x)}{ (1-x)^{k+2}}##

So
##S_{k+1}= xS_k '(x)(1-x) + x(k+1)S_k (x)##

My advice is for part (a) as well (except that the denominator function is specified); basically, if I were doing it I would do both parts (a) and (b) together--or, rather, I would not split it up into two parts at all.

I cannot figure out exactly what the "##f(n)##" is in the question; it seems to me that if the question is just asking for a generating function of the sequence ##\{n^k\}## it should just say so.

QuietMind