# Generating Function via Recurrence Relation

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?

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;
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