Peter wrote: Define \[ \begin{cases}d(n, 0)=d(n, n)=1&(n \ge 0),\\ md(n, m)=md(n-1, m)+(2n-m)d(n-1,m-1)&(0<m<n).\end{cases}\] Prove that $ d(n, m)$ are integers for all $ m, n \in \mathbb{N}$. Very easy: First we are going to prove the identity (1) $ m\binom{n}{m}^{2}=m\binom{n-1}{m}^{2}+\left(2n-m\right)\binom{n-1}{m-1}^{2}$ for any integer $ n$ and any positive integer $ m$. In fact, for $ n=0$, proving (1) is easy (exercise to the reader), while for $ n\neq 0$, we have $ \binom{n-1}{m}=\frac{\left(n-1\right)\left(n-2\right)...\left(n-m+1\right)\left(n-m\right)}{m!}=\frac{n-m}{n}\cdot\frac{n\left(n-1\right)\left(n-2\right)...\left(n-m+1\right)}{m!}$ $ =\frac{n-m}{n}\cdot\binom{n}{m}$ and $ \binom{n-1}{m-1}=\frac{\left(n-1\right)\left(n-2\right)...\left(n-m+1\right)}{\left(m-1\right)!}=\frac{m}{n}\cdot\frac{n\left(n-1\right)\left(n-2\right)...\left(n-m+1\right)}{m\cdot\left(m-1\right)!}$ $ =\frac{m}{n}\cdot\frac{n\left(n-1\right)\left(n-2\right)...\left(n-m+1\right)}{m!}=\frac{m}{n}\cdot\binom{n}{m}$, so that $ m\binom{n-1}{m}^{2}+\left(2n-m\right)\binom{n-1}{m-1}^{2}=m\left(\frac{n-m}{n}\cdot\binom{n}{m}\right)^{2}+\left(2n-m\right)\left(\frac{m}{n}\cdot\binom{n}{m}\right)^{2}$ $ =\left(m\left(\frac{n-m}{n}\right)^{2}+\left(2n-m\right)\cdot\left(\frac{m}{n}\right)^{2}\right)\cdot\binom{n}{m}^{2}=m\cdot\binom{n}{m}^{2}$, and (1) is proved. The rest of the solution is trivial, but formally explaining it is some work. We claim that (2) $ d\left(n,m\right)=\binom{n}{m}^{2}$ for any nonnegative integers $ n$ and $ m$ satisfying $ m\leq n$. Of course, (2) immediately will yield that $ d\left(n,m\right)$ is integer for any nonnegative integers $ n$ and $ m$ satisfying $ m\leq n$. Thus, in order to solve the problem, it is enough to prove (2). We will prove (2) by induction over $ n$: The induction base, $ n=0$, is trivial (in fact, if we have $ n=0$, then $ m\leq n$ becomes $ m\leq 0$, so that $ m=0$ (because $ m$ must be nonnegative), so that $ d\left(n,m\right)=d\left(0,0\right)=1=1^{2}=\binom{0}{0}^{2}=\binom{n}{m}^{2}$). The induction step is straightforward, but long to write up: Let $ u$ be a positive integer. Assume that (2) is proven for all nonnegative integers $ n$ and $ m$ satisfying $ m\leq n$ and $ n<u$. We want to show that (2) also holds for all nonnegative integers $ n$ and $ m$ satisfying $ m\leq n$ and $ n=u$. In fact, let $ n$ and $ m$ be nonnegative integers satisfying $ m\leq n$ and $ n=u$. Then, $ n-1<u$. Since $ m$ is nonnegative and satisfies $ m\leq n$, one of the three cases $ m=0$, $ m=n$ and $ 0<m<n$ must hold. We distinguish between these three cases: First case. Assume that $ m=0$. Then, $ d\left(n,m\right)=d\left(n,0\right)=1=1^{2}=\binom{n}{0}^{2}=\binom{n}{m}^{2}$. Second case. Assume that $ m=n$. Then, $ d\left(n,m\right)=d\left(n,n\right)=1=1^{2}=\binom{n}{n}^{2}=\binom{n}{m}^{2}$. Third case. Assume that $ 0<m<n$. Then, $ n-1$ and $ m$ are nonnegative integers satisfying $ m\leq n-1$ and $ n-1<u$, so that, by the induction assumption, these integers satisfy (2), i. e. we have $ d\left(n-1,m\right)=\binom{n-1}{m}^{2}$. Also, $ n-1$ and $ m-1$ are nonnegative integers satisfying $ m-1\leq n-1$ and $ n-1<u$, so that, by the induction assumption, these integers satisfy (2), i. e. we have $ d\left(n-1,m-1\right)=\binom{n-1}{m-1}^{2}$. Finally, since $ 0<m<n$, we have $ md\left(n,m\right)=md\left(n-1,m\right)+\left(2n-m\right)d\left(n-1,m-1\right)$, so that $ md\left(n,m\right)=m\binom{n-1}{m}^{2}+\left(2n-m\right)\binom{n-1}{m-1}^{2}$. Comparing this with (1), we get $ md\left(n,m\right)=m\binom{n}{m}^{2}$, so that $ d\left(n,m\right)=\binom{n}{m}^{2}$ (since $ m>0$). Thus, in all three cases, we get $ d\left(n,m\right)=\binom{n}{m}^{2}$, so that (2) holds for our two integers $ n$ and $ m$. Hence, the induction step is complete, and (2) is proven. As said above, this solves the problem. Darij