Function Generation, Expressing in closed forms

[QuietMind]

Homework Statement

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

F(x) = f₀ + f₁x + f₂x² + f₃x³ + · · · ,
then
F' (x) ::= f₁ + 2f₂x + 3f₃x² + · · · .
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 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?

 

[Ray Vickson]

Homework Statement

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

F(x) = f₀ + f₁x + f₂x² + f₃x³ + · · · ,
then
F' (x) ::= f₁ + 2f₂x + 3f₃x² + · · · .
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.

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.

Aren't you being asked to start with
\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.

 

[QuietMind]

Your

Aren't you being asked to start with
\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]

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.