$(20$ points$)$ Let RANDOM$(1,k)$ be a procedure that draws an integer uni$-$

formly at random from $1,k$ and returns it$.$ We assume that a call of

Random takes $O(1)$ worst$-$case time. The following recursive algorithm

RANDOM$-$SAMPLE generates a random subset of $1,n$ with $mn$ dis$-$

tinct elements. Prove that Random$-$Sample returns a subset of $1,n$ of

size $m$ drawn uniformly at random.