# How does WolframAlpha simplify $\sum_{k=0}^{n-1} {k+n-1 \choose n-1}$

Working through a Discrete Math proof I was trying to simplify my equation, but I didn't know how to deal with this summation of a selection: $$\sum_{k=0}^{n-1} {k+n-1 \choose n-1}$$

I put it into wolframalpha and it simplified it for me, saying: $$\sum_{k=0}^{n - 1} {k + n - 1 \choose n - 1} = {2 n - 1 \choose n - 1}$$ (This link should show you the result I got)

That let me simplify enough to finish the problem, but I don't know how wolframalpha got to that answer. We've just begun the basics of this 'choose notation,' but if I need to do some background research to understand why this simplification is valid I'm willing to.

My Question: WolframAlpha simplified my equation, but I'd like to understand the work necessary to get that answer.

P.S. I'm new here, I read through the rules but if I'm doing anything wrong be sure to tell me :)

• You're looking for the hockey stick identity. Dec 8, 2020 at 3:02
• It works through a symbolic algebra program. I'm not sure what the exact algorithm is but I don't think the question is right for this site. It may fit in better on the computational mathematics stack but they don't typically do these questions either. Dec 8, 2020 at 3:06
• @rogerl Hmm thanks I'll look into that Dec 8, 2020 at 3:07
• Notice that the hockey stick identity gives you that the sum is equal to $\dbinom{2n-1}n$ which is the same as $\dbinom{2n-1}{n-1}$ since $\dbinom nr=\dbinom n{n-r}$ Dec 8, 2020 at 3:08
• @PrasunBiswas I can't seem to figure out how the Hockey stick identity applies to my problem, can you show me why it gives that? Dec 8, 2020 at 5:24

First note that $$\sum_{k=0}^{m} {n+k \choose n} = {n+m+1 \choose n+1}$$ So now we have $$\sum_{k=0}^{n-1} {n-1+k \choose n-1}$$ $$={n-1+n-1+1\choose n-1+1}$$ $$={2n-1\choose n}$$ Also note that when $$0\le n\le 2n-1$$, we have $${2n-1\choose n}={2n-1\choose 2n-1-n}$$ I think you can take it from here.