# Derive the recurrence relations

Let $$P_{m,n}=P_{m,n}(x,y)$$ be a polynomial family. Here is some initial terms $$P_{0,0}=1, P_{1,0}=2x, P_{0,1}=2y, P_{1,1}=8xy.$$ I know that the polynomials for any $$m,n \geq 0$$ satisfies the five differential recurrence relations \begin{align} &n \frac{\partial P_{m,n-1}}{\partial x}=m \frac{\partial P_{m-1,n}}{\partial y},\\ & x \frac{\partial P_{m,n}}{\partial x}=m P_{m,n}+m\frac{\partial P_{m-1,n}}{\partial x},\\ & y\frac{\partial P_{m,n}}{\partial x}=m P_{m-1,n+1}+n \,\frac{\partial P_{m,n-1}}{\partial x},\\ & y \frac{\partial P_{m,n}}{\partial y}=n P_{m,n}+n\frac{\partial P_{m,n-1}}{\partial y},\\ & x\frac{\partial P_{m,n}}{\partial y}=n P_{m+1,n-1}+m \,\frac{\partial P_{m-1,n}}{\partial y}. \end{align}

Also, they satisfies the differential equation $$(1-x^2) \frac{\partial^2 P_{m,n}}{\partial x^2} -x y \frac{\partial^2 P_{m,n} }{\partial x \partial y} -(n+3) x \frac{\partial P_{m,n}}{\partial x }+m y \frac{\partial P_{m,n}}{\partial y }+m(m+n+2) P_{m,n}=0,$$ for any $$m,n.$$

I need to eliminate all the derivatives and get pure recurrence relations for $$P_{m,n}$$.

By numeric expеriments I guess such recurrence relations $$2 (1{+}m{+}n) x P_{m,n}=P_{m+1,n}{-}n(n{-}1)P_{m+1,n-2}{+m(m+2n+1)}P_{m-1,n},\\ 2 (1{+}m{+}n) y P_{m,n}=P_{m,n+1}{-}m(m{-}1)P_{m-2,n+1}{+}n(n+2m+1)P_{m,n-1},$$ but I still cant prove it.

Any help?

P.S. There is an exact expression

$$P_{m,n}=m! n! 2^{m+n} \sum_{i=0}^{\frac{m}{2}} \sum_{j=0}^{\frac{n}{2}} (-1)^{i+j}\frac{(m{+}n{-}i{-}j)!}{i! j! (m{-}2i)! (n{-}2j) 2^{2(i+j)}} x^{m-2i} y^{n-2j}.$$

• Are we given that $P_{m,n}(x,y)$ is of the form $x^my^n?$ It seems like it should be. Jun 30, 2020 at 16:40
• @Ross Millikan Yes, In some sence, $P_{m,n}$ is a generalisation of $x^m y^n.$
– Leox
Jun 30, 2020 at 16:50
• Please check your recurrence relations. If $P_{m,n}(x,y)=c_{m,n}x^my^n$ we have $x\frac{\partial P_{m,n}}{\partial x}=mP_{m,n}$ and two terms in the second relation cancel, leaving the third equal to zero. The same thing happens in the fourth one involving $y$. Jun 30, 2020 at 20:08
• @EwanDelanoy: The correct result for $P$ is $$P_{m,n}(x,y)=m! n! \sum_{i=0}^{\lfloor\frac{m}{2}\rfloor} \sum_{j=0}^{\lfloor\frac{n}{2}\rfloor} (-1)^{i+j}\frac{(m+n-i-j)!}{i! j! (m-2i)! (n-2j)!} (2x)^{m-2i} (2y)^{n-2j}.$$ Jul 1, 2020 at 16:34
• @EwanDelanoy: I have verified that this function satisfies all of the relations above. Jul 1, 2020 at 16:44

Your polynomials are crying out to be put into a generating function, $$P = \sum_{m, n \geq 0} P_{m, n} \frac{u^m}{m!} \frac{v^n}{n!}.$$ Working backwards from your explicit formula, set $$N = m+n-i-j$$, $$m' = m-2i, n' = n-2j$$ and do routine simplifications to get \begin{align*} P &= \sum_{N \geq 0} \sum_{(i, j, m', n') \vDash N} \binom{N}{i,j,m',n'} (2x)^{m'} (2y)^{n'} (-u^2)^i (-v^2)^j u^{m'} v^{n'} \\ &= \sum_{N \geq 0} (2xu + 2yv - u^2 - v^2)^N \\ &= \frac{1}{1 + u^2 + v^2 - 2xu - 2yv}. \end{align*} That is, $$P_{m, n} = m! n! [u^m v^n] \frac{1}{1 + u^2 + v^2 - 2xu - 2yv}.$$

Sometimes in practice you'd be able to prove your interpretation satisfies the above generating function formula independently, which would prove the explicit formula by running the preceding argument backwards.

In any case, your initial recurrences can be packaged up into PDE's involving the $$P$$ generating function in a standard way. (See e.g. Wilf's generatingfunctionology for a nice, though unusual, treatment.) For example, $$\frac{\partial}{\partial u} P = \sum_{m, n \geq 0} P_{m+1,n} \frac{u^m}{m!} \frac{v^n}{n!}$$ and $$\frac{\partial}{\partial u} u P = \sum_{m, n \geq 0} (m+1) P_{m, n} \frac{u^m}{m!} \frac{v^n}{n!}.$$

Using these observations, your first recurrence relation, $$n \partial_x P_{m, n-1} = m \partial_y P_{m-1, n},$$ can be repackaged into $$\partial_{uvx} vP = \partial_{uvy} uP.$$ It's of course easy to have a computer verify this holds with the formula above.

Your five differential recurrence relations translate to \begin{align*} \partial_{uvx} vP &= \partial_{uvy} uP \\ x \partial_{xu} P &= \partial_u u (\partial_u + \partial_x) P \\ y \partial_{xuv} P &= \partial_{uv^2} uP + \partial_{xuv} vP \\ y \partial_{vy} P &= \partial_v v (\partial_v + \partial_y) P \\ x \partial_{yuv} P &= \partial_v v \partial_{u^2} P + \partial_u u \partial_y. \end{align*} Your "pure" differential equation translates to $$(1-x^2) \partial_{x^2} P - xy \partial_{xy} P - x \partial_{xv} vP - 2x \partial_x P + uy \partial_{uy} P + u \partial_u (\partial_u u + \partial_v v) P = 0.$$ Your "pure" recurrence relations translate to \begin{align*} 2x (\partial_u u + \partial_v v + 2) \partial_{uv^2} P &= \partial_{u^2 v^2} P - (1+\partial_v v) \partial_{u^2} P + \partial_u u (\partial_u u + 2 \partial_v v + 3) \partial_{v^2} P \\ 2y (\partial_v v + \partial_u u + 2) \partial_{vu^2} P &= \partial_{v^2 u^2} P - (1+\partial_u u) \partial_{v^2} P + \partial_v v (\partial_v v + 2 \partial_u u + 3) \partial_{u^2} P. \end{align*} All 8 of these relations hold for $$P$$ above.

These identities correspond to elements of the annihilator of $$P$$ in the Weyl algebra on 4 variables. These elements are, respectively, \begin{align*} &\partial_{uvx} v - \partial_{uvy} u \\ &x \partial_{xu} - \partial_u u (\partial_u + \partial_x) \\ &y \partial_{xuv} - \partial_{uv^2} u - \partial_{xuv} v \\ &y \partial_{vy} - \partial_v v (\partial_v + \partial_y) \\ &x \partial_{yuv} - \partial_v v \partial_{u^2} - \partial_u u \partial_{yv} \\ &(1-x^2) \partial_{x^2} - xy \partial_{xy} - x \partial_{xv} v - 2x \partial_x + uy \partial_{uy} + u \partial_u (\partial_u u + \partial_v v) \\ &2x (\partial_u u + \partial_v v + 2) \partial_{uv^2} - \partial_{u^2 v^2} + (1+\partial_v v) \partial_v v \partial_{u^2} - \partial_u u (\partial_u u + 2 \partial_v v + 3) \partial_{v^2} \\ &2y (\partial_v v + \partial_u u + 2) \partial_{vu^2} - \partial_{v^2 u^2} + (1+\partial_u u) \partial_u u \partial_{v^2} - \partial_v v (\partial_v v + 2 \partial_u u + 3) \partial_{u^2}. \end{align*}

Your question--how to derive the last two "pure" recurrence relations from the previous six--is equivalent to asking if the last two elements are in the (left) ideal generated by the first six elements. We can check this in Macaulay2:

loadPackage "Dmodules"
W = QQ[x,y,u,v,Dx,Dy,Du,Dv, WeylAlgebra => {x=>Dx, y=>Dy, u=>Du, v=>Dv}]
rP = 1+u^2+v^2-2*x*u-2*y*v
I = RatAnn rP -- the ideal of relations from the explicit formula
J = ideal(Du*Dv*(Dx*v-Dy*u), x*Dx*Du - Du*u*(Du+Dx), y*Dx*Du*Dv-Du*Dv*Dv*u-Dx*Du*Dv*v, y*Dv*Dy-Dv*v*(Dv+Dy), x*Dy*Du*Dv-Dv*v*Du^2-Du*u*Dy*Dv, (1-x^2)*Dx^2-x*y*Dx*Dy-x*Dx*Dv*v-2*x*Dx+u*y*Du*Dy+u*Du*(Du*u+Dv*v))
isSubset(J,I) -- True: first 6 proposed relations hold for explicit formula
isSubset(I,J) -- False: there are more than these 6
f = 2*x*(Du*u+Dv*v+2)*Du*Dv^2-Du^2*Dv^2+(1+Dv*v)*Dv*v*Du^2-Du*u*(Du*u+2*Dv*v+3)*Dv^2
f % J -- 0: 7th relation is implied by first 6!
f // gens J -- write 7th relation in terms of first 6; pages of horrendous mess


This counts as a proof, though we have to trust the computer for the hard part. If you can't prove the geometric series formula directly, you could instead prove the other generators of "I" work in your context and presumably simplify the mess the computer had to do to get the 7th relation from the first 6. This does not seem worthwhile, however.

• thanks, very interesting approach, but, this is only a possible way. Did you do such a check? What was Macaulay2's answer? I dont sure that we have a generanig set for the differential ideal, so the answer can be "No"
– Leox
Jul 7, 2020 at 9:49
• As I said at the bottom, I did have Macaulay2 check that the 7th relation is indeed a consequence of the first 6. (So is the 8th.) This is despite the fact that the full differential ideal of $P$ ("I" in my code) is larger than the one generated by your first 6 [hence, all 8] relations. If you run the code I wrote, it will spit out a generating set for I. It has 10 elements and is not bad. Jul 7, 2020 at 9:58
• Good solution, I trust Macaulay2. Now I have my own short solution but I like yours one.
– Leox
Jul 7, 2020 at 10:25
• For what it's worth, my solution does contain a simple, direct proof of your "pure" recurrence relation starting from the generating function formula or equivalently the explicit formula, without relying on Macaulay2. Namely, translate the recurrence relation to the PDE $2x(\partial_u u + \ldots)$ and have any CAS check the PDE indeed holds. That approach does not use the six auxiliary relations. Jul 7, 2020 at 20:21

My solution.

From the identity $$1=(1-2 (xu+yv)+u^2+v^2)\sum_{m,n=0}^\infty P_{m,n} \frac{u^m}{m!} \frac{v^n}{n!},$$ by equating coefficients to $$0$$ we get that $$$$2(1{+}m) x P_{m,n}{+}2 n y P_{m+1,n{-}1}=P_{m+1,n}{+}m(m{+}1) P_{m-1,n}{+}n(n{-}1) P_{m{+}1,n{-}2} \tag{1}$$$$ By using known differential recurrence relations (and by some shifting indexes if need ) easy to check that the following hods: $$P_{m,n}+x \frac{\partial P_{m,n}}{\partial x}- y \frac{\partial P_{m+1,n{-}1}}{\partial x}=m \frac{\partial P_{m+1,n{-}1}}{\partial x}-(n{-}1) \frac{\partial P_{m+1,n-2}}{\partial x}.$$ Rewrite it in the form $$\frac{\partial }{\partial x}(x P_{m,n}- y P_{m+1,n{-}1}) =\frac{\partial }{\partial x}(mP_{m-1,n}-(n{-}1)P_{m+1,n-2}).$$ Integrate $$x P_{m,n}- y P_{m+1,n{-}1}=mP_{m-1,n}-(n{-}1)P_{m+1,n-2}+C_{m,n}(y),$$ where $$C_{m,n}(y)$$ is some unknown function of one variable $$y.$$

Again differentiate by $$y$$ and by simplification we get that $$\frac{\partial }{\partial y}C_{m,n}(y)=0,$$ thus $$C_{m,n}(y)$$ is a constant $$C_{m,n}.$$ Therefore $$x P_{m,n}- y P_{m+1,n{-}1}=mP_{m-1,n}-(n{-}1)P_{m+1,n-2}+C_{m,n},$$ By puting $$x=y=0$$ we get that $$C_{m,n}=0$$ and $$x P_{m,n}- y P_{m+1,n{-}1}=mP_{m-1,n}-(n{-}1)P_{m+1,n-2}.\tag{2}$$

Now, multiply $$(2)$$ by $$2n$$ and add to $$(1)$$ we get the first recurrence relation.