Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer
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*}$$


$$\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*}$$


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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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