# Demonstrating that probability for every possible result is uniform at the end of an algorithm

I have memory of $$k$$ elements that you can imagine being represented by an array. One by one, the array receives a value corresponding to the time index, for example at $$t=1$$ the value will be $$1$$. At some point ($$t=k+1$$) the array will be full and we must choose a value inside the array to replace with the new one. The objective is to find an algorithm that outputs a uniform subset of $$k$$ elements. For example, with $$k=2$$ and $$t=3$$ it will output with uniform probability one of the following: $$\{1,2\}$$, $$\{1,3\}$$ or $$\{2,3\}$$. One possible algorithm is the following:

1. create array of $$k$$ elements
2. FOR $$t=1,.\ldots,T$$:
3. if array is not full insert an empty space
5. discard the input with probability $$1 - k/t$$
It's easy to implement such a program and convince yourself that this is indeed a solution to the problem but how do I demonstrate it? Essentially I need to demonstrate that each subset has probability $$1/\binom tk$$ to be the result at the end (that's because $$\binom tk$$ is the number of possible subsets of $$k$$ elements at time $$t$$).
The proof is by induction. The base case $$t = k$$ is clear. Suppose that the claim is true at some time $$t$$. We will prove it for time $$t+1$$.
Let the first $$t+1$$ elements be $$x_1,\ldots,x_{t+1}$$. By the induction hypothesis, at time $$t$$ each of the $$\binom{t}{k}$$ possible $$k$$-subsets of $$x_1,\ldots,x_t$$ is found in the array with equal probability. The probability that at step $$t+1$$ the array remains the same is $$1-k/(t+1)$$, hence each of the $$k$$-subsets of $$x_1,\ldots,x_t$$ appears at time $$t+1$$ with probability $$\frac{t+1-k}{t+1} \frac{1}{\binom{t}{k}} = \frac{1}{\binom{t+1}{k}}.$$ Now consider some $$k$$-subset $$S$$ of $$x_1,\ldots,x_{t+1}$$ that contains $$x_{t+1}$$. For this set to be appear at time $$t+1$$, the following two events need to happen: at time $$t$$, the array consisted of $$S \setminus \{x_{t+1}\}$$ together with one of the $$t-(k-1)$$ remaining elements; and at time $$t+1$$, this element was replaced by $$x_{t+1}$$. In total, the probability is $$\frac{k}{t+1} \cdot \frac{1}{k} \cdot \frac{t-k+1}{\binom{t}{k}} = \frac{1}{\binom{t+1}{k}}.$$