4
$\begingroup$

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?

  • 0
    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.2012-08-28

2 Answers 2

3

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.

  • 0
    @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).2012-08-28
2

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)\;.$

  • 0
    Interesting! I guess this connection with the Chebyshev polynomials is likely to be linked with Marc's solution using the Stirling numbers.2012-08-28