2

We have the following recurrence relation for $a_{n,m}$

$a_{n,m}=4a_{n+1,m-1}+\sum_{i=0}^{n-1}\sum_{j=0}^{m}a_{i,j}a_{n-1-i,m-j}$

with the boundary condition $a_{n,0}=c_n$ for $n\ge0$ where $c_n$ are the Catalan numbers and $a_{0,m}=0$ for $m>0$. After defining the generating function

$\phi(x,y)=\sum_{n,m=0}^\infty x^n y^m a_{n,m}$

the relation becomes an easy quadratic equation for $\phi(x,y)$ which basically solves the problem. This equation however involves $A(y)=\sum_{m=0}^\infty y^m a_{1,m}$ as a parameter, which is not given by the boundary condition. Anybody any ideas on how this $A(y)$ can be determined from the recursion rules without knowing the solution for $a_{n,m}$?

Juraj
  • 21
  • This isn't really a recurrence relation for $a_{n,m}$, since $a_{n,m}$ occurs on both sides and cancels out (since $a_{0,0}=1$). Perhaps you should regard it as a recurrence relation for $a_{n+1,m-1}$? – joriki Sep 25 '12 at 08:07
  • 1
    I'm wondering: If we set $a_{n,-1}=0$, the recurrence for $a_{n,0}$ looks similar to the one for the Catalan numbers; they'd coincide if we had $n+1$ on the left and the sum on the right ran up to $n$. That makes me wonder whether you've got a typo in there somewhere, since the relation would make much more sense if the left-hand side didn't occur in the sum on the right and if the Catalan numbers as initial values came out as a special case of the recurrence. – joriki Sep 25 '12 at 09:12
  • Yes, there was a typo

    $\sum_{i=0}^{n-1}\sum_{j=0}^{m}a_{i,j}a_{n-i,m-j} ---> \sum_{i=0}^{n-1}\sum_{j=0}^{m}a_{i,j}a_{n-1-i,m-j}$

    sorry about that.

     – Juraj Sep 25 '12 at 16:53

0 Answers0