Collatz Sequence – part 6

Proof of Collatz sequence convergence.

Some reminders first

Remember Collatz sequence definition

Let’s divide the Collatz sequence into two independent suites, for analysis convenience.
First suite ω is for numbers: ω_{n + 1} = 3 ω_n + 1
Second suite η is for numbers: η_{n + 1} = η_n / 2

Resolution for numbers from 2 to 11

resolution graph

First, let’s proceed to an exploratory analysis, and show results as a graph

computation

Doing computation, here is a summary for number 9, that covers all the cases for numbers between 2 and 11.

> cs(9)
 [1] 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

First important result
Therefore, by calculus, I proved that all the numbers from 2 to 11, provides 1 as final output of Collatz sequence.

Assumption

Let’s consider the Collatz sequence to be proven up to a given number z. This means that Collatz sequence is proven to be converging for any number m ∈ respecting m z.

Proof for any number e verifying z e 2z

As e is an number, then let’s apply η. The result of dividing by two is less than z, and therefore under the assumption stated above, is proven to be converging. Therefore any even number respecting z e 2z is proven to be a valid input for Collatz sequence to be converging.

Now that it is proven for number z e 2z, let’s repeat same reasoning with z’ = 2z. This proves that any number e respecting z’ e 2z’ converges. And so on, proving that any number converges.

Reasoning by recurrence, I got

1. first number that is 2 converges to 1 immediately, just applying η.
2. any number verifying z e 2z, whatever is z converges applying Collatz sequence.

Therefore,

Second important result
All the numbers, converges to 1 as final output of Collatz sequence.

Proof for any number o

Direct proof

As o is an number, then let’s apply ω. I already demonstrated that applying ω to and number provides an number. As I have proven here above, that any number brings convergence, therefore, all the numbers also bring convergence.

Calculus proof

As o is an number, it can be written as ah + bt +u. And as it is an number, then let’s apply ω and η.

starting number cs₁ = o = 2p + 1 = ah + bt +u
cs₃ = η(ω(s)) = η(ω(2p + 1)) = 3p + 2 = η(ω(ah + bt +u)) = (3ah + 3bt + (3u + 1)) / 2

Let’s focus on cs₃, when it outputs an number. From calculus, shown on previous table, the cases happen when cs₁ has a starting unit digit that is amongst , or . As we have previously proven that any number converges, this means that any number finishing with digit , or converges.

Now remain two cases, when cs₁ has a starting unit digit that is among or . Here, let’s apply again ω and η as those numbers are . Reusing previous table, the commutation will prove

• cs₁ cs₃ cs₅ number
• cs₁ cs₃ cs₅ number.

Again, as we have previously proven that any number converges, this means that any number finishing with digit or converges.

Third important result
All the numbers, converges to 1 as final output of Collatz sequence.

Summary

Simply put, I have proven

1. all the numbers from 2 to 11 converges to 1. Proven by calculus
2. all numbers converges to 1. Proven by recurrence
3. all numbers converges to 1. Proven by reusing numbers convergence, based on calculus.

Therefore, proof of Collatz sequence is achieved. Your comments, remarks and feebacks are welcome. Use comment zone to do so.

Note

All calculus done using R language.