# Supplementary exercise 51, chapter 3 from 'A walk through combinatorics' 4th edition

I'm selfstudying 'A walk through combinatorics' by Miklós Bóna. This book has some supplementary exercises at the end of each chapter, no solution provided. I'm trying exercise 51, chapter 3.

Problemstatement:

A store has $$n$$ different products for sale. Each of them has a different price that is at least one dollar, at most $$n$$ dollars, and is a whole dollar. A customer only has the time to inspect $$k$$ different products. After doing so, she buys the product that has the lowest price among the $$k$$ products she inspected. Prove that on average she will pay $$\frac{n+1}{k+1}$$ dollars.

Attempt at solution: The customer pays:

• 1 dollar if the product with price 1 dollar is the cheapest among the $$k$$ inspected products. This is possible in $$\binom{n-1}{k-1}$$ ways, since we need to pick $$k-1$$ products with prices in $$\{2, \ldots, n\}$$.
• 2 dollars if the product with price 2 dollars is the cheapest among the $$k$$ inspected products. This is possible in $$\binom{n-2}{k-1}$$ ways, since we need to pick $$k-1$$ products with prices in $$\{3, \ldots, n\}$$.
• $$\ldots$$
• $$n-k+1$$ dollar if the product with price $$n-k+1$$ is the cheapest among the $$k$$ inspected products. There are only $$k-1$$ products which are more expensive, so this is possible in $$\binom{n-(n-k+1)}{k-1} = \binom{k-1}{k-1}$$ ways.

This implies that the customer has to pay, on average $$\frac{1}{\binom{n}{k}}\cdot\left(1\cdot \binom{n-1}{k-1} + 2 \cdot \binom{n-2}{k-1} + \ldots + (n-k+1) \cdot \binom{k-1}{k-1}\right).$$

This is where I'm stuck: I want to show that the sum in brackets equals $$\binom{n+1}{k+1}$$ (guess based on what we need to prove, checked with some values of $$n,k$$. This seems to be correct).

Question: How to prove that $$1\cdot \binom{n-1}{k-1} + 2 \cdot \binom{n-2}{k-1} + \ldots + (n-k+1) \cdot \binom{k-1}{k-1} = \binom{n+1}{k+1},$$ a hint would be appreciated. I tried to give a combinatorial proof, but failed.

• The identity you want follows from the Vandermonde Identity
– lulu
Commented Dec 29, 2022 at 12:12
• @lulu I tried wrapping my head around this for the last 30 minutes. In the Vandermonde Identity, the $m$ and $n$ are fixed, whereas I have a variable amount to choose from in the summations. Could you elaborate on why this follows from the Vandermonde Identity? Commented Dec 29, 2022 at 12:39
• One version of Vandermonde is $\sum_{m=0}^n\binom mj\times \binom {n-m}{k-j}=\binom {n+1}{k+1}$. See, e.g., this. Now take $j=1$.
– lulu
Commented Dec 29, 2022 at 12:44
• @lulu Thanks. Would you happen to know if there is a combinatorial proof of that version of the identity? Commented Dec 29, 2022 at 13:06
• Oh, to choose $k+1$ out of $n+1$, pick the $(j+1)^{st}$ value, then take $j$ to the left of it and $k-j$ to the right. Might need to play with that idea a bit, but it should be close.
– lulu
Commented Dec 29, 2022 at 13:32

Based on @Lulu's comment, here is a combinatorial proof of the identity needed to complete the solution of the exercise: $$1\cdot \binom{n-1}{k-1} + 2 \cdot \binom{n-2}{k-1} + \ldots + (n-k+1) \cdot \binom{k-1}{k-1} = \binom{n+1}{k+1}$$

Proof: Consider the set $$\{0, 1, \ldots, n\}$$. Clearly the number of $$(k+1)$$-element subsets equals $$\binom{n+1}{k+1}$$.

We could also pick a $$(k+1)$$-element subset as follows: for an element $$x \in \{1,\ldots, n-k+1\}$$, take one element in the subset $$\{0, 1, \ldots, x-1\}$$ and $$k-1$$ elements in the subset $$\{x+1, \ldots, n\}$$. There are $$x \cdot \binom{n-x}{k-1}$$ ways to do this. Summing over all possible values of $$x$$ proves the identity.

The same approach could be used to prove that $$\sum_{m = 0}^n \binom{m}{j}\binom{n-m}{k-j} = \binom{n+1}{k+1}$$ by taking $$j$$ elements smaller then $$x$$ and $$k-j$$ elements larger than $$x$$ and summing over all possible values of $$x$$.

I want to show a proof that uses the lattice interpretation for the binomial coefficients.

A $$NE-path$$ is a lattice path made up of a unit steps $$NORTH$$ (from $$(a,b)$$ to $$(a,b+1)$$) or unit steps $$EAST$$ (from $$(a,b)$$ to $$(a+1,b)$$).

The binomial coefficient $$\binom{n}{k}$$ is the number of $$NE-paths$$ from $$(0,0)$$ to $$(n-k,k)$$ (or $$(k,n-k)$$). Note that you need to take a total of $$n$$ steps from the origin to get to $$(n-k,k)$$, out of which exactly $$k$$ of them have to be $$NORTH$$.

Now, to come to the identity in question:

$$\binom{n+1}{k+1}$$ counts the number of $$NE-paths$$ from $$(0,0)$$ to $$(n-k,k+1)$$.

$$1\cdot \binom{n-1}{k-1} + 2 \cdot \binom{n-2}{k-1} + \ldots + (n-k+1) \cdot \binom{k-1}{k-1}$$ counts the same lattice paths but grouping the paths based on $$x-coordinate$$ when the lattice path first touches the line $$y=2$$. (Obviously, any $$NE-path$$ from $$(0,0)$$ to $$(n-k,k+1)$$ has to cross the line $$y=2$$ for large enough $$n,k$$).

Once the lattice path touches the line $$y=2$$, the remainder of the path can be considered as a $$NE-path$$ from the point of first contact $$(i,2)$$ to $$(n-k,k+1)$$.

A small hint for alternative:

1. List all possible $$(k+1)$$ - subsets of $$\{0,1,...,n\}$$
2. Remove the smallest element from each subset

You'll end up with a list of all possible $$k$$ - subsets of $$\{1,...,n\}$$ but with each subset repeated as many times as its smallest element.

How many entries are in the list? $$\binom{n+1}{k+1}$$

• I had to write an example to convince myself that this works. Can I ask how you got this idea? What were your thoughts? Commented Jan 4, 2023 at 12:15
• @Student for any integer $m$, $\binom{m}{1}=m$. So sometimes when you wish to multiply with $m$, you can think of it as choosing an additional element from a set of $m$ elements. In this particular example, $m$ is the smallest element in a $k$ subset, and the set $\{0,1,...,m-1\}$ contains $m$ elements Commented Jan 4, 2023 at 13:50