# How can I prove that an iterated transformation describes all odd integers?

This is a question where I want to find "a best" way (or even different ways) to prove my assumption - just to widen my understanding of similar problems and how to approach them. It's a question of proof-strategy. (This is also related to my studies of the Collatz-problem)

Remark: this problem was less difficult than I thought it were, see my own answer. Regarding my question for a proof-strategy it is a nice example for how a tabular representation can obfuscate the problem and mislead the mind away from a relatively simple solution.

Consider the transformation on odd positive numbers $$x_{k+1} = \left\{ \begin{array} {} { 3x_k-1 \over 2} &\qquad \text{ if } x_k \equiv 1 \pmod 4 \\ { 3x_k+1 \over 2} &\qquad \text{ if } x_k \equiv -1 \pmod 4 \end{array} \right.$$ such that for instance the trajectory beginning at $5$ continues like $5 \to 7 \to 11 \to 17 \to \ldots$

Because the numbers of the form $x \equiv 3 \pmod 6$ have no preimage I take them as "roots" and order all trajectories in the following two-way infinite array of odd natural numbers $\ge 3$ : $$\small \begin{array} {r|rrrr} 3 & 5 & 7 & 11 & 17 & 25 & 37 & 55 & \cdots \\ 9 & 13 & 19 & 29 & 43 & 65 & 97 & 145 & \cdots \\ 15 & 23 & 35 & 53 & 79 & 119 & 179 & 269 & \cdots \\ 21 & 31 & 47 & 71 & 107 & 161 & 241 & 361 & \cdots \\ 27 & 41 & 61 & 91 & 137 & 205 & 307 & 461 & \cdots \\ 33 & 49 & 73 & 109 & 163 & 245 & 367 & 551 & \cdots \\ 39 & 59 & 89 & 133 & 199 & 299 & 449 & 673 & \cdots \\ 45 & 67 & 101 & 151 & 227 & 341 & 511 & 767 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array}$$ The number $1$ forms a cycle $1 \to 1$ and is not in this table.

It looks quite obvious, that I've got all positive odd numbers in this table, but now my question:

Q: How can I begin and proceed with a proof, that this table contains /that this transformation rule describes all positive odd integers $\ge 3$ ?

Remark: perhaps my question is not optimally formulated, I'd even like getting help for this

I tried, whether it is useful to reformulate the transformation in such a way: $$T: x_k = 4j + r \to x_{k+1}=6j +r \qquad \qquad \text{ for } j \ge 1 , r \in \{-1,1\}$$ then look at the inverse and ask, whether any number of the form $x=6j \pm 1$ under the inverse transform has a trajectory, which ends at a number of the form $3+6i$.

But I have no idea how to arrive at a so-to-say "completeness"-statement.

[update] after the comment of André Nicholas - ansatz transferred into a new answer

-
Your inverse transformation idea should do it. – André Nicolas Jul 6 '13 at 6:42
@André : I've got it now. It came out that for me it has been a problem of unnecessary complication, also known as "obfuscation" ... – Gottfried Helms Jul 6 '13 at 19:31
Yes, you go backwards until you can't do it any more. Must happen, since terms are decreasing (fast) and remain positive. – André Nicolas Jul 6 '13 at 19:35

Hint 1: What would be the smallest odd integer missing from the list?

Hint 2: You already made the observation that an odd integer $\not\equiv 3\pmod6$ has a preimage (that is smaller).

Hint 3: The empty set is the only set of positive odd integers that does not have a smallest element. Fermat's infinite descent was one of the first proofs by induction.

-
Hmm. At hint 1: such a number whose inverse trajectory does not arrive at a number of the form $3 + 6j$ ...? <arrggh> - I've actually no idea ... – Gottfried Helms Jul 6 '13 at 6:36
If it has a preimage smaller than itself, it cannot be the smallest missing number. So the smallest missing number cannot have a preimage at all, so... – Jyrki Lahtonen Jul 6 '13 at 6:45
Hmmm... it's immediate, that if a number $x_k$ has the form $x_k = 6j_k+r_k \qquad r_k \in \{-1,1\},j_k \gt 0$ then there exists a smaller number $x_{k+1} = 4j_k+r_k$. But for the next step we must either have $x_{k+1} = 6j_{k+1} + 3$ which is then a root without further preimage or we must have $x_{k+1} = 6j_{k+1} + r_{k+1} = 4j_k+r_k$ where $j_{k+1} \lt j_k$ . So now one more step ... – Gottfried Helms Jul 6 '13 at 7:58
So you can prove that there is no smallest counterexample. So the set of counterexamples has to be empty. That's the essence of induction! – Jyrki Lahtonen Jul 6 '13 at 11:11
Yes. I've got it now. I recognize now my main problem in that I was obfuscated/mislead by the two-dimensional structure of the table and that I could not intuitively exclude the idea, that in one row the proceeding from the right to the left could perhaps jump between two of the 3-divisible roots. $\\$ Omitting the vizualisation by the table, considering simply the set of consecutive odd numbers with one lowest number makes the solution obvious. I'll add that insight in terms of an extra answer later. Thanks for your hints! – Gottfried Helms Jul 6 '13 at 18:47

You can show by induction that every odd number greater than $1$ is in your table :

If $n = 6k+3$ then $n$ is a root.
If $n = 6k+5$ then $n = T(4k+3)$, and $1 < 4k+3 < 6k+5$.
If $n = 6k+7$ then $n = T(4k+5)$, and $1 < 4k+5 < 6k+7$.

-
Hmm, I don't see the induction... Perhaps I'm completely dense at the moment and should take a break first... – Gottfried Helms Jul 6 '13 at 6:38

We consider the odd numbers $x \ge 3$ . Any of that numbers can be written as $x = 6j - 3$ or $x=6j-1$ or $x=6j+1$ with $j \gt 0$ .

We define the inverse transformation in the following way:

we pick some $x_0$.

• Case 1: if $x_0$ is of the form $x=6j -3$ we have that number in our table as a "root" entry.

• Case 2: if $x_0$ is of the form $x=6j +r$ where $r \in \{-1,1\}$ we transform that number according to

$\qquad U: x_k = 6j_k + r_k \to x_{k+1} = 4 j_k+r_k$

Because $x_{k+1}$ is again odd, it is again $x_{k+1} = 4 j_k+r_k = 6j_{k+1} + r_{k+1}$ and of one of the two Cases and we can repeat:

• Case 1: if it is of the form $x_{k+1} = 6j_{k+1} - 3$ we have again, that it is in the table, and with it all numbers $x_0 \ldots x_k$ in between.

• Case 2a: if $j_k >1$ we have $x_{k+1} = 4j_k + r_k$ and the smallest of that numbers is with $j_k = 2$ the number $x_{k+1} = 4 \cdot 2 -1 = 7 = 6 \cdot 1 +1$ such that $j_{k+1}=1$

• Case 2b: And if finally $j_k =1$ we have either
$\qquad \qquad x_{k+1} = 4\cdot 1 -1 = 3$ and this is in the table and closes the trajectory or we have
$\qquad \qquad x_{k+1} = 4 \cdot 1 +1 = 5$ and this transforms to $x_{k+2}=3$ which then closes again the trajectory.

Because all trajectories end on some number which is divisible by 3 and these numbers are in the table by definition together with all of their preimages, the given table contains all odd natural numbers $x \ge 3$ .

(I think the way of arguing and the formalism should be improvable, please point out any error or weakness...)

-