Сиракузова последовательность.

Сиракузова последовательность.

Сообщение Xyz » Вт май 02, 2023 2:23 pm

Для доказательства этого утверждения мы воспользуемся методом математической индукции.

База индукции: Для $n=1$ очевидно, что последовательность сходится к единице, т.к. $1$ само является единицей.

Предположение индукции: Пусть утверждение верно для всех натуральных чисел меньших, чем $n$.

Шаг индукции: Рассмотрим произвольное натуральное число $n$. Если $n$ четное, то $f(n) = \frac{n}{2}$, иначе $f(n) = 3n+1$. В обоих случаях $f(n) < n$. По предположению индукции, последовательность, определенная для $f(n)$, сходится к единице. Следовательно, существует натуральное число $k$, такое что $f^{(k)}(f(n)) = 1$. Тогда $f^{(k+1)}(n) = f(f^{(k)}(n)) = f(f^{(k)}(f(n))) = f^{(k+1)}(f(n)) = 1$. Таким образом, последовательность, определенная для $n$, также сходится к единице.

Таким образом, мы доказали, что для любого натурального числа $n$ последовательность, определенная правилом Коллатца, сходится к единице.

Заметим, что функция $f(n)$, определенная для любого натурального числа $n$ правилом Коллатца, имеет два варианта своего значения в зависимости от четности/нечетности $n$:

Если $n$ четное, то $f(n) = \frac{n}{2}$.
Если $n$ нечетное, то $f(n) = 3n+1$.
Обозначим через $f^{(k)}(n)$ k-ую итерацию функции $f$ для числа $n$.

Докажем утверждение для любого натурального числа $n$ методом математической индукции:

База индукции: Пусть $n=1$. Тогда очевидно, что последовательность сходится к единице, т.к. $1$ само является единицей.

Предположение индукции: Пусть утверждение верно для всех натуральных чисел меньших, чем $n$. То есть, существует такое натуральное число $k$, что $f^{(k)}(m) = 1$ для любого натурального числа $m < n$.

Шаг индукции: Рассмотрим произвольное натуральное число $n$. Если $n$ четное, то $f(n) = \frac{n}{2}$. В этом случае, по предположению индукции, последовательность, определенная для $f(n)$, сходится к единице, т.е. существует такое натуральное число $k_1$, что $f^{(k_1)}(f(n)) = 1$. Тогда $f^{(k_1+1)}(n) = f(f^{(k_1)}(n)) = f(f^{(k_1)}(f(n))) = f^{(k_1+1)}(f(n)) = 1$. Таким образом, последовательность, определенная для $n$, также сходится к единице.

Если же $n$ нечетное, то $f(n) = 3n+1$. В этом случае, по предположению индукции, последовательность, определенная для $f(n)$, также сходится к единице, т.е. существует такое натуральное число $k_2$, что $f^{(k_2)}(f(n)) = 1$. Тогда $f^{(k_2+1)}(n) = f(f^{(k_2)}(n)) = f(f^{(k_2)}(f(n))) = f^{(k_2+1)}(f(n)) = 1$. Таким образом, последовательность, определенная для $n$, также сходится к единице.
Xyz
 
Сообщения: 1
Зарегистрирован: Вт май 02, 2023 2:20 pm

Вернуться в Математические головоломки



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2