Prove that $\sum_{k=0}^nk{m+k \choose m}=n{m+n+1\choose m+1}-{m+n+1 \choose m+2}$

Question

Can someone please see the work I have so far for the following proof and provide guidance on my inductive step?

Prove that if $m,n\in\mathbb{N}$, then $\sum_{k=0}^nk{m+k \choose m}=n{m+n+1\choose m+1}-{m+n+1 \choose m+2}$

Base Case. Let n=0. Then $\sum_{k=0}^{n=0}k{m+k \choose m}=0$ and $n{m+n+1\choose m+1}-{m+n+1 \choose m+2}=0-0=0$. Thus for $n=0$ our equation is satisfied.

Inductive Step. Let $n\ge0$. Assume $\sum_{k=0}^nk{m+k \choose m}=n{m+n+1\choose m+1}-{m+n+1 \choose m+2}$. Now observe that

$$\begin{align*}\sum_{k=0}^{n+1}k{m+k \choose m}&=\\ \sum_{k=0}^{n}k{m+k \choose m}+(n+1){m+n+1\choose m}&=n{m+n+1\choose m+1}-{m+n+1 \choose m+2}+(n+1){m+n+1\choose m} \end{align*}$$

This is where I'm getting stuck... using Pascal's Identity to combine some of these terms seems ideal. However, the factors of $n$ and $n+1$ are making a clever manipulation difficult for me.

Answer 1

A combinatorial proof is also possible. I have $m+n+1$ white balls numbered $0$ through $m+n$. I’m going to paint $m+2$ of them red, then choose any of the red balls except the one with the highest number and put a gold star on it, and I want to know how many different outcomes are possible.

Suppose that the highest-numbered red ball is ball $m+k$. There are $m+k$ balls with smaller numbers (since I started the numbering at $0$), so there are $\binom{m+k}m$ ways to choose the other $m$ red balls that don’t have the gold star. Once they’ve been chosen, there are $k$ ways to pick one of the remaining balls numbered below $m+k$, paint it red, and slap a gold star on it. Thus, there are $k\binom{m+k}m$ outcomes in which ball $m+k$ is the highest-numbered red ball. Summing over $k$ gives the total number of possible outcomes: it’s

$$\sum_{k=0}^nk\binom{m+k}m\;.$$

But we can count these outcomes in another way. There are $\binom{m+n+1}{m+1}$ ways to choose $m+1$ balls to be the unstarred red balls, and we can then choose any of the remaining $n$ balls to be the starred red ball, so there are

$$n\binom{m+n+1}{m+1}\tag{1}$$

ways to choose a set of $m+2$ balls, paint them red, and put a gold star on one of the balls. However, this includes the outcomes in which the gold star is on the highest-numbered red ball, and we don’t want those. For each possible set of $m+2$ red balls there is exactly one unwanted outcome, the one in which we put the gold star on the highest-numbered red ball, and there are

$$\binom{m+n+1}{m+2}$$

possible sets of red balls, so we need to subtract this from $(1)$ to get the correct count of

$$n\binom{m+n+1}{m+1}-\binom{m+n+1}{m+2}\;.$$

This shows that

$$\sum_{k=0}^nk\binom{m+k}m=n\binom{m+n+1}{m+1}-\binom{m+n+1}{m+2}\;,$$

as desired.

Added: Let me suggest a way to proceed from the point at which you got stuck with your induction argument. First, it’s not too hard to notice that you have both $n\binom{m+n+1}{m+1}$ and $n\binom{m+n+1}m$, which can be combined using Pascal’s identity:

$$\begin{align*} &\sum_{k=0}^nk\binom{m+k}m+(n+1)\binom{m+n+1}m\\ &\qquad=n\binom{m+n+1}{m+1}-\binom{m+n+1}{m+2}+(n+1)\binom{m+n+1}m\\ &\qquad=n\left(\binom{m+n+1}{m+1}+\binom{m+n+1}m\right)+\binom{m+n+1}m-\binom{m+n+1}{m+2}\\ &\qquad=n\binom{m+n+2}{m+1}+\binom{m+n+1}m-\binom{m+n+1}{m+2}\;.\tag{1} \end{align*}$$

You want to show that this is equal to

$$(n+1)\binom{m+n+2}{m+1}-\binom{m+n+2}{m+2}\;.\tag{2}$$

You might try taking the difference and trying to show that it’s $0$. Subtracting $(1)$ from $(2)$, we get

$$\binom{m+n+2}{m+1}-\binom{m+n+2}{m+2}-\binom{m+n+1}m+\binom{m+n+1}{m+2}\;.\tag{3}$$

Pascal’s identity allows us to combine the second and fourth terms:

$$\binom{m+n+2}{m+2}=\binom{m+n+1}{m+2}+\binom{m+n+1}{m+1}\;,$$

so

$$\binom{m+n+1}{m+2}-\binom{m+n+2}{m+2}=-\binom{m+n+1}{m+1}\;,$$

and $(3)$ reduces to

$$\binom{m+n+2}{m+1}-\binom{m+n+1}{m+1}-\binom{m+n+1}m\;,$$

and one more application of Pascal’s identity verifies that this is indeed $0$.

Answer 2

$$\sum_{k=0}^nk{m+k \choose m}=n{m+n+1\choose m+1}-{m+n+1 \choose m+2}$$

Inductive Step. 1: $n\longrightarrow0$

$\sum_{k=0}^{n=0}k{m+k \choose m}=0$ and $n{m+n+1\choose m+1}-{m+n+1 \choose m+2}=0-0=0$.

the equation is satisfied.

Inductive Step. 2: $n\longrightarrow n$

$$\sum_{k=0}^nk{m+k \choose m}=$$ By Pascal's identity: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \Rightarrow \binom{n}{k} - \binom{n-1}{k}= \binom{n-1}{k-1} \Rightarrow \binom{n+1}{k+1} - \binom{n-1+1}{k+1}= \binom{n-1+1}{k-1+1}= $ $\binom{n+1}{k+1} - \binom{n}{k+1}= \binom{n}{k}$ $$\sum_{k=0}^nk\left[\binom{m+k+1}{m+1}-\binom{m+k}{m+1}\right]=$$ $$\sum_{k=0}^nk\binom{m+k+1}{m+1}-\sum_{k=0}^nk\binom{m+k}{m+1}=$$ $$n\binom{m+n+1}{m+1}+\sum_{k=0}^{n-1}k\binom{m+k+1}{m+1}-\sum_{k=0}^{n-1}(k+1)\binom{m+(k+1)}{m+1} + 0\binom{m+ 0 }{m+1}=$$ $$n\binom{m+n+1}{m+1}+\sum_{k=0}^{n-1}k\binom{m+k+1}{m+1}-\sum_{k=0}^{n-1}(k+1)\binom{m+k+1}{m+1}=$$

$$n\binom{m+n+1}{m+1}+\sum_{k=0}^{n-1}(k-(k+1))\binom{m+k+1}{m+1}=$$ $$n\binom{m+n+1}{m+1}+\sum_{k=0}^{n-1}-1\binom{m+k+1}{m+1}=$$ By the Hockey-Stick identity:

$\sum_{k=r}^n\binom{k}{r}=\binom{n+1}{r+1}$ $$n\binom{m+n+1}{m+1}-\binom{m+(n-1)+1 +1}{m+2}=$$ $$n\binom{m+n+1}{m+1}-\binom{m+n+1}{m+2}$$

The equation is satisfied.

Inductive Step. 3: $n\longrightarrow (n+1)$

$$\sum_{k=0}^{(n+1)}k{m+k \choose m}=$$

$$\sum_{k=0}^{(n+1)}k\left[\binom{m+k+1}{m+1}-\binom{m+k}{m+1}\right]=$$ $$\sum_{k=0}^{(n+1)}k\binom{m+k+1}{m+1}-\sum_{k=0}^{(n+1)}k\binom{m+k}{m+1}=$$ $$(n+1)\binom{m+(n+1)+1}{m+1}+\sum_{k=0}^{n}k\binom{m+k+1}{m+1}-\sum_{k=0}^{n}(k+1)\binom{m+(k+1)}{m+1} + 0=$$

$$(n+1)\binom{m+(n+1)+1}{m+1}+\sum_{k=0}^{n}k\binom{m+k+1}{m+1}-\sum_{k=0}^{n}(k+1)\binom{m+k+1}{m+1}=$$

$$(n+1)\binom{m+(n+1)+1}{m+1}+\sum_{k=0}^{n}(k-(k+1))\binom{m+k+1}{m+1}=$$ $$(n+1)\binom{m+(n+1)+1}{m+1}+\sum_{k=0}^{n}-1\binom{m+k+1}{m+1}=$$

By the Hockey-Stick identity:

$\sum_{k=r}^n\binom{k}{r}=\binom{n+1}{r+1}$ $$(n+1)\binom{m+(n+1)+1}{m+1}-\binom{m+(n+1) +1}{m+2}$$

The equation is satisfied.

q.e.d

Answer 3

Here is a somewhat different approach. We use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series. This way we can write e.g. \begin{align*} [x^k](1+x)^n=\binom{n}{k} \end{align*}

We obtain for $m,n\geq 0$ \begin{align*} \sum_{k=0}^n&k\binom{m+k}{m}\\ &=\sum_{k=1}^nk[x^m](1+x)^{m+k}\tag{1}\\ &=[x^m](1+x)^{m+1}\sum_{k=1}^nk(1+x)^{k-1}\tag{2}\\ &=[x^m](1+x)^{m+1}D_x\left(\sum_{k=1}^n(1+x)^k\right)\tag{3}\\ &=[x^m](1+x)^{m+1}D_x\left(\frac{1-(1+x)^{n+1}}{1-(1+x)}\right)\tag{4}\\ &=[x^m](1+x)^{m+1}\left[\frac{n(1+x)^n}{x}-\frac{(1+x)^n}{x^2}+\frac{1}{x^2}\right]\tag{5}\\ &=n[x^{m+1}](1+x)^{m+n+1}-[x^{m+2}](1+x)^{m+n+1}+[x^{m+2}](1+x)^{m+1}\tag{6}\\ &=n\binom{m+n+1}{m+1}-\binom{m+n+1}{m+2} \end{align*} and the claim follows

Comment:

• In (1) we apply the coefficient of operator.

• In (2) we do a little rearrangement by using the linearity of the coefficient of operator.

• In (3) we use the differential operator $D_x:=\frac{d}{dx}$.

• In (4) we use the formula for the finite geometric series.

• In (5) we differentiate the expression.

• In (6) collect terms and apply the formula \begin{align*} [x^{p+q}]A(x)=[x^p]x^{-q}A(x) \end{align*}

• In (7) we select the coefficients of $x^{m+1}$ and $x^{m+2}$. Note the coefficient of $x^{m+2}$ in the last term is zero, since the polynomial $(1+x)^{m+1}$ has degree less than $m+2$.

Answer 4

$\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{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#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}$

$\ds{\sum_{k = 0}^{n}k{m + k \choose m} = n{m + n + 1 \choose m + 1} - {m + n + 1 \choose m + 2}:\ ?\,,\qquad m, n \geq 0}$.

1. Our first step is 'to move' the index $\ds{k}$ to the binomial lower argument as follows: \begin{align} \color{#f00}{\sum_{k = 0}^{n}k{m + k \choose m}} & = \sum_{k = 0}^{n}k{m + k \choose k} = \sum_{k = 0}^{n}k{-m - k + k - 1 \choose k}\pars{-1}^{k} \\[5mm] & = \sum_{k = 0}^{n}\pars{-1}^{k}\,k{-m - 1 \choose -m - 1 - k}\label{1}\tag{1} \end{align}
2. Hereafter, we'll use the identity \begin{equation} {p \choose q} = \oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{p} \over z^{q + 1}} \,{\dd z \over 2\pi\ic}\label{2}\tag{2} \end{equation} With \eqref{1} and \eqref{2}: \begin{align} \color{#f00}{\sum_{k = 0}^{n}k{m + k \choose m}} & = \sum_{k = 0}^{n}\pars{-1}^{k}\,k\oint_{\verts{z}\ =\ 1^{-}} {\pars{1 + z}^{-m - 1} \over z^{\pars{-m - 1 - k} + 1}} \,{\dd z \over 2\pi\ic} \\[5mm] & = \oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{-m - 1} \over z^{-m}} \sum_{k = 0}^{n}k\,\pars{-z}^{k}\,{\dd z \over 2\pi\ic} \\[1cm] & = \oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{-m - 1} \over z^{-m}}\,\times \\[5mm] & \bracks{\pars{-1}^{n}n\, {z^{n + 2} \over \pars{1 + z}^{2}} + \pars{-1}^{n}\pars{n + 1}\,{z^{n + 1} \over \pars{1 + z}^{2}} - {z \over \pars{1 + z}^{2}}}\,{\dd z \over 2\pi\ic}\label{3}\tag{3} \end{align} In \eqref{3}, the $\ds{\bracks{\cdots}}$-bracket expression is the result of $\ds{\sum_{k = 0}^{n}k\,\pars{-z}^{k}}$.
3. \eqref{3} is reduced to

\begin{align} &\color{#f00}{\sum_{k = 0}^{n}k{m + k \choose m}} \\[5mm] = &\ \pars{-1}^{n}\,n\oint_{\verts{z}\ =\ 1^{-}} {\pars{1 + z}^{-m - 3} \over z^{-m - n - 2}} \,{\dd z \over 2\pi\ic} + \pars{-1}^{n}\pars{n + 1} \oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{-m - 3} \over z^{-m - n - 1}} \,{\dd z \over 2\pi\ic} \\[5mm] &\ - \oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{-m - 3} \over z^{-m - 1}} \,{\dd z \over 2\pi\ic} \end{align} With the identity \eqref{2}, the last expression becomes \begin{align} \color{#f00}{\sum_{k = 0}^{n}k{m + k \choose m}} & = \pars{-1}^{n}\,n{-m - 3 \choose -m - n - 3} + \pars{-1}^{n}\pars{n + 1}{-m - 3 \choose -m - n - 2} - {-m - 3 \choose -m - 2} \label{4}\tag{4} \end{align} In this expression, the binomial arguments are negative since $\ds{m, n \geq 0}$. Therefore, it's convenient to use the following identity: \begin{equation} {p \choose q} = \pars{-1}^{p - q}{-q - 1 \choose p - q}\,,\qquad q \leq p \end{equation} 4. \eqref{4} is reduced to: \begin{align} \color{#f00}{\sum_{k = 0}^{n}k{m + k \choose m}} & = \pars{-1}^{n}\,n\,\pars{-1}^{n}{m + n + 2 \choose n} + \pars{-1}^{n}\pars{n + 1}\,\pars{-1}^{n - 1}{m + n + 1 \choose n - 1} \\ & -\,\pars{-1}^{-1}\ \overbrace{{m + 1 \choose -1}}^{\ds{=\ 0}} \\[1cm] & = n{m + n + 2 \choose m + 2} - \pars{n + 1}{m + n + 1 \choose m + 2} \\[5mm] & = n\ \overbrace{\bracks{{m + n + 1 \choose m + 2} + {m + n + 1 \choose m + 1}}} ^{\ds{\mbox{Pascal Triangule Identity}}}\ -\ \pars{n + 1}{m + n + 1 \choose m + 2} \end{align} The last expression leads to $$ \color{#f00}{\sum_{k = 0}^{n}k{m + k \choose m}} = \color{#f00}{n{m + n + 1 \choose m + 1} - {m + n + 1 \choose m + 2}} $$