Hint for the "triple variable recursion" problem:
Define an ordering as follows: (x, y, z) < (x', y', z') iff x<x', or x=x' and y<y', or x=x' and y=y' and z<z'. (If you want a rigorous solution, below is a second hint.)
Second hint:
We show, as follows, that, for the ordering given in the first hint, there is no infinite decreasing sequence (x_1, y_1, z_1) > (x_2, y_2, z_2) > (x_3, y_3, z_3) > ...
Suppose towards contradiction there is such a sequence. For all k > 1, x_1 >= x_k. So, for some m > 1, we must have x_m = x_{m+1} = x_{m+2} = ... So, for all k > m, we must have y_m >= y_k. So, for some n > m, we must have y_n = y_{n+1} = y_{n+2} = ... So, for all k > n, we must have z_n >= z_i. So for some p > n, we must have z_p = z_{p+1} = z_{p+2} = ...
It follows that the sequence is in fact finite, which is a contradiction, as desired.