Prove that $f(y',z') > f(y,z)$ if $y' > y$ or $y=y'$ and $z' > z$ 
Let $y,z$ be positive integers so that $z\equiv 1\mod 4, y > z,$ and $y = 2^n$ for some integer $n\ge 2$. Define a sequence of triples $(x_k, y_k, z_k)$ as follows: set $y_{n-1} = y, z_{n-1} = z, x_{n-1} = y/2 + z.$ If $y_k > z_k$, then let $(x_{k-1}, y_{k-1}, z_{k-1}) = (2x_k, y_k/2, z_k)$ and if $z_k > y_k,$ let $(x_{k-1}, y_{k-1}, z_{k-1}) = (x_k - y_k/2 + z_k, y_k, z_k-y_k)$ (note that $y_k$ and $z_k$ are never actually equal, since one is even and the other is odd). Let $f(y,z)$ be the value of $x_i$ when $(y_i, z_i) = (4,1)$. Prove that if $y' > y, f(y',z') > f(y,z)$ and if $z' > z, f(y,z') > f(y,z)$.

Observe that $(y_i, z_i) = (4,1)$ is always eventually reached, since at each stage $y_k$ is reduced or $z_k > y_k$ and $z_k$ is reduced. Once $y_i$ reaches $4, z_i$ will either exceed $y_i$ and will be repeatedly reduced until it reaches $1$ or $z_i$ will already equal $1$ before $y_i$ reaches $4$.
I was thinking of using induction to prove the claim, but I can't make much progress. Initially, $(x_{n-2}, y_{n-2}, z_{n-2}) = (y+2z, y/2, z).$ But then after this step, we may have $y_i > z_i$ or $z_i > y_i$ at each step, where $i$ is the corresponding index for the step. I need to show that the final value obtained if $y < y'$ is smaller than that obtained when $y > y'$. I tried to apply the process to $(y,z) = (128, 1)$ and $(y',z') = (64,61)$. It seems that after a certain point, the values for $(y,z)$ exceed the corresponding ones for $(y',z')$.  For instance, we get that the first few terms of the sequence starting with $(x,y,z) = (65,128,1)$ are $(130,64,1), (260,32,1), (520,16,1)$ and the first few for the sequence starting with $(x,y,z) = (93,64,61)$ are $(186,32,61), (231,32,29), (462,16,29).$
 A: Obseravation
$f( 8, 1) =   10$
$f( 8, 5) =   21$
$f(16,\,\ 1) = \,\ 36$
$f(16,\,\ 5) = \,\ 55$
$f(16,\,\ 9) = \,\ 78$
$f(16,13) =  105$
$f(32,\,\ 1) =  136$
$f(32,\,\ 5) =  171$
$f(32,\,\ 9) =  210$
$f(32,13) =  253$
$f(32,17) =  300$
$f(32,21) =  351$
$f(32,25) =  406$
$f(32,29) =  465$
Computing the difference between $f(y, z)$ and $f(y,z+1)$ for fixed $y$, we can find they form an arithmetic progression. It is not hard to figure out that it seems
$$f(y,z)=\frac{(y+z)^2-1}8$$
Proof of the formula above
Once we have pinpointed the goal, it indicates the way to prove it.
Claim: $2x_{k-1}y_{k-1}+{z_{k-1}}^2=2x_ky_k+{z_k}^2$ for all $k$.
Proof: If $y_k > z_k$, then LHS is $2\cdot2x_k\cdot y_k/2+{z_k}^2$, which is RHS.
If $z_k > y_k,$ LHS is $2(x_k - y_k/2 + z_k)y_k+(z_k-y_k)^2=2x_ky_k-{y_k}^2+2z_ky_k + {z_k}^2-2z_ky_k+{y_k}^2$, which is RHS. $\quad\Box$
The claim says that $2x_ky_k+{z_k}^2$ does not depend on $k$.
When $k=n-1$, that expression is $2(y/2+z)y+z^2=(y+z)^2$.
When the triple becomes $(f(y,z), 4,1)$, that expression is $8f(y,z)+1$.
Hence we know $(y+z)^2=8f(y,z)+1$.
Last step
Since $f(y,z)=\frac{(y+z)^2-1}8$, $y=2^n$ for some integer $n$ and $y>z$, it is straightforward to verify that

*

*if $y' > y, f(y',z') > f(y,z)$ and

*if $z' > z, f(y,z') > f(y,z)$.

