Indukcja matematyczna - podzielność 10ⁿ + 3·4ⁿ⁺² + 5 przez 9

Krok 1. Sprawdzenie dla n = 1 (baza).

$f(1) = 10 + 3 \cdot 4^3 + 5 = 10 + 192 + 5 = 207 = 9 \cdot 23.$

Liczba $f(1)$ dzieli się przez $9$.

Krok 2. Założenie i teza. Zakładamy, że $9 \mid f(k)$ dla pewnego $k \ge 1$. Teza: $9 \mid f(k + 1)$.

Krok 3. Dowód kroku. Tym razem wygodniej policzyć różnicę $f(k + 1) - f(k)$:

$f(k + 1) - f(k) = \left(10^{k + 1} - 10^k\right) + 3\left(4^{k + 3} - 4^{k + 2}\right) + (5 - 5).$

Każdy nawias upraszczamy, wyłączając mniejszą potęgę:

$10^{k + 1} - 10^k = 10^k(10 - 1) = 9 \cdot 10^k, \qquad 3\left(4^{k + 3} - 4^{k + 2}\right) = 3 \cdot 4^{k + 2} \cdot 3 = 9 \cdot 4^{k + 2}.$

Zatem

$f(k + 1) = f(k) + 9\left(10^k + 4^{k + 2}\right).$

Pierwszy składnik dzieli się przez $9$ z założenia, drugi jest wielokrotnością $9$, więc $9 \mid f(k + 1)$.

Odpowiedź. Na mocy zasady indukcji matematycznej $9 \mid 10^n + 3 \cdot 4^{n+2} + 5$ dla każdego $n \ge 1$.

Metoda różnicy działa dobrze, gdy wyrażenie jest sumą kilku potęg: zamiast żonglować jednym wielkim wyrażeniem, pokazujemy, że przyrost przy przejściu od $k$ do $k + 1$ dzieli się przez $9$.