Given a permutation of $1,\ldots,n$ we can decompose it into cycles (e.g., the permutation $(3,2,1,4) $ has cycles $1\to 3\to 1, 2\to 2, 4\to 4 $). Let's use the convention that the first cycle starts with $1$.
Let $X_k=1$ if a cycle ends at the $k$th step and $0$ otherwise (so that in the above example, $X_1=0,X_2=X_3=X_4=1).$ I want to show $$P(X_k=1)=\frac{1}{n-k+1}$$
I am having difficulty since I don't know how many different ways one of the cycles can end at the $k$th step. If $k=2,$ we have either a cycle (a) $1\to a\to 1$ or (b) two cycles $1\to 1,a\to a$. So the probability that $P(X_2=1)$ should be the sum that we are in one of these disjoint cases. The probability of (a) is $\frac{(n-1)(n-2)!}{n!}=\frac{1}{n}$ since there are $n-1$ choices for $a$ and $(n-2)!$ ways to permute the remaining $n-2$ elements other than $1,a$; and the probability of (b) is $\frac{(n-1)(n-2)!}{n!}=\frac{1}{n}$ since there are $(n-1)(n-2)!$ permutations fixing $1,a\not=1$.
This cannot be correct since the sum is $2/n$ while the formula says it's $\frac{1}{n-2+1}=\frac{1}{n-1}$. How can this be proved (for any $k$)?
Attached is the original source of the problem, #12 of Feller'Probability.
Here is one way of understanding this result.
Define a bijection $\Phi:\Omega_n\to\Omega_n$ on the set $\Omega_n$ of permutations. For a permutation $x= x_1 x_2\dots x_n$, move from right to left inserting a right bracket after every $x_k$ where $x_k=\inf\{x_k,x_{k+1},\dots, x_n\}$. Fill in left brackets where necessary. This is the cycle structure of a new permuation $\Phi(x).$
For example, if $x = 361975284$ then we get the cycle structure $(361)(9752)(84)$ which gives $\Phi(x)=396821547$. We adopt the convention that the smallest element in each cycle is written last, and that the cycles are ordered by smallest element.
Since $\Phi$ is a bijection, if $Y$ is uniformly distributed on $\Omega_n$ then so is $X=\Phi^{-1}(Y)$. The chance that a randomly selected permutation $Y$ will have a cycle completed at the $k$th step is the chance that $X_k=\inf\{X_k,X_{k+1},\dots, X_n\}$, that is, ${1\over n-k+1}$.