Indukcja matematyczna - nierówność n! > 2ⁿ dla n ≥ 4

Krok 1. Szukamy bazy i ją sprawdzamy. Porównujemy kolejne wartości:

• $n = 1$: $1! = 1$, $2^1 = 2$ - nierówność fałszywa,
• $n = 2$: $2! = 2$, $2^2 = 4$ - fałszywa,
• $n = 3$: $3! = 6$, $2^3 = 8$ - fałszywa,
• $n = 4$: $4! = 24$, $2^4 = 16$ - prawdziwa.

Zatem $n_0 = 4$ i baza indukcji jest sprawdzona: $24 > 16$.

Krok 2. Założenie i teza. Zakładamy, że dla pewnego $k \ge 4$ zachodzi $k! > 2^k$. Teza: $(k + 1)! > 2^{k + 1}$.

Krok 3. Dowód kroku. Z definicji silni i z założenia:

$(k + 1)! = (k + 1) \cdot k! > (k + 1) \cdot 2^k.$

Ponieważ $k \ge 4$, mamy $k + 1 \ge 5 > 2$, więc

$(k + 1) \cdot 2^k > 2 \cdot 2^k = 2^{k + 1}.$

Łącząc obie nierówności, dostajemy $(k + 1)! > 2^{k + 1}$.

Odpowiedź. Najmniejsze takie $n$ to $n_0 = 4$, a na mocy zasady indukcji matematycznej $n! > 2^n$ dla każdego $n \ge 4$. Zauważ, że w kroku wystarczyłoby $k + 1 > 2$ - trudność leży w bazie, nie w kroku.