Combinatorial Problem: Does Sum = Binomial Coefficient?

[mathstime]

Does \sum_{i=0}^n \binom{n-1+d-i}{d-i} = \binom{n+d}{d}??

 

[Werg22]

I'm going to go ahead and assume that the sum on the LHS goes from 0 to d, not from 0 to n. In this case, yes. Because \binom {a}{b} = \binom{a}{a-b}, you can rewrite the LHS as

\sum_{i=0}^d \binom{n-1+d-i}{n -1}

For the same reason, you can rewrite the RHS as \binom{n+d}{n}.

Consider this hint: \binom{n-1+d-i}{n -1} counts the number of subets of {1, 2, 3, ..., n+d-i-1} that are have size n -1. How many subsets of {1, 2, 3, ..., n+d} of size n have maximal maximal element n+d-i?

 

[mathstime]

I'm sorry I don't understand? Could you explain again?

Thank you for your help

 

[mathstime]

Yes, you are correct. The summation should be from 0 to d.

I have actually altered the problem slightly. I want to show that
\sum_{k=0}^d \binom{n+d-k}{n} = \binom{n+d}{n}??

I could maybe do this by induction on d as follows:

<br /> d=0 : \binom{n}{n} = \binom{n+1}{n+1}<br />
assume true for all d
<br /> \sum_{k=0}^{d+1} \binom{n+(d+1)-k}{n} = \binom{n+d+1}{n} + \sum_{k=1}^{d+1} \binom{n+d+1-k}{n}<br />

<br /> = \binom{n+d+1}{n} + \sum_{k=0}^{d} \binom{n+d-k}{n} <br />

and this is where I get stuck? ...any ideas?

 

[mathstime]

I get that this equals

<br /> \binom{n+d+1}{n} + \binom{n+d+1}{n+1} = \binom{n+d+2}{n+1}<br />

is this correct?

If so, how can I show that this equals \binom{n+d}{n} ??

 

[mathstime]

anyone??

 

[Werg22]

Yes, you are correct. The summation should be from 0 to d.

I have actually altered the problem slightly. I want to show that
\sum_{k=0}^d \binom{n+d-k}{n} = \binom{n+d}{n}??

This is not correct. The LHS you have here is not equal to the LHS you had before.

More details on my response:

You should know that if a and b are any two non-negative integers, \binom{a}{b} = \binom{a}{a - b}. e.g., if I have 5 apples, the number of ways I can choose 2 apples is the same as the number of ways I can choose 3 apples. This is easy to see: to every choice of 2 apples, corresponds a choice of 3 apples (the apples that I didn't choose).

This said, this means that we have:

\sum_{i=0}^d \binom{n-1+d-i}{d-i} = \sum_{i=0}^d \binom{n-1+d-i}{(n-1 + d - i) - (d-i)} = \sum_{i=0}^d \binom{n-1+d-i}{n-1}

Also,

\binom{n+d}{d} = \binom{n+d}{(n+d) - d} = \binom{n+d}{n}

So in fact, we are trying to prove that:

\sum_{i=0}^d \binom{n-1+d-i}{n-1} = \binom{n+d}{n}

Let's see how we can prove this. Let's first examine the RHS. What is this number? It's the number of ways we can choose n things from a set of n + d objects.

Let's now look at the LHS. What does this count? Well, consider the set {1, 2, ..., n, n+1, ..., n +d}. As observed above, the RHS counts the number of size n subsets of this set.

Aside from computing \binom{n+d}{n}, there's another way we can count these. Here's the idea: for each of n, n+1, n+2, ... , n+d, count the number of subsets of size n whose maximum element is that number, then add up the results.

For example, if n = 3, d = 2, the number of subsets of size n with maximum element n, is 1, i.e. only the set {1,2,3}. The number of subsets with maximum element of size n+1 (4) is 3, i.e. {1,2,4}, {2, 3, 4}, {1, 3, 4}. The number of elements of subsets of size n with maximum element n + 2 = 5 is 6 (I won't list them). 1 + 3 + 6 = 10. You can easily check that \binom{3+2}{3} = 10, as expected.

Now do you see where this is going? Can you show that \binom{n-1+d-i}{n -1} counts the number of size n subsets of {1, 2, ..., n+d} whose maximum element is n + d - i?