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

Question

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.

Answer 1

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$.

Answer 2

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)$.

Answer 3

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}$