# Recurrence relation involving unknown d(n, m) numbers

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.

• Induction is the way to go. – Don Thousand Nov 6 '18 at 19:58
• With 2 variables? Does it mean I should fix one and use induction on the other? – Peanut Nov 6 '18 at 20:00
• That's right. You do two layers of induction – Don Thousand Nov 6 '18 at 20:01
• But how did the proposer derive this formula? I don't think he used induction. – Peanut Nov 6 '18 at 20:04
• I think proving $d(n,m)$ to be an integer is equivalent to showing that $m$ divides $2n \cdot d(n-1,m-1)$. Check if that works – Rakesh Bhatt Dec 24 '18 at 12:11

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.

• The tricky part is always guess something. Once you have an idea of a suitable function, then it's no big deal – Peanut Dec 24 '18 at 12:45