Try to use Pascal's identity.
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 dollars.
There are ways to select k products out of n. The maximum amount she will ever pay is n-k+1.
There are ways in which she ends up paying 1 dollar.
There are ways in which she ends up paying 2 dollars.
... and so on.
How do I proceed?