4

I got this question in a maths contest archive and I am completely clueless over how to start.

$$\sum_{m=0}^q(n-m){(p+m)!\over m!}= {(p+q+1)! \over q!}\left(\frac{ n}{ p+1}-\frac {q}{p+2}\right)$$

I thought of transforming $\frac{(p+m)!}{m!}$ into $p+m\choose m$ by multiplying and dividing by $p!$ but that was surely a bad idea or maybe I couldn't figure it out right.

Harsh Sharma
  • 2,369

3 Answers3

2

Let's try induction on $q$.

Base Case: $q=0$, so our statement is: $$(n-0)\frac{(p+0)}{0!}=\frac{(p+0+1)!}{0!}\left(\frac{n}{p+1}-\frac{0}{p+2}\right)$$ The left-side is clearly $n \cdot p!$ while the right side is $(p+1)!\left(\frac{n}{p+1}\right)=n\cdot p!$, so the above is true.

Induction Case: Assume: $$\sum_{m=0}^q(n-m){(p+m)!\over m!}= {(p+q+1)! \over q!}\left(\frac{ n}{ p+1}-\frac {q}{p+2}\right)$$ Now, add the term for $q+1$ to both sides: $$\sum_{m=0}^{q+1}(n-m){(p+m)!\over m!}= {(p+q+1)! \over q!}\left(\frac{ n}{ p+1}-\frac {q}{p+2}\right)+(n-q-1)\frac{(p+q+1)!}{(q+1)!}$$ Now, I think it might be useful to seprate the $n$ terms from the $q$ terms, so I'm going to do distribute a little: $$\sum_{m=0}^{q+1}(n-m){(p+m)!\over m!}= \\ {(p+q+1)! \over q!}\frac{ n}{ p+1}-{(p+q+1)! \over q!}\frac {q}{p+2}+n\frac{(p+q+1)!}{(q+1)!}-(q+1)\frac{(p+q+1)!}{(q+1)!}$$ And then rearrange the terms: $$\sum_{m=0}^{q+1}(n-m){(p+m)!\over m!}= \\ {(p+q+1)! \over q!}\frac{ n}{ p+1}+n\frac{(p+q+1)!}{(q+1)!}-\left((q+1)\frac{(p+q+1)!}{(q+1)!}+{(p+q+1)! \over q!}\frac {q}{p+2}\right)$$ Now, I'm going to change each term a little so it will be easier to factor: $$\sum_{m=0}^{q+1}(n-m){(p+m)!\over m!}= \\ {n(p+q+1)! \over q!}\frac{1}{ p+1}+\frac{n(p+q+1)!}{q!}\frac{1}{q+1}-\left(\frac{(p+q+1)!}{q!}+{(p+q+1)! \over q!}\frac {q}{p+2}\right)$$ Now, I'm going to change each term a little so it will be easier to add like terms: $$\sum_{m=0}^{q+1}(n-m){(p+m)!\over m!}= \\ {n(p+q+1)! \over q!}\frac{q+1}{(p+1)(q+1)}+\frac{n(p+q+1)!}{q!}\frac{p+1}{(p+1)(q+1)}-\left(\frac{(p+q+1)!}{q!}\frac{p+2}{p+2}+{(p+q+1)! \over q!}\frac {q}{p+2}\right)$$ Factor and add like terms: $$\sum_{m=0}^{q+1}(n-m){(p+m)!\over m!}={n(p+q+1)! \over q!}\frac{p+q+2}{(p+1)(q+1)}-\frac{(p+q+1)!}{q!}\frac{p+q+2}{p+2}$$ Combine products to create bigger factorials: $$\sum_{m=0}^{q+1}(n-m){(p+m)!\over m!}={n(p+q+2)! \over (q+1)!}\frac{1}{p+1}-\frac{(p+q+2)!}{q!}\frac{1}{p+2}$$ Change the terms a little to make it easier to factor: $$\sum_{m=0}^{q+1}(n-m){(p+m)!\over m!}={(p+q+2)! \over (q+1)!}\frac{n}{p+1}-\frac{(p+q+2)!}{(q+1)!}\frac{q}{p+2}$$ Finally, factor: $$\sum_{m=0}^{q+1}(n-m){(p+m)!\over m!}={(p+q+2)! \over (q+1)!}\left(\frac{n}{p+1}-\frac{q}{p+2}\right)$$ Thus, we have proven that the statement for $q$ implies the statement for $q+1$, concluding the induction step.

Noble Mushtak
  • 18,402
  • 28
  • 44
1

For $q=0$ you have only the term $m=0$,$n\frac{p!}{0!}=n p!$ on the left side of the equation. On the right side you have $\frac{(p+1)!}{0!}\frac{n}{p+1}$. Noting that $(p+1)!=p!(p+1)$ you get the left hand side term. We now prove by induction. We assume that the given equation is valid for $q$, and we want to prove that is valid for $q+1$. $$\sum_{m=0}^{q+1}(n-m)\frac{(p+m)!}{m!}=\sum_{m=0}^{q}(n-m)\frac{(p+m)!}{m!}+(n-q-1)\frac{(p+q+1)!}{(q+1)!} = \frac{(p+q+1)!}{q!}\left(\frac{n}{p+1}-\frac{q}{p+2}\right)+(n-q-1)\frac{(p+q+1)!}{(q+1)!}=\frac{(p+q+1)!}{(q+1)!}\left(\frac{n(q+1)}{p+1}-\frac{q(q+1)}{p+2}+(n-q-1)\right)=\frac{(p+q+1)!}{(q+1)!}\left(\frac{n(q+1)+n(p+1)}{p+1}-\frac{q(q+1)+(p+2)(q+1)}{p+2}\right)=\frac{(p+q+2)!}{(q+1)!}\left(\frac{n}{p+1}-\frac{q+1}{p+2}\right)$$ Which is exactly what we wanted to show

Andrei
  • 37,370
1

$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} &\color{#f00}{\sum_{m = 0}^{q}\pars{n - m}{\pars{p + m}! \over m!}} = p!\sum_{m = -\infty}^{q}\pars{n - m}{p + m \choose m} = p!\sum_{m = -q}^{\infty}\pars{n + m}{p - m \choose -m} = \\[3mm] = &\ p!\sum_{m = 0}^{\infty}\pars{n + m - q}{p - m + q \choose -m + q} = p!\sum_{m = 0}^{\infty}\pars{n + m - q}{-p - 1 \choose -m + q}\pars{-1}^{-m + q} \\[3mm] = &\ \pars{-1}^{q}\,p!\lim_{x \to 1^{-}}\pars{n - q + x\,\partiald{}{x}} \underbrace{\sum_{m = 0}^{\infty}{-p - 1 \choose -m + q}\pars{-x}^{m}} _{\ds{\equiv\ \mathcal{I}\pars{x}}}\,,\ \qquad\verts{x} < 1\tag{1} \end{align}

\begin{align} \mathcal{I}\pars{x} & = \sum_{m = 0}^{\infty}\pars{-x}^{m}\oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{-p - 1} \over z^{-m + q + 1}}\,{\dd z \over 2\pi\ic} = \oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{-p - 1} \over z^{q + 1}}\sum_{m = 0}^{\infty}\pars{-xz}^{m} \,{\dd z \over 2\pi\ic} \\[3mm] & = \oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{-p - 1} \over z^{q + 1}\pars{1 + xz}} \,{\dd z \over 2\pi\ic} \\[8mm] \mathcal{I}\pars{x \to 1^{-}} & = \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{-p - 2} \over z^{q + 1}} \,{\dd z \over 2\pi\ic} = {-p - 2 \choose q} = {p + 2 + q - 1 \choose q}\pars{-1}^{q} \\[3mm] & = {p + q + 1 \choose q}\pars{-1}^{q}\tag{2} \\[8mm] \mathcal{I}'\pars{x \to 1^{-}} & = -\oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{-p - 3} \over z^{q}} \,{\dd z \over 2\pi\ic} = -{-p - 3 \choose q - 1} = -{p + 3 + q - 1 - 1 \choose q - 1}\pars{-1}^{q - 1} \\[3mm] & = {p + q + 1 \choose q - 1}\pars{-1}^{q}\tag{3} \end{align}
The next step is to replace $\pars{2}$ and $\pars{3}$ in $\pars{1}$: \begin{align} &\color{#f00}{\sum_{m = 0}^{q}\pars{n - m}{\pars{p + m}! \over m!}} = p!\bracks{\pars{n - q}{p + q + 1 \choose q} + {p + q + 1 \choose q - 1}} \\[3mm] = &\ p!\bracks{\pars{n - q}{\pars{p + q + 1}! \over q!\pars{p + 1}!} + {\pars{p + q + 1}! \over \pars{q - 1}!\pars{p + 2}!}} \\[3mm] = &\ {\pars{p + q + 1}! \over q!}\bracks{\pars{n - q}{1 \over p + 1} + {q \over \pars{p + 2}\pars{p + 1}}} \\[3mm] = &\ {\pars{p + q + 1}! \over q!}\bracks{\pars{n - q}{1 \over p + 1} + q\pars{{1 \over p + 1} - {1 \over p + 2}}} \\[3mm] = &\ \color{#f00}{% {\pars{p + q + 1}! \over q!}\pars{{n \over p +1} - {q \over p + 2}}} \end{align}
Felix Marin
  • 89,464