1
$\begingroup$

Prove $$ \sum_{k=0}^n \binom{m+k}{m} = \binom{m+n+1}{m+1} $$ by considering the coefficient of $x^n$ in $(1-x)^{-1} (1-x)^{-m-1} = (1-x)^{-m-2}$.

I have succeeded in proving this using induction and in a combinatorial way, but I need to practice with power series.

Background: third year mathematics at university

My attempt

The given equality can be rewritten as

$$ \left( \sum_{k=0}^\infty \binom{-1} k (-x)^k \right) \left( \sum_{\ell=0}^\infty \binom{-m-1}{\ell} (-x)^\ell \right) = \sum_{n=0}^\infty \binom{-m-2}{n} x^n (-1)^n $$

and we can work out the left-hand side as

$$ \sum_{n=0}^\infty \sum_{k+\ell=n} \binom{-1}{k} \binom{-m-1}{\ell} (-x)^{k+\ell} = \sum_{n=0}^\infty \sum_{k=0}^n \binom{-1}{k} \binom{-m-1}{n-k} x^n (-1)^n $$

and now we equate the coefficients in front of $x^n$ on both sides to get

$$ \sum_{k=0}^n \binom{-1}{k} \binom{-m-1}{n-k} = \binom{-m-2}{n}. $$

But how to proceed? Because I don't see the original equation in this.

$\endgroup$
3
  • 1
    $\begingroup$ Hockey Stick Identity $\endgroup$ Commented Dec 19, 2018 at 8:20
  • $\begingroup$ @YadatiKiran Thanks for the link, it is indeed the same! Now to figure out from the many answers how to prove it using power series. $\endgroup$
    – PHPirate
    Commented Dec 19, 2018 at 8:52
  • $\begingroup$ Ok maybe it is not quite the same, there are ideas in those answers similar to mine but the problem here remains. $\endgroup$
    – PHPirate
    Commented Dec 19, 2018 at 9:10

1 Answer 1

1
$\begingroup$

I mean, you're pretty much done from where you got at. Just note that ${ -1 \choose k}=(-1)^k$ and ${-m-2 \choose n}= {m+n+1 \choose n}$(up to some minus sign) and ${-m-1 \choose k}={m+k \choose k}$(use this instead of ${-m-1 \choose n-k}$ on the LHS of your identity by just changing k to n-k). To prove these identities just write out your binomial coefficients in full.

$\endgroup$
4
  • $\begingroup$ Indeed it almost works out, I have the LHS equal but for the RHS I have $\binom{-m-2}{n}=(-1)^n \binom{m+n+1}{n}$, so it is almost equal to $\binom{m+n+1}{m+1}$ except for the minus sign, which stays, right? $\endgroup$
    – PHPirate
    Commented Dec 19, 2018 at 9:36
  • $\begingroup$ What do you mean by the "minus sign stays"? The minus signs on the LHS should balance those on the RHS, please check carefully. $\endgroup$
    – Sorin Tirc
    Commented Dec 19, 2018 at 9:39
  • $\begingroup$ For the LHS I have that they are exactly equal: $\binom{-1}{k} \binom{-m-1}{k} = (-1)^k (-1)^k \binom{m+k}{k}=\binom{m+k}{m}$ as you say, so that's not where the $(-1)^n$ disappears. $\endgroup$
    – PHPirate
    Commented Dec 19, 2018 at 9:40
  • $\begingroup$ Oh I see, I have a $(-1)^n$ wrong in my attempt in the question! Thanks! $\endgroup$
    – PHPirate
    Commented Dec 19, 2018 at 9:45

You must log in to answer this question.

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