2

Terras (via Lagarias) has a method explained here (2.2) for finding the kth term of any Collatz sequence (that is)

$$T(n) = \frac{3n+1}{2}$$ if n is odd and

$$=\frac n2$$ if n is even. The lambda term makes perfect sense as the factor by which n has been increased or decreased, but what is the p(n) term? What does it signify, and how does one prove that this equation yields $T^k(n)$?

Ralph
  • 21
  • The description in the post is misleading. Terras only gives a relation between the $k$-th term of Collatz sequence and the parity sequence $(x_0,x_1,...)$. This is not a method to determine the $k$-th term because the parity sequence cannot be determined before computing out the Collatz sequence. – Zelox Feb 10 '22 at 11:38

1 Answers1

2

$\rho$ is the contribution of all the +1 terms.

For reference, the relevant equations are: $$ T^{(k)}(n) = \lambda_k (n) n + \rho_k(n) $$

$$ \lambda_k(n) = \frac{3^{x_0(n) + \cdots + x_{k-1}(n)}}{2^k} $$

$$ \rho_k(n) = \sum_{i=0}^{k-1} x_i(n) \frac{3^{x_{i+1}(n)+\cdots+x_{k-1}(n)}}{2^{k-i}} $$

Where $x_i(n)$ is defined as $$ T^{(i)}(n) \equiv x_i(n) \mod 2 $$

E.g. in the case of $n=3$, $T^{(1)}(3) = 5$ and $T^{(2)}(3) = 8$, which are broken down as: $$ T^{(1)}(3) = \frac{3}{2} \times 3 + \frac{1}{2} $$ $$ T^{(2)}(3) = \frac{9}{4} \times 3 + \left( \frac{3}{4} + \frac{1}{2} \right) $$

Sketch of inductive step in a proof by induction on $k$:

$$ T^{(k)}(n) = \frac{3^{x_{k-1}(n)}}{2}( T^{(k-1)}(n) + x_{k-1}(n) ) =\\= \frac{3^{x_{k-1}(n)}}{2}(\lambda_{k-1}(n) + \rho_{k-1}(n) + x_{k-1}(n) ) =\\ =\lambda_k(n) + \frac{3^{x_{k-1}(n)}}{2} ( \rho_{k-1}(n) + x_{k-1}(n) ) $$ Giving $$ \rho_k(x) = \frac{3^{x_{k-1}(n)}}{2}( x_{k-1}(n) + \rho_{k-1}(n) ) = \\ = x_{k-1}(n) \frac{3^{x_{k-1}(n)}}{2} + \sum_{i=0}^{k-2} x_i(n) \frac{3^{x_{i+1}(n)+\cdots+x_{k-1}(n)}}{2^{k-i}} = \\ = \sum_{i=0}^{k-1} x_i(n) \frac{3^{x_{i+1}(n)+\cdots+x_{k-1}(n)}}{2^{k-i}} $$

trutheality
  • 1,042