Proof of the infinite descent principle

I would argue a different way.

By assumption, for all $n$, $a_n > a_{n+1}$, or $a_n \ge a_{n+1}+1$.

Therefore, since $a_{n+1} \ge a_{n+2}+1$, $a_n \ge a_{n+2}+2$.

Proceeding by induction, for any $k$, $a_n \ge a_{n+k}+k$.

But, set $k = a_n+1$. We get $a_n \ge a_{n+a_n+1}+a_n+1 > a_n$.

This is the desired contradiction.

This can be stated in this form: We can only go down as far as we are up.

Note: This sort of reminds me of some of the fixed point theorems in recursive function theory.

Your argument does seem to work. Note that the last paragraph, however, is unnecessary. In the second last paragraph you have shown that $a_n \ge k + 1$ for every $n$ ($n$ was arbitrary here).

Also, your argument seems to be unneccesarily complicated. Here is how I would argue:

Fix any sequence of natural numbers $\left\{a_n\right\}$. Then by definition of natural numbers there are only finitely many $m \le a_0$, therefore we cannot choose infinitely many distinct numbers below $a_0$ and $\left\{a_n\right\}$ does not have infinite descent.