2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.