MathDB

For a given natural number

n

, two players randomly (uniformly distributed) select a common number

0 \le j \le n

, and then each of them independently randomly selects a subset of

\{1,2, \cdots, n \}

with

j

elements. Let

p_n

be the probability that the same set was chosen. Prove that \sum_{k=1}^{n} p_k = 2 \log{n} + 2 \gamma - 1 + o(1), (n \to \infty), where

\gamma

is the Euler constant.

9