Polynomial representation of $\sum\limits_{n=m+1}^N \binom {n-1} m$

Question

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?

Answer 1

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. $$