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

Question

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

Answer 1

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.

Answer 2

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$.

Answer 3

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...)