4
$\begingroup$

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 :)

$\endgroup$
6
  • 3
    $\begingroup$ You're looking for the hockey stick identity. $\endgroup$
    – rogerl
    Dec 8, 2020 at 3:02
  • 4
    $\begingroup$ 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. $\endgroup$
    – Ryan Howe
    Dec 8, 2020 at 3:06
  • $\begingroup$ @rogerl Hmm thanks I'll look into that $\endgroup$
    – Ammon Kunzler
    Dec 8, 2020 at 3:07
  • 4
    $\begingroup$ 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}$ $\endgroup$
    – Prasun Biswas
    Dec 8, 2020 at 3:08
  • 1
    $\begingroup$ @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? $\endgroup$
    – Ammon Kunzler
    Dec 8, 2020 at 5:24

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks, I see how you got from step to step $\endgroup$
    – Ammon Kunzler
    Dec 10, 2020 at 23:17
  • $\begingroup$ Where does that identity come from though? $\endgroup$
    – Ammon Kunzler
    Dec 10, 2020 at 23:17
  • 1
    $\begingroup$ It's an application of the hockey-stick identity. You can also find it here. $\endgroup$
    – k170
    Dec 11, 2020 at 6:03

You must log in to answer this question.

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