Recurrence relation involving unknown d(n, m) numbers

Question

Problem goes like this: numbers $d(n, m)$, where $n, m$ are integers and $0\le m \le n$ are defined by:$$d(n, 0) = d(n, n) = 1$$ for all $n\ge 0$ and$$m\cdot d(n, m) = m\cdot d(n-1, m) + (2n-m)\cdot d(n-1, m-1)$$ for $0\lt m \lt n$. Prove that all the $d(n, m)$ are integers. Now this statement reminds me of some combinatorial identities, where the $d(n, m)$ can be considered, for example, the number of ways to distribute or arrange $m+n$ objects in a specific way. Since I don't know what these numbers represent from a combinatorial point of view, I can't prove the identity, but if it turns out that I guess what they represent, proving it should be easy enough. Problem is I struggle to find out what they can relate to. Am I in the right way or is there a completely different approach to solve it? I tried to expand $d(n, m)$ using its definition and it looks like binomial coefficients make their appearance.

Answer 1

A good start would be to tabulate some small values. Here is some python code to do that:

>>> def tab(n):
...   r = [[0]*(n+1) for _ in range(n+1)]
...   for i in range(n+1):
...     r[i][i], r[i][0] = 1, 1
...   for i in range(1, n+1):
...     for j in range(1, i):
...       r[i][j] = r[i-1][j]+(2*i-j)*r[i-1][j-1]//j
...   for i in range(n+1):
...     print('\t'.join(map(str, r[i])))
... 
>>> tab(6)
1   0   0   0   0   0   0   
1   1   0   0   0   0   0
1   4   1   0   0   0   0
1   9   9   1   0   0   0
1   16  36  16  1   0   0
1   25  100 100 25  1   0
1   36  225 400 225 36  1

If you're familiar with them, you'll pretty quickly recognize these as the squares of the Pascal's triangle. Hence, we hypothesize that $d(n, m) = \binom{n}{m}^2$.

We can show this holds using induction. The boundary conditions $d(n, n)$ and $d(n, 0)$ hold trivially since $1^2 = 1$.

Now take $0 < m < n$, substitute in $d(n-1, m) = \binom{n-1}{m}^2$ and $d(n-1,m-1) = \binom{n-1}{m-1}^2$ and divide the whole equation by $m$. Then:

$$d(n, m) = \binom{n-1}{m}^2 + \frac{2n}{m}\binom{n-1}{m-1}^2 - \binom{n-1}{m-1}^2$$

Recall $\binom{n}{m} = \frac{n}{m}\binom{n-1}{m-1}$, so:

$$d(n, m) = \binom{n-1}{m}^2 + 2\binom{n}{m}\binom{n-1}{m-1} - \binom{n-1}{m-1}^2$$

Expand $\binom{n}{m} = \binom{n-1}{m} + \binom{n-1}{m-1}$ to get:

$$d(n, m) = \binom{n-1}{m}^2 + 2\binom{n-1}{m}\binom{n-1}{m-1} + 2\binom{n-1}{m-1}\binom{n-1}{m-1} - \binom{n-1}{m-1}^2$$

A mess, but we can cancel the last two terms and factor:

$$d(n, m) = \Big(\binom{n-1}{m} + \binom{n-1}{m-1}\Big)^2 = \binom{n}{m}^2$$

Which is our induction hypothesis. So by induction, $d(n, m) = \binom{n}{m}^2$, which certainly is an integer.