ТерминологияДавайте определимся, что под шагом рекурсии (шагом итерации):

мы подразумеваем два правила: 1/3 и

.
Под термином "отдельная ветка", мы подразумеваем последовательность чисел следующих друг за другом по правилу 1/3.
Как только такая последовательность достигает

, ветка заканчивается.
Переход числа в ветку

- это всегда новая ветка.
Под рекурсией

мы будем подразумевать все возможные итерации с бесконечными вариациями и ответвлениями по правилу 1/3 и

, а также всю их совокупность на любом шаге. В математике этот вид рекурсии называется возвратная, или рекурсия с пробегом.
Далее, мы соглашаемся, что гипотеза Коллатца

- это развернутая в обратном направлении рекурсия

.
Если да, то нам уже не нужно больше ничего доказывать. Почему? Потому что это рекурсия. Она начинается с единицы. Развернув ее в обратную сторону у нас нет другого варианта, как снова спуститься к 1.
Но мы спросим: А есть ли такое число, которое не входит в рекурсию

?
Предположим, что есть. Но тогда из этого следует, что его нельзя подставить в

. Потому что

- это уже сформированная рекурсия от

.
Что я пытаюсь вам сказать? А вот, что! Коллатц предложил нам головоломку

, не сказав, что мы уже, как зверь в клетке, вступили на поле рекурсии.
Вопрос Коллатца: Есть ли такое число, которое не рождено единицей?
Ответ: Нет.
ДоказательствоДля любого нечетного числа, уже начиная с 1, мы можем применить правила 1/3 и

.
Таким образом, нет такого числа, к которому мы не могли бы применить эти правила.
Развернув эти правила в обратную сторону, мы получим единицу.
Эти правила – часть рекурсии. Это означает, что любое нечетное число можно представить как рекурсию из других чисел.
Акцентирую! Всего один раз применив

и

мы уже находимся в рекурсии. Ч.т.д.