Challenge: prove that if x is in a cycle of length n, then x < 2^n
For some notational consistency:
Use the shortcut odd step: T(x) = {x/2, even; (3x+1)/2, odd}
Let the number of steps be n, and the number of odd steps be m.
If x follows a given parity sequence (example: EOEOOEE), then
- kᵢ are the indices of the odd steps (example: [1,3,4]), and
- S = ∑2^(kᵢ)3^(m-1-i) from i=0 to m-1 (example: 2^(1)3^(2) + 2^(3)3^(1) + 2^(4)3^(0))
- So, T^(n)(x) = (3^(m)x + S)/2^(n)
Per a proof in a stackexchange answer, the title claim is true, but can you prove it?