Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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

share|cite|improve this question
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
@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
up vote 3 down vote accepted

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

share|cite|improve this answer
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
Let's go back a bit... you said "Insisting that the right hand side have lower index as the terms in the left hand side is unhelpful." I am saying that this part of your answer is sidestepping the whole point of my question. But I'll provide an example in my question that may help. – abiessu Aug 12 '13 at 18:32
I see your point about an identity. I have rephrased the title to more accurately identify what I am looking for. – abiessu Aug 12 '13 at 19:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.