I know that ${m+1 \choose p+1} = {m \choose p} + {m \choose p+1}$, does this identity extend further out? My guess is that there exist certain $k$ such that there exists $r > k$ where the title formula holds.
Problem constraints:
- $m, p, k$ and $r$ are restricted to the non-negative integers
- This problem may be rephrased as "Given positive integers $m$ and $p$, how many non-negative integers $k$ and $r$ exist such that ${m+r \choose p} + {m \choose p+1} = {m+k \choose p+1}$?"
This problem has arisen in conjunction with some of my integer polynomial studies.
In particular, consider the following two integer polynomials:
$$p(x) = {x \choose 3} + x + 1$$
and
$$q(x) = {x \choose 2} + 1$$
These two polynomials have a common point at $x = 0$. Do they have any others? I write them in binomial form because that is the most broad form of integer polynomial I am aware of. Note that these two polynomials are related in the sense that $q(x) = p(x+1) - p(x)$ (barring any offset to $x$).
Define $r(x; x_0) = q(x) + p(x_0)$. This polynomial is the starting point for this question. In particular, for a given $x_0$, how many polynomials $r(x; x_1 \neq x_0)$ share a value with $r(x; x_0)$ for some $x$?
The primary question is for ${m+r \choose p} + {m \choose p+1} = {m+k \choose p+1}$, what about for ${m+r \choose p} + {m \choose p+u} = {m+k \choose p+u}$ for $u\in [2, m-p-2]$?
Edited, hopefully now understanding better what was being asked.
One has $\sum_{i=0}^n\binom ik=\binom{n+1}{k+1}$, which is easily proved by induction from Pascal's recurrence you mentioned. It follows (with some renaming, and subtracting the part of the summation that has been skipped) that $$ \sum_{i=0}^k{m+i \choose p} = \binom{m+k+1}{p+1} - \binom{m}{p+1}. $$ With this the formula asked in the title becomes equivalent to $$ \binom{m+r}p + \binom m{p+1} = \binom{m+k+1}{p+1}. $$ Apart from the case $k=0,r=0$ that gives Pascal recurrence, it looks highly unlikely that there would be such an identity with $k$ and $r$ expressions in $m$ and $p$. Indeed it is easy to see that when $p=0$ there are no nonzero values at all for $k$ that work, as the equation becomes $1+m=m+k+1$. For $p=1$ there are a lot of solutions: the equation becomes $m+r=\binom{m+k+1}2-\binom m2$, so $k$ can be arbitrary and $r$ can be adapted to it using this equation. For the first really interesting value $p=2$ I've done some computational experiments, using the fact that it is easy to test whether a given number (here $\binom{m+k+1}3-\binom m3$) can be written a triangular number. I did not find any values of $m$ for which no $k>0$ could be found at all, but often a long search was needed, and there appears to be no regularity at all in the values of $k$ that worked (also some values of $m$ gave a lot of possibilities for $k$, while others gave very few. Here is a small table for $p=2$. $$ \begin{matrix} m &1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16 \\ \hline k & 4& 16& 6& 1& 88& 124& 2& 214& 268& 12& 9& 7& 10& 26& 718& 814\\ r & 10& 51& 20& 8& 534& 875& 16& 1935& 2690& 64& 54& 48& 65& 153& 11504& 13855 \end{matrix} $$ So I guess my conclusion would be that there is little hope for an identity of the kind you are after. I have no guess about the abstract question whether for every $p>0$ and $m$ there would exist some appropriate $k>0$ and $r$.