Suppose you would like to take an SRS of size n from a list of N units, but do not know the population size N in advance. Consider the following procedure:
a. Set S0 = {1, 2. . . n}, so that the initial sample for consideration consists of the first n units on the list.
b. For k =1, 2, . . ., generate a random number uk between 0 and 1. If uk >n / (n+k), then set Sk equal to Sk−1. If uk ≤ n / (n+k), then select one of the units in Sk−1 at random, and replace it by unit (n + k) to form Sk .
Show that SN−n from this procedure is an SRS of size n. Hint: Use induction.