The solution is just zero. orl,I wonder how can you find the problems of China TST? Though I am Chinese,most of the China TST problems I can't find. Please tell me the way that you find the problems.

suweijie wrote: The solution is just zero. orl,I wonder how can you find the problems of China TST? Though I am Chinese,most of the China TST problems I can't find. Please tell me the way that you find the problems. You can go to visit the old site of mathfan http: http://www.mathfan.net

orl wrote: Given positive integers $ k, m, n$ such that $ 1 \leq k \leq m \leq n$. Evaluate \[ \sum^{n}_{i = 0}\frac {1}{n + k + i}\cdot \frac {(m + n + i)!}{i!(n - i)!(m + i)!}.\] Sure that a closed form exists? EDIT: I see that there is a typo in the problem. It should be: Corrected problem. Given integers $ k$, $ m$, $ n$ such that $ 1 \leq k \leq m \leq n$. Show that $ \sum^{n}_{i = 0}\frac {\left( - 1\right)^{i}}{n + k + i}\cdot \frac {(m + n + i)!}{i!(n - i)!(m + i)!} = 0$. Solution. We will use the following fact from the theory of finite differences (this fact can be easily shown by induction over $ n$): Theorem 1. If $ n$ is an integer, and $ P$ is a polynomial of degree $ < n$, then $ \sum_{i = 0}^{n}\left( - 1\right)^{i}\binom{n}{i}P\left(i\right) = 0$. Now, since $ 1\leq k + n - m\leq n$ (in fact, $ 1\leq k + n - m$ follows from $ 1\leq k$ and $ 0\leq n - m$, the latter being a consequence of $ m\leq n$, and $ k + n - m\leq n$ follows from $ k - m\leq 0$, what is because $ k\leq m$), the polynomial $ P$ defined by $ P\left(X\right) = \frac {1}{n!}\cdot\prod_{1\leq i\leq n;\ i\neq k + n - m}\left(X + i + m\right)$ has degree $ < n$ (in fact, its degree is $ n - 1$, since it is the product of the constant factor $ \frac {1}{n!}$ and the $ n - 1$ linear factors $ X + i + m$ for $ i\in\left\{1,2,...,n\right\}\backslash\left\{k + n - m\right\}$). Hence, Theorem 1 yields (1) $ \sum_{i = 0}^{n}\left( - 1\right)^{i}\binom{n}{i}P\left(i\right) = 0$. Now, $ P\left(X\right) = \frac {1}{n!}\cdot\prod_{1\leq i\leq n;\ i\neq k + n - m}\left(X + i + m\right) = \frac {1}{n!}\cdot\frac {\prod_{1\leq i\leq n}\left(X + i + m\right)}{X + \left(k + n - m\right) + m}$ $ = \frac {1}{n!}\cdot\frac {\prod_{1\leq i\leq n}\left(X + i + m\right)}{n + k + X} = \frac {1}{n + k + X}\cdot\frac {\prod_{1\leq i\leq n}\left(X + i + m\right)}{n!}$ $ = \frac {1}{n + k + X}\cdot\frac {\prod_{1\leq i\leq n}\left(X + n + m - \left(n - i\right)\right)}{n!}$ $ = \frac {1}{n + k + X}\cdot\frac {\prod_{0\leq i\leq n - 1}\left(X + n + m - i\right)}{n!}$ (here we substituted $ n - i$ for $ i$ in the product) $ = \frac {1}{n + k + X}\cdot\binom{X + n + m}{n}$ (since $ \frac {\prod_{0\leq i\leq n - 1}\left(X + n + m - i\right)}{n!} = \binom{X + n + m}{n}$). Thus, (1) becomes $ \sum_{i = 0}^{n}\left( - 1\right)^{i}\binom{n}{i}\cdot\frac {1}{n + k + i}\cdot\binom{i + n + m}{n} = 0$. Hence, $ 0 = \sum_{i = 0}^{n}\left( - 1\right)^{i}\binom{n}{i}\cdot\frac {1}{n + k + i}\cdot\binom{i + n + m}{n}$ $ = \sum_{i = 0}^{n}\left( - 1\right)^{i}\cdot\frac {n!}{i!\left(n - i\right)!}\cdot\frac {1}{n + k + i}\cdot\frac {\left(i + n + m\right)!}{n!\left(\left(i + n + m\right) - n\right)!}$ $ = \sum_{i = 0}^{n}\left( - 1\right)^{i}\cdot\frac {n!}{i!\left(n - i\right)!}\cdot\frac {1}{n + k + i}\cdot\frac {\left(m + n + i\right)!}{n!\left(m + i\right)!}$ $ = \sum_{i = 0}^{n}\frac {\left( - 1\right)^{i}}{n + k + i}\cdot\frac {\left(m + n + i\right)!}{i!\left(n - i\right)!\left(m + i\right)!}$, and the problem is solved. PS. @Orl: The transformation $ n\mapsto n!$ called factorial, not faculty. Darij

We have: $\displaystyle S_{n,m,k}=\sum_{i=0}^n\dfrac{(-1)^i}{n+k+i}\cdot\dfrac{(m+n+i)!}{i!(n-i)!(m+i)!}=$ $=\sum_{i=0}^n\dfrac{(-1)^i(m+n+i)...(n+k+i+1). (n+k+i-1)!}{i!(n-i)!(m+i)...(k+i+1).(k+i)!}$ $\displaystyle\quad =\sum_{i=0}^n\dfrac{(m+n+i)^{\underline{m-k}}}{(m+i)^{\underline{m-k}}}\cdot \dfrac{(-1)^i{n\choose i}{n+k+i-1\choose n-1}}{n}$ *Note: $(x)^{\underline{n}}=x(x-1)...(x-n+1)$ Now, We caculate differences $\Delta\left[\dfrac{(m+n+i)^{\underline{m-k}}}{(m+i)^{\underline{m-k}}}\right]=\dfrac{(n+k+i+2)...(m+n+i+1)}{(k+i+2)...(m+i+1)}-\dfrac{(n+k+i+1)...(m+n+i)}{(k+i+1)...(m+i)}$ $\quad =n(k-m)\cdot\dfrac{(m+n+i)^{\underline{m-k-1}}}{(m+i+1)^{\underline{m-k+1}}}$ and $\Delta\left[(-1)^{i-1}.{n-1\choose i-1}{n+k+i-1\choose n}\right]=\dfrac{n+k}{n}(-1)^i.{n\choose i} {n+k+i-1\choose n-1}$ Therefor by Summation by parts, we have: $\displaystyle S_{n,m,k}=\dfrac{1}{n+k}\sum_{i=0}^n \dfrac{(m+n+i)^{\underline{m-k}}}{(m+i)^{\underline{m-k}}}\Delta\left[(-1)^{i-1}.{n-1\choose i-1}{n+k+i-1\choose n}\right]$ $\displaystyle = \dfrac{1}{n+k}\left.\left[\dfrac{(m+n+i)^{\underline{m-k}}}{(m+i)^{\underline{m-k}}}\cdot (-1)^{i-1}.{n-1\choose i-1}{n+k+i-1\choose n}\right]\right|_{i=0}^{n+1}$ $\quad +\dfrac{n(m-k)}{n+k}\sum_{i=0}^n (-1)^{i}.{n-1\choose i}{n+k+i\choose n} \cdot\dfrac{(m+n+i)^{\underline{m-k-1}}}{(m+i+1)^{\underline{m-k+1}}}$ $\displaystyle =\dfrac{(m-k)}{n+k}\sum_{i=0}^{n-1} \dfrac{(-1)^i(m+n+i)!}{(n+k+i+1) i!(n-1-i)!(m+i+1)!}$ $\Rightarrow S_{n,m,k}=\dfrac{m-k}{n+k}S_{n-1,m+1,k+2}=\dfrac{m-k}{n+k}\cdot\dfrac{m-k-1}{n+k+1}S_{n-2,m+2,k+4}=...=$ $=\dfrac{(m-k)(m-k-1)...(m-k-n+1)}{(n+k)(n+k+1)...(2n+k-1)}S_{0,m+n,k+2n}$ inside $S_{0,m+n,k+2n}=\dfrac{(-1)^0 (m+n+0+0)!}{(0+k+2n+0) 0!(0-0)!(m+n+0)!}=\dfrac{1}{2n+k}$ Result: $\boxed{\displaystyle\sum_{i=0}^n\dfrac{(-1)^i}{n+k+i}\cdot\dfrac{(m+n+i)!}{i!(n-i)!(m+i)!}=\dfrac{(m-k)^{\underline{n}}}{(n+k)_{n+1}}}$ *Note: *Pochhammer symbol*: $(x)_n=x(x+1)...(x+n-1)$

Here's a *very* different (and possibly overkill) solution using calculus. We have \begin{align*} \sum_{i=0}^n\frac{(-1)^i}{n+k+i}\cdot\frac{(m+n+i)!}{i!(n-i)!(m+i)!} &= \sum_{i=0}^n\frac{(-1)^i(m+n+i)!}{i!(n-i)!(m+i)!}\int_0^1x^{n+k+i-1}\;dx \\ &= \int_0^1\left[\sum_{i=0}^n\binom{n}i\binom{m+n+i}n(-1)^ix^i\right]x^{n+k-1}\;dx \\ &= \int_0^1\left[\sum_{i=0}^n\binom{n}i(-1)^ix^i\cdot\frac1{n!}\frac{\partial^n}{\partial y^n}y^{m+n+i}\biggr\rvert_{y=1}\right]x^{n+k-1}\;dx \\ &= \frac1{n!}\frac{\partial^n}{\partial y^n}\left[\int_0^1\sum_{i=0}^n\binom{n}i(-1)^ix^{n+k+i-1}y^{m+n+i}\;dx\right]_{y=1} \\ &= \frac1{n!}\frac{\partial^n}{\partial y^n}\left[\int_0^1x^{n+k-1}y^{m+n}(1-xy)^n\;dx\right]_{y=1} \\ &= \frac1{n!}\frac{\partial^n}{\partial y^n}\left[y^{m-k}\int_0^yu^{n+k-1}(1-u)^n\;du\right]_{y=1} \\ &= \frac1{n!}\sum_{j=0}^n\binom{n}j\left[\frac{\partial^j}{\partial y^j}y^{m-k}\right]_{y=1}\left[\frac{\partial^{n-j}}{\partial y^{n-j}}\int_0^yu^{n+k-1}(1-u)^n\;du\right]_{y=1} \end{align*}Now if $j < n$, the second factor (due to the Fundamental Theorem of Calculus) is $$\left[\frac{\partial^{n-j-1}}{\partial y^{n-j-1}}y^{n+k-1}(1-y)^n\right]_{y=1}$$which is zero because we are differentiating at most $n-1$ times, and there is a zero of order $n$ at $y=1$. And if $j=n$, the first factor is zero because $m-k < m \le n$. So all the terms of the sum vanish, and thus the sum is zero. $\blacksquare$

darij grinberg wrote: orl wrote: Given positive integers $ k, m, n$ such that $ 1 \leq k \leq m \leq n$. Evaluate \[ \sum^{n}_{i = 0}\frac {1}{n + k + i}\cdot \frac {(m + n + i)!}{i!(n - i)!(m + i)!}.\] Sure that a closed form exists? EDIT: I see that there is a typo in the problem. It should be: Corrected problem. Given integers $ k$, $ m$, $ n$ such that $ 1 \leq k \leq m \leq n$. Show that $ \sum^{n}_{i = 0}\frac {\left( - 1\right)^{i}}{n + k + i}\cdot \frac {(m + n + i)!}{i!(n - i)!(m + i)!} = 0$. Solution. We will use the following fact from the theory of finite differences (this fact can be easily shown by induction over $ n$): Theorem 1. If $ n$ is an integer, and $ P$ is a polynomial of degree $ < n$, then $ \sum_{i = 0}^{n}\left( - 1\right)^{i}\binom{n}{i}P\left(i\right) = 0$. Now, since $ 1\leq k + n - m\leq n$ (in fact, $ 1\leq k + n - m$ follows from $ 1\leq k$ and $ 0\leq n - m$, the latter being a consequence of $ m\leq n$, and $ k + n - m\leq n$ follows from $ k - m\leq 0$, what is because $ k\leq m$), the polynomial $ P$ defined by $ P\left(X\right) = \frac {1}{n!}\cdot\prod_{1\leq i\leq n;\ i\neq k + n - m}\left(X + i + m\right)$ has degree $ < n$ (in fact, its degree is $ n - 1$, since it is the product of the constant factor $ \frac {1}{n!}$ and the $ n - 1$ linear factors $ X + i + m$ for $ i\in\left\{1,2,...,n\right\}\backslash\left\{k + n - m\right\}$). Hence, Theorem 1 yields (1) $ \sum_{i = 0}^{n}\left( - 1\right)^{i}\binom{n}{i}P\left(i\right) = 0$. Now, $ P\left(X\right) = \frac {1}{n!}\cdot\prod_{1\leq i\leq n;\ i\neq k + n - m}\left(X + i + m\right) = \frac {1}{n!}\cdot\frac {\prod_{1\leq i\leq n}\left(X + i + m\right)}{X + \left(k + n - m\right) + m}$ $ = \frac {1}{n!}\cdot\frac {\prod_{1\leq i\leq n}\left(X + i + m\right)}{n + k + X} = \frac {1}{n + k + X}\cdot\frac {\prod_{1\leq i\leq n}\left(X + i + m\right)}{n!}$ $ = \frac {1}{n + k + X}\cdot\frac {\prod_{1\leq i\leq n}\left(X + n + m - \left(n - i\right)\right)}{n!}$ $ = \frac {1}{n + k + X}\cdot\frac {\prod_{0\leq i\leq n - 1}\left(X + n + m - i\right)}{n!}$ (here we substituted $ n - i$ for $ i$ in the product) $ = \frac {1}{n + k + X}\cdot\binom{X + n + m}{n}$ (since $ \frac {\prod_{0\leq i\leq n - 1}\left(X + n + m - i\right)}{n!} = \binom{X + n + m}{n}$). Thus, (1) becomes $ \sum_{i = 0}^{n}\left( - 1\right)^{i}\binom{n}{i}\cdot\frac {1}{n + k + i}\cdot\binom{i + n + m}{n} = 0$. Hence, $ 0 = \sum_{i = 0}^{n}\left( - 1\right)^{i}\binom{n}{i}\cdot\frac {1}{n + k + i}\cdot\binom{i + n + m}{n}$ $ = \sum_{i = 0}^{n}\left( - 1\right)^{i}\cdot\frac {n!}{i!\left(n - i\right)!}\cdot\frac {1}{n + k + i}\cdot\frac {\left(i + n + m\right)!}{n!\left(\left(i + n + m\right) - n\right)!}$ $ = \sum_{i = 0}^{n}\left( - 1\right)^{i}\cdot\frac {n!}{i!\left(n - i\right)!}\cdot\frac {1}{n + k + i}\cdot\frac {\left(m + n + i\right)!}{n!\left(m + i\right)!}$ $ = \sum_{i = 0}^{n}\frac {\left( - 1\right)^{i}}{n + k + i}\cdot\frac {\left(m + n + i\right)!}{i!\left(n - i\right)!\left(m + i\right)!}$, and the problem is solved. PS. @Orl: The transformation $ n\mapsto n!$ called factorial, not faculty. Darij Can you please share the motivation or thought process of finding the specific polynomial P(X)?