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 🙂
Best Answer
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.