6
$\begingroup$

I was just doing some algebra on a paper and obtained: $$\sum_{l=0}^{n-1} {{n+l} \choose l}={2n \choose {n+1}}$$

Are there some generalizations of this identity?

One possible generalization would be $$F_m(n)=\sum_{l=0}^{n-1} {{n+l} \choose l}^{m}$$ but it is not in my reach to obtain what would $F_m(n)$ equal to for every $m \in \mathbb N$

Other possible generalization could be of the form $$G_k(n)=\sum_{l=0}^{n-1} k^l \cdot{{n+l} \choose l}$$

I am interested in any generalization(s), not neccessarily of the forms I mentioned (I could mention some other forms but so could you so there is no need to do that).

You do not need to prove in an answer a generalization that you mention but it would be nice if you would point me to a direction where that generalization is mentioned and proven.

I asked a same question on MSE and received neither a comment nor an answer so I deleted that question there and decided to ask it here, although this is a low-level question for MO.

Improve this question
$\endgroup$
2
  • $\begingroup$ Favourited. I swear I've seen this before. ETA: An answer below beat me to it. $\endgroup$
    – BCLC
    Commented Apr 2, 2018 at 18:41
  • $\begingroup$ Note: your last expression can also be written as $$(1-k)^{-(n+1)} \left(1-\frac{(2 n)! B_k(n,n+1)}{n! (n-1)!}\right),$$ where $B$ is the incomplete beta function. $\endgroup$
    – AccidentalFourierTransform
    Commented Apr 2, 2018 at 19:10

3 Answers 3

Reset to default
9
$\begingroup$

What about the generalised Vandermonde identity: $$ { n_1+\dots +n_p \choose m }= \sum_{k_1+\cdots +k_p = m} {n_1\choose k_1} {n_2\choose k_2} \cdots {n_p\choose k_p} $$

See also Hockey-stick identity and Identities involving binomial coefficients.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The hockey-stick identity is indeed a generalization of the identity in question. But how does the identity in question quickly follow from the Vandermonde identity? $\endgroup$
    – Iosif Pinelis
    Commented Apr 2, 2018 at 17:42
  • $\begingroup$ @IosifPinelis if take $p=2$ and use $\binom{n}{k}=\binom{n}{n-k}$ and relabel some indices you get the identity in your post. $\endgroup$
    – AccidentalFourierTransform
    Commented Apr 2, 2018 at 17:56
  • 1
    $\begingroup$ I KNEW I'VE SEEN THIS BEFORE! Great answer! $\endgroup$
    – BCLC
    Commented Apr 2, 2018 at 18:40
  • 1
    $\begingroup$ @AccidentalFourierTransform : I still don't see see it. In the Vandermonde identity, the upper indices $n_i$ are fixed, and the lower indices $k_i$ vary. In the OP's identity, the upper index varies. Can you add to your answer full details of the derivation of the OP's identity from the Vandermonde one? $\endgroup$
    – Iosif Pinelis
    Commented Apr 2, 2018 at 18:52
6
$\begingroup$

Since $\binom{n+l}{l} = \binom{n+l}n$, we have $$\sum_{l=0}^{n-1} \binom{n+l}{l} = \sum_{i=n}^{2n-1} \binom{i}{n}.$$ Here the lower and upper summation bounds as well as the lower index of binomial coefficients depend on $n$. This is a particular case of a more general formula, where all three entities are independent: $$\sum_{i=n}^m \binom{i}{k} = \binom{m+1}{k+1} - \binom{n}{k+1}.$$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Isn't your identity equivalent to the hockey-stick identity (without loss of generality you can take $n=k$ in your 2nd displayed identity)? $\endgroup$
    – Iosif Pinelis
    Commented Apr 2, 2018 at 17:45
  • $\begingroup$ @IosifPinelis: Yes, one can be easily obtained from the other. $\endgroup$
    – Max Alekseyev
    Commented Apr 2, 2018 at 18:24
5
$\begingroup$

Formula 4.2.5.37 on page 503 in Prudnikov, Brychkov, Marichev is \begin{equation} \sum_{k=0}^n\binom{a+k}a\binom{b-k}{b-n}=\binom{a+b+1}n. \end{equation} Substituting here $a=n+1$ and $b=n$, and then replacing $n$ by $n-1$, we get your identity.

The book Prudnikov, Brychkov, Marichev is in Russian, but this should be no problem here.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ These formulas are essentially the same: formula 4.2.5.36 is obtained from formula 4.2.5.37 by replacement $b$ with $b+n$. $\endgroup$
    – Max Alekseyev
    Commented Apr 2, 2018 at 13:31
  • $\begingroup$ @MaxAlekseyev : That's right, thank you. :-) $\endgroup$
    – Iosif Pinelis
    Commented Apr 2, 2018 at 17:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .