Generating Function via Recurrence Relation

Question

I am trying to find the solution to the following recurrence for polynomials: \begin{align*} h^{[0]}(z) &= z \\ h^{[n+1]}(z) &= z h^{[n]}(z) (z+z^2+...+z^{n+1}) +z \end{align*} I calculated the first polynomials, yet couldn't find any obvious pattern (neither could I find it with the help of OEIS). Also my limited Maple-knowledge wasn't enough to find a solution (I tried rsolve, but I guess I don't understand the syntax for polynomials completely).

Is there a closed-form expression for these polynomials? And how can I solve such recurrences with Maple or Mathematica?

Answer 1

Fortunately that summation term z+z^2+...+z^(n+1) can be put into a closed form. Otherwise you might have to combine what can be thought of as a mixed pair of recurrences.

That summation term can be dealt with by either rsolve or, more simply, the sum command.

palt:=rsolve({b(n)=b(n-1)+z^(n),b(1)=z},b(n));

                                    2         n 
                                   z       z z  
                     palt := z - ------ + ------
                                 -1 + z   -1 + z

p:=sum(z^i,i=1..n);

                             (n + 1)         
                            z            z   
                       p := -------- - ------
                             -1 + z    -1 + z

simplify( p - palt );

                                  0

Now we can solve the problem. Below, I'll focus on finding h(n).

sol:=rsolve({h(n)=h(n-1)*z*p+z,h(0)=z},h(n)):

where sol has products and summations (with n in the index bounds) but is no longer a recurrence relation.

lprint(sol);

     (z^2/(-1+z))^n*(-1+z)*(product(z^(n0+1)-1, n0 = 0 .. n))*(sum((z^2/(-1+z))^
     (-n1)/(product(z^(n0+1)-1, n0 = 0 .. n1)), n1 = 0 .. n-1))/((z^(n+1)-1)*z)
     +(product(z^(n0+1)-1, n0 = 0 .. n))*(z^2/(-1+z))^n*z/(z^(n+1)-1)

We may test that result for a few cases of n, by comparing with a recursive procedure set up to compute similar to the original recurrence.

It's your choice whether to put the results into expanded, factored, or otherwise simplified form.

seq(factor(simplify(eval(sol,n=i))),i=0..3);

           / 2    \    / 5    4    3    2    \  
      z, z \z  + 1/, z \z  + z  + z  + z  + 1/, 

        / 9      8      7      6      5      4    3    2    \  
        \z  + 2 z  + 3 z  + 3 z  + 2 z  + 2 z  + z  + z  + 1/ z

makeh:=proc(n::nonnegint)
  if n=0 then z;
  else z*procname(n-1)*add(z^i,i=1..n)+z;
  end if;
end proc:

seq(factor(simplify(makeh(i))),i=0..3);

           / 2    \    / 5    4    3    2    \  
      z, z \z  + 1/, z \z  + z  + z  + z  + 1/, 

        / 9      8      7      6      5      4    3    2    \  
        \z  + 2 z  + 3 z  + 3 z  + 2 z  + 2 z  + z  + z  + 1/ z

seq( simplify( makeh(i) - eval(sol,n=i) ), i=0..10 );

                   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0