3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Induction is the way to go. $\endgroup$ – Don Thousand Nov 6 '18 at 19:58
  • $\begingroup$ With 2 variables? Does it mean I should fix one and use induction on the other? $\endgroup$ – Peanut Nov 6 '18 at 20:00
  • $\begingroup$ That's right. You do two layers of induction $\endgroup$ – Don Thousand Nov 6 '18 at 20:01
  • $\begingroup$ But how did the proposer derive this formula? I don't think he used induction. $\endgroup$ – Peanut Nov 6 '18 at 20:04
  • $\begingroup$ 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 $\endgroup$ – Rakesh Bhatt Dec 24 '18 at 12:11
5
+50
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The tricky part is always guess something. Once you have an idea of a suitable function, then it's no big deal $\endgroup$ – Peanut Dec 24 '18 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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