Мы можем доказать неравенство ( 2^n > n ) для всех целых ( n \geq 1 ) методом математической индукции.
Шаг 1: База индукции
Для ( n = 1 ):
[
2^1 = 2 > 1
]
База индукции выполнена.
Шаг 2: Индукционные предположение
Предположим, что неравенство верно для некоторого ( n = k ), то есть:
[
2^k > k
]
Шаг 3: Индукционный шаг
Теперь нужно показать, что неравенство верно для ( n = k + 1 ):
[
2^{k+1} > k + 1
]
Мы можем переписать левую часть:
[
2^{k+1} = 2 \cdot 2^k
]
По нашему индукционному предположению:
[
2^{k+1} > 2k
]
Для завершения доказательства нам нужно показать, что:
[
2k > k + 1
]
Это равносильно неравенству:
[
2k - k > 1 \quad \Rightarrow \quad k > 1
]
Таким образом, если ( k > 1 ), то неравенство верно. Проверим случай ( k = 1 ) (по базовому случаю) и ( k = 2 ):
Для ( k = 2 ):
[
2^2 = 4 > 2
]
И для ( k = 3 ):
[
2^3 = 8 > 3
]
Таким образом, для ( k \geq 1 ) неравенство выполняется.
Шаг 4: Заключение
Мы доказали, что если неравенство ( 2^k > k ) верно для некоторого ( k ), то оно также верно для ( k + 1 ). Поскольку база индукции верна, неравенство ( 2^n > n ) выполняется для всех целых ( n \geq 1 ).
