@kaiqi I think another entrance could make the induction more tractable and convincing.

ps:

Proof: P(i, j, k) = 1 / k , 1 <= k <= n & 1 <= i , j <= k

first, we should notice that swap process based on position i won't affect elements after it, because we exchange it with an element before it.

k = 1, true, as we can only exchange it with itself, P(1, 1, 1) = 1 = 1 / 1

k = 2, true, as P(1,2,2) = P(1,1,1) = P(2,1,2) = P(2,2,2) = 1 / 2

Suppose P(i, j, m - 1) = 1 / (m - 1) holds for all i, j that 1 <= i, j <= m - 1. When k = m,

P(m, j, m) = 1 / m, because we randomly choice a new position in [1, m] for the element originally at position m

for any element originally at postion i that i is [1, m - 1],

j = m, P(i, m, m) = sum ( P(i, a, m - 1) * 1 / m ), a = 1, 2, ..., m - 1

= (1 / (m - 1) * 1 / m + 1 / (m - 1) * 1 / m + ..... + 1 / (m - 1) * 1 / m)

= (m - 1) * ( 1 / (m - 1) * 1 / m)

= 1 / m

above formula means: the element originally at position i is at position a when finishing swap based on position (m - 1), and now we choice to swap it with element at position m. a has (m - 1) possible values.

j != m, then this element is not chose, so it is not affected in this turn. If it at position j, it must be at position j last turn.

P(i, j, m) = P(i, j, m - 1) * (m -1) / m = 1 / (m - 1) * (m - 1) / m = 1/ m

proved!