1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Function Generation, Expressing in closed forms

  1. Apr 20, 2016 #1
    1. The problem statement, all variables and given/known data
    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)}##

    2. Relevant equations


    3. 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?
     
  2. jcsd
  3. Apr 21, 2016 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
    [tex] \sum_{n=0}^{\infty} n^k x^n = F_k(x) = \frac{S_k(x)}{(1-x)^{k+1}}, [/tex]
    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.
     
  4. Apr 21, 2016 #3
    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)##
     
  5. Apr 21, 2016 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted