MathDB

Expected number of elements of a subset

Source: Problem 4, Polish NO 1989

October 1, 2005

probabilityexpected valuecombinatorics unsolvedcombinatorics

Problem Statement

n, k

are positive integers.

A_0

is the set

\{1, 2, ... , n\}

A_i

is a randomly chosen subset of

A_{i-1}

(with each subset having equal probability). Show that the expected number of elements of

A_k

\dfrac{n}{2^k}