[Math] Recursive derangement proof clarification

Question

I saw a proof of a recursive definition of $D_n$ = the number of derangements of a set of size $n$.

A combinatorial proof of the recurrence for $D_n$:

Here's a combinatorial proof of $D_n = (n-1)(D_{n-1} + D_{n-2})$ for $n \geq 2$ due to Euler.

For any derangement $(j_1, j_2, \ldots, j_n)$, we have $j_n \neq n$. Let $j_n = k$, where $k \in \{1, 2, \ldots, n-1\}$. We now break the derangements on $n$ elements into two cases.

Case 1: $j_k = n$ (so $k$ and $n$ map to each other). By removing elements $k$ and $n$ from the permutation we have a derangement on $n-2$ elements, and so, for fixed $k$, there are $D_{n-2}$ derangements in this case.

Case 2: $j_k \neq n$. Swap the values of $j_k$ and $j_n$, so that we have a new permutation with $j_k = k$ and $j_n \neq n$. By removing element $k$ we have a derangement on $n-1$ elements, and so, for fixed $k$, there are $D_{n-1}$ derangements in this case.

Thus, with $n-1$ choices for $k$, we have, for $n \geq 2$,
$$D_n = (n-1)(D_{n-1} + D_{n-2}).$$

What I'm having trouble understanding is, if $j_n \neq n$, and $j_n=k$, why can $k$ only be any positive integer less than $n$, and does this only apply to the final element of the derangement (which is listed here as $j_n$), or does it apply to all of them? If it did apply to all of them, it seems like the only numbers being able to be chosen for a certain position would be those less than the position number, but that doesn't seem logical to me.

Any help would be very much appreciated.

Proof from: Mike Spivey (https://math.stackexchange.com/users/2370/mike-spivey), I have a problem understanding the proof of Rencontres numbers (Derangements), URL (version: 2012-08-28): https://math.stackexchange.com/q/83433

Answer 1

We do not have to pick the last element. We can pick other element as well and the proof will still work.

If $j_n = n$, then it is not a derangement anymore. Hence $j_n = k$ where $k \neq n$.

We can change the proof.

You can pick a particular index $p \in \{ 1, \ldots, n\}$

For any derangement $(j_1, j_2, \ldots, j_n)$, we have $j_p \neq p$. Let $j_p = k$, where $k \in \{1, 2, \ldots, n\}\setminus \{p\}$. We now break the derangements on $n$ elements into two cases.

Case $1$: $j_k = p$

Case $2$: $j_k \neq p$.