How to prove that permutations of x-y can go infinite I am a novice when it comes to mathematics, but I have been give a problem that is causing quite the headache. Basically, I need to know if two values are able to infinitely go against one another given a basic set of rules. The lower number is always multiplied times 2 and the lower number is always subtracted from the higher number, so the sum always stays the same. When either x or y hits 0 the sequence will be terminated, and is therefore finite.
Ex. Where x = 1 and y = 7. Then the next steps would be x = 2 and y = 6, x = 4 and y = 4 x = 8 and y = 0.
I've already concluded that a number is unable to go infinite when x = y, which also means that when the sum of x and y is odd it should always go infinite.
But that's about it when it, I've also noticed that when the sum is equal to a power of 2 the combination is also finite.
I've attempted a recursive function where each the combination of numbers will be recorded, and the function will stop when either a pair has been detected that has already occurred in the sequence before (x=2,y=4 will always be alternating between the values therefore detecting a duplicate) indicating the sequence can go infinite, or when x is equal to y indicating that the sequence is finite. The problem here was the number of iterations required to find an awnser.
Apologies if this has been posted before or if the question is a little vague.
Any help of pointers in the right direction would be greatly appreciated.
 A: First, note that if some integer $k$ divides both numbers in a pair, it will also divide both numbers after the operation. Also note that the original pair $(x,y)$ will lead to a termination if and only if $\left(\frac xk,\frac yk\right)$ also leads to a termination. So it suffices to figure out what happens when the original $x, y$ are coprime. (In this I am assuming that termination means one of the values becomes $0$.)
The inverse of this fact is almost true as well: if you apply the operation to $(x_0, y_0)$ to get $(x_1, y_1)$, and there is some odd $k$ such that $k \mid x_1$ and $k \mid y_1$, then $k \mid x_0$ and $k \mid y_0$. However, the same is not true for $k = 2$. If $x_0, y_0$ are both odd, then $2 \mid x_1, 2 \mid y_1$.
More generally, if $2^n \mid x_0, 2^n \mid y_0$ and $2^{n+1} \mid (x_0 + y_0)$, then $2^{n+1} \mid x_1, 2^{n+1} \mid y_1$. For labelling the numbers so that $x_0 \le y_0$, we get $x_1 = 2x_0$, so $2^{n+1} \mid x_1$, and if $s = x_0 + y_0$, then $x_1, y_1$ have the same sum, so $y_1 = s - x_1$, and since $2^{n+1}$ divides both $s$ and $x_1$, it divides $y_1$ as well.
This observation leads to the solution to your problem: if $x_0, y_0$ are coprime, then the sequence they induce will terminate if and only if $x_0 + y_0 = 2^n$ for some $n$. If $x_0 + y_0 = 2^n$, then by induction, $2^k$ will divide both $x_k$ and $y_k$ for all $k \le n$. In particular, $2^n \mid x_n$ and $2^n \mid y_n$, but still $x_n + y_n = 2^n$. The only way this can be is if $x_n = 0$ or $y_n = 0$.
Conversely, if $x_0 + y_0 \ne 2^n$ for any $n$, then there is some $n, m$ with $m > 1$ and odd, such that $x_0 + y_0 = 2^nm$. It will still be true that $2^n$ will divide both $x_n$ and $y_n$. However if you define $(s_0, t_0) = \left(\frac{x_n}{2^n}, \frac{y_n}{2^n}\right)$, then $s_0 + t_0 = m$, which is odd. Thus as you've noted, the sequence beginning with $(s_0, t_0)$ can never terminate. But for all $k$, $(x_{n+k}, y_{n+k}) = (2^ns_k, 2^nt_k)$, so that sequence cannot terminate either.
So a coprime pair $(x,y)$ will lead to a non-terminating sequence if and only if $x + y$ is not a power of $2$. More generally, any pair $(x,y)$ will produce a non-terminating sequence if and only if $\frac{x+y}{\gcd(x,y)}$ is not a power of $2$.
