# Given $p, m$, how many $r, k$ exist such that $\sum_{i=0}^k{m+i \choose p} = {m+r \choose p}$?

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]$?

-
In what way does the summation in the title "extend" the identity mentioned in the body of the question? –  Zev Chonoles Aug 11 '13 at 3:42
–  lab bhattacharjee Aug 11 '13 at 3:45
@labbhattacharjee: yes, related, but only in the sense of the sums that I have already been struggling with for the past month... –  abiessu Aug 11 '13 at 3:47
I have corrected the "alternate formula" in my question. –  abiessu Aug 12 '13 at 12:23

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$.
This restates what has already been said in the comments, and I don't see how it answers the question. I don't insist that $r > k$, I simply note that it must be so. Please review the "alternate formulation" of my question and note that I wish to arrive at ${m+r \choose p}$ as the LHS of your final equation, rather than the sum that I am already very familiar with. –  abiessu Aug 12 '13 at 16:35
The answer applies to the formula suggested in the title: $\sum_{i=0}^k{m+i \choose p} = {m+r \choose p}$. That formula has the same lower index$~p$ on the right as each term on the left: it asks for a relation between coefficients in one same column (namely column $p$) of Pascal's triangle. Such a relation does not exist. The "alternate fomulation" of the second bullet point becomes $\binom{m+r}p=\binom{m+k}{p+1}-\binom m{p+1}=\sum_{i=0}^{k-1}\binom{m+i}p$ with above formula; note the different upper summation limit. –  Marc van Leeuwen Aug 12 '13 at 18:01
Anyway asking that both $k$ and $r$ be adapted for any given $m$ and $p$, even if it could always be done (which I doubt), would hardly amount to an identity unless those $k$ and $r$ are given by fixed, simple, expressions in $m$ and $p$. If you have any idea of why an identity of this nature should exist, you should explain the reasons to believe so in the question. –  Marc van Leeuwen Aug 12 '13 at 18:06