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:

$$d=0 : \binom{n}{n} = \binom{n+1}{n+1}$$
assume true for all d
$$\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}$$

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

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

 

[mathstime]

I get that this equals

$$\binom{n+d+1}{n} + \binom{n+d+1}{n+1} = \binom{n+d+2}{n+1}$$

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?