Background: I am looking for a polynomial representation of
$$
\sum_{n=m+1}^N \binom {n-1} m \tag{1}
$$
where $m\in\mathbb{Z^+}$ is a positive integer $2,3,4,\ldots $ that is greater than or equal to $2$. I know how to write polynomials for small values of $m$ and am curious if the general case also produces a polynomial that can be written down by hand. Below I complete the analysis where $m=2$ and $m=3$.
Case 1: m=2. Equation $(1)$ becomes
\begin{equation}
\sum_{n=3}^N \binom {n-1} 2 = \sum_{n=3}^N \frac{(n-1)(n-2)}{2} = \sum_{n=3}^N \frac{n^2-3n+2}{2}.
\end{equation}
Since
\begin{align}
\sum_{n=3}^N n^2 &= \sum_{n=1}^N n^2 – \sum_{n=1}^2 n^2 = \frac{N(N+1)(2N+1)}{6}-5 = \frac{1}{6}\left(2N^3+3N^2+N-30\right), \\\\
3\sum_{n=3}^N n &= 3\sum_{n=1}^N n – 3\sum_{n=1}^2 n=\frac{3N(N+1)}{2} – 9 = \frac{3}{2}\left(N^2+N-6\right), \\\\
\sum_{n=3}^N 2 &= 2\sum_{n=1}^N 1 – 2\sum_{n=1}^2 1 = 2(N-2),
\end{align}
we have
\begin{align}
\sum_{n=3}^N \binom {n-1} 2 &= \frac{1}{12}\left(2N^3+3N^2+N-30\right) – \frac{3}{4}\left(N^2+N-6\right) + (N-2) \notag\\\\&=
\boxed{\frac{N^3}{6} – \frac{N^2}{2} + \frac{N}{3}}. \tag{2}
\end{align}
Case 2: m=3. Equation $(1)$ becomes
\begin{equation}
\sum_{n=4}^N \binom {n-1} 3 = \sum_{n=4}^N \frac{(n-1)(n-2)(n-3)}{6} = \sum_{n=4}^N \frac{n^3-6n^2+11n-6}{6}.
\end{equation}
Because
\begin{align*}
\sum_{n=4}^N n^3 &= \sum_{n=1}^N n^3 – \sum_{n=1}^3 n^3 = \frac{N^2(N+1)^2}{4} – 36 = \frac{1}{4}\left(N^4 + 2N^3 + N^2 – 144\right), \\\\
6\sum_{n=4}^N n^2 &= 6\sum_{n=1}^N n^2 – 6\sum_{n=1}^3 n^2 = N(N+1)(2N+1)-84 = 2N^3+3N^2+N-84, \\\\
11\sum_{n=4}^N n &= 11\sum_{n=1}^N n – 11\sum_{n=1}^3 n= \frac{11N(N+1)}{2} – 66 = \frac{11}{2}\left(N^2+N-12\right), \\\\
\sum_{n=4}^N 6 &= 6\sum_{n=1}^N 1 – 6\sum_{n=1}^3 1 = 6(N-3),
\end{align*}
we see that
\begin{align*}
\sum_{n=4}^N \binom {n-1} 3 &= \notag \frac{1}{24}\left(N^4 + 2N^3 + N^2 – 144\right) – \frac{1}{6}\left(2N^3+3N^2+N-84\right) \\\\
& + \frac{11}{12}\left(N^2+N-12\right) – (N-3) \notag \\\\&=
\boxed{\frac{N^4}{24} – \frac{N^3}{4} + \frac{11N^2}{24} – \frac{N}{4}}. \tag{3}
\end{align*}
Next, I move onto the general case where $m$ is greater than $3$.
Case 3: m=m. Equation $(1)$ is
$$
\sum_{n=m+1}^N \binom {n-1} m = \sum_{n=m+1}^N\frac{(n-1)(n-2)\ldots(n-m)}{m!}=? \tag{4}.
$$
Through a computer algebraic system (such as Mathematica), I found that
$$
\sum_{n=m+1}^N \binom {n-1} m = \frac{\binom N m(N-m)}{m+1}=\boxed{\frac{(N-m)N!}{m!(N-m)!(m+1)}}\tag{5}.
$$
Equation $(5)$ follows from induction. For the inductive step, I assume
$$
\sum_{n=m+1}^N \binom {n-1} m = \frac{\binom N m(N-m)}{m+1}.
$$
Adding $\binom{N}{m}$ to both sides to gives
$$ \begin{align*}
\sum_{n=m+1}^{N+1} \binom {n-1} m &= \frac{\binom N m(N-m)}{m+1} + \binom{N}{m} \\&=
\frac{(N+1)!}{(m+1)!(N-m)!} \\&=
\frac{(N+1)!(N+1-m)}{(m+1)!(N+1-m)!} \\&=
\frac{\binom {N+1} m (N+1-m)}{m+1}
\end{align*}$$
which validates $(5)$.
Question: Is $(5)$ the most general polynomial representation of the general case (similar to $(2)$ and $(3)$ when $m=2$ and $m=3$)? Would it be better to instead apply Stirling numbers of the first kind?
Best Answer
Yes, what you found in (5) is the Hockey stick identity, yours can be written more simply as $$ \sum_{n=m+1}^N \dbinom {n-1} m=\binom{N}{m+1}. $$ If you wanted it as a polynomial in $N$, i.e. expressing its coefficients, then again yes Stirling numbers of the first kind are the answer. By definition $(x)_n=\sum_{k=0}^{n}s(n,k)x^k$ and so $$ \sum_{n=m+1}^N \dbinom {n-1} m=\sum_{k=0}^{m+1}\frac{s(m+1,k)}{(m+1)!}N^k. $$