How to prove a sampling algorithm?

This is a homework question. In order to print M sorted distinct random integers in range [0,N) we can use the following algo开发者_运维知识库rithm:

int n = N 
int m = M 
for i in [0,N)
    if (bigrandom() % n--) < m) 
        print i
        m--

As we know, this algorithm pick all integers in the range with equal probability. Could you help me to prove it ?

---

1. The chance of having any particular number selected is m/n.
2. If this number is selected, we have same problem, but with n' = n - 1 and m' = m - 1. If it's not, we have same problem, but with n' = n - 1 and m' = m.

Your algorithm is an implementation of this idea.

You'll also need to prove assumption 1, but that you can probably do yourself.