# A partial recurrence equation

What is the closed form solution to the following partial recurrence relation? $$q(n,m) = \frac{q(n-1,m-1)}{n} - q(n-1,m)$$ where $q(0,m)=0$ for all $m > 0$ and $q(n,0) = (-1)^n$ for all $n \geq 0$. We make the assumption that $q(n,m) = 0$ if any index is negative. What methods are involved in finding a closed form solution?

-
This function needs a base case for $q(1,0)$. There's no unique way to get more values out of it as is. –  Kevin Carlson Aug 28 '12 at 5:07
@Kevin: On the not uncommon understanding that $q(n,m)=0$ when at least one index is negative, $q(n,0)=0$ for $n>0$. Failing some such assumption, you need $q(n,0)$ for all $n>0$. –  Brian M. Scott Aug 28 '12 at 5:15
Thanks, @BrianM.Scott. –  Kevin Carlson Aug 28 '12 at 5:16
Thanks Kevin and Brian. I should have been more clear. As Brian suggests, I'm assuming that $q(n,m) = 0$ if any index is negative. However, this makes $q(n,0) = (-1)^n$ for all $n > 0$. I've added this to the question just to make it clear. –  Robby McKilliam Aug 28 '12 at 5:46

It is a good idea to clean things up a bit first. Your recurrence can be rid of denominators and negative numbers by putting $$q'(n,m)=(-1)^{n-m}n!\,q(n,m)$$ for which the recurrence becomes $$q'(n,m)=q'(n-1,m-1)+nq'(n-1,m)\quad\text{for }n,m>0$$ with initial values $$q'(n,0)=n!\qquad\text{and}\qquad q'(0,m)=0^m\qquad\text{for }n,m\geq0.$$ Now by inspection of the recurrence or by computing a few values one sees that $$q'(n,m)=\genfrac[]0{}{n+1}{m+1},\qquad\text{for }n,m\geq0$$ where the RHS denotes an unsigned Stirling number of the first kind. Your original equation then has as solution $$q(n,m)=\frac{(-1)^{n-m}}{n!}\genfrac[]0{}{n+1}{m+1},$$ involving the signed version of the Stirling numbers of the first kind.

-
I see. It appears that computing the Stirling numbers involves a recursion. So, in some sense, there isn't a closed form solution at all! –  Robby McKilliam Aug 28 '12 at 7:28
@RobbyMcKilliam: Indeed, but at least we find ourselves in good company not having found a "closed" form (say one involving polynomial expressions, factorials, without varying length summations or products). –  Marc van Leeuwen Aug 28 '12 at 8:26

It also turns out that these numbers are very closely related to the coefficients of the Chebyshev polynomials of the first kind, though I discovered this empirically and only then proved it.

Here’s a table of the first few values of $q(n,m)$:

$$\begin{array}{c|r|r} n\backslash m&0&1&2&3&4&5&6\\ \hline 0&1&0&0&0&0&0&0\\ 1&-1&1&0&0&0&0&0\\ 2&1&-\frac32&\frac12&0&0&0&0\\ 3&-1&2&-\frac54&\frac14&0&0&0\\ 4&1&-\frac52&\frac94&-\frac78&\frac18&0&0\\ 5&-1&3&-\frac72&2&-\frac9{16}&\frac1{16}&0\\ 6&1&-\frac72&5&-\frac{15}4&\frac{25}{16}&-\frac{11}{32}&\frac1{32} \end{array}$$

And here is $2^{n-1}q(n,m)$:

$$\begin{array}{c|r|r} n\backslash m&0&1&2&3&4&5&6\\ \hline 0&1&0&0&0&0&0&0\\ 1&-1&1&0&0&0&0&0\\ 2&2&-3&1&0&0&0&0\\ 3&-4&8&-5&1&0&0&0\\ 4&8&-20&18&-7&1&0&0\\ 5&-16&48&-56&32&-9&1&0\\ 6&32&-112&160&-120&50&-11&1 \end{array}$$

Now $a(n,m)=2^{n-m-1}q(n-m,m)$:

$$\begin{array}{c|r|r} n\backslash m&0&1&2&3&4\\ \hline 0&1&0&0&0&0\\ 1&-1&0&0&0&0\\ 2&2&1&0&0&0\\ 3&-4&-3&0&0&0\\ 4&8&8&1&0&0&\\ 5&-16&-20&-5&0&0\\ 6&32&48&18&1&0\\ 7&-64&-112&-56&-7&0\\ 8&128&256&160&32&1\\ 9&-256&-576&-432&-120&-9 \end{array}$$

Compare these values with the coefficients of the Chebyshev polynomials of the first kind; it appears that

$$T_n(x)=\sum_{k=0}^{\lfloor n/2\rfloor}(-1)^{n+k}a(n,k)x^{n-2k}\;.$$

To verify this, let $$S_n(x)=\sum_{k=0}^{\lfloor n/2\rfloor}(-1)^{n+k}a(n,k)x^{n-2k}\;.$$

The Chebyshev polynomials of the first kind are given by the recurrence \begin{align*}&T_0(x)=1\\&T_1(x)=x\\&T_{n+1}(x)=2xT_n(x)-T_{n-1}(x),\quad n>1\;.\end{align*}

Now

\begin{align*} a(n+1,k)&=2^{n-k}q(n+1-k,k)\\\\ &=2^{n-k}\left(\frac12q(n-k,k-1)-q(n-k,k)\right)\\\\ &=2^{n-k-1}q(n-k,k-1)-2^{n-k}q(n-k,k)\\\\ &=a(n-1,k-1)-2a(n,k)\;, \end{align*}

so

\begin{align*} S_{n+1}(x)&=\sum_{k=0}^{\lfloor(n+1)/2\rfloor}(-1)^{n+1+k}a(n+1,k)x^{n+1-2k}\\ &=\sum_{k=0}^{\lfloor(n+1)/2\rfloor}(-1)^{n+1+k}\Big(a(n-1,k-1)-2a(n,k)\Big)x^{n+1-2k}\\ &=\sum_{k=0}^{\lfloor(n+1)/2\rfloor}(-1)^{n+1+k}a(n-1,k-1)x^{n+1-2k}+2x\sum_{k=0}^{\lfloor(n+1)/2\rfloor}(-1)^{n+k}a(n,k)x^{n-2k}\\ &=\sum_{k=0}^{\lfloor(n+1)/2\rfloor}(-1)^{n-1+k}a(n-1,k)x^{n-1-2k}+2x\sum_{k=0}^{\lfloor(n+1)/2\rfloor}(-1)^{n+k}a(n,k)x^{n-2k}\\ &=S_{n-1}(x)+2xS_n(x)\;. \end{align*}

Clearly $S_0(x)=1$ and $S_1(x)=x$, so $S_n(x)=T_n(x)$ for $n\ge 0$. Thus, any expression for the coefficients of $T_n(x)$ gives an expression for the $q(n,m)$ via the transformation $$q(n,m)=2^{1-n}a(n+m,m)\;.$$

-
Interesting! I guess this connection with the Chebyshev polynomials is likely to be linked with Marc's solution using the Stirling numbers. –  Robby McKilliam Aug 28 '12 at 9:39