Question

Доказать, что n! не делится на 2^n (n>=1)

Answer 1

Сравним степени вхождения двойки в $2^n$ и $n!$. В первом случае, очевидно, $v_{2}(2^{n})=n$. Во втором: $v_{2}(n!)=\sum\limits_{i=1}^{\infty}[\frac{n}{2^{i}}]< \sum\limits_{i=1}^{\infty}\frac{n}{2^{i}}=n$. Поэтому $2^{n} \nmid n!$

Answer 2

Давайте докажем данное утверждение методом математической индукции. Мы будем доказывать, что для всех целых чисел n >= 1, выполняется неравенство n! > 2^n.

Базовый случай (n = 1): При n = 1, левая часть равна 1!, что равно 1, а правая часть равна 2^1, что также равно 2. Очевидно, что 1 > 2 не выполняется.

Индукционное предположение: Предположим, что для некоторого целого числа k >= 1 выполняется неравенство k! > 2^k.

Индукционный переход: Теперь докажем, что если для k выполняется неравенство k! > 2^k, то оно также выполняется и для k+1.

Рассмотрим выражение (k+1)!: (k+1)! = (k+1) * k!

Так как по индукционному предположению мы знаем, что k! > 2^k, то мы можем записать: (k+1)! = (k+1) * k! > (k+1) * 2^k

Мы можем заметить, что (k+1) * 2^k больше, чем 2 * 2^k, так как k+1 >= 2 (при k >= 1).

Таким образом, (k+1)! > 2 * 2^k = 2^(k+1), что означает, что неравенство выполняется и для k+1.

Таким образом, мы доказали, что если неравенство k! > 2^k выполняется для некоторого k >= 1, то оно также выполняется для k+1.

С учетом базового случая и индукционного перехода, мы можем заключить, что неравенство n! > 2^n выполняется для всех целых чисел n >= 1. Это означает, что n! не делится на 2^n для всех n >= 1.