Indukcja matematyczna - podzielność 8ⁿ − 1 przez 7

Krok 1. Sprawdzenie dla n = 1 (baza). $8^1 - 1 = 7$, a $7$ dzieli się przez $7$.

Krok 2. Założenie i teza. Zakładamy, że dla pewnego $k \ge 1$ liczba $8^k - 1$ dzieli się przez $7$, czyli $8^k - 1 = 7m$ dla pewnej liczby całkowitej $m$. Teza: $7 \mid 8^{k + 1} - 1$.

Krok 3. Dowód kroku. W wyrażeniu dla $k + 1$ „wyciągamy” wyrażenie z założenia:

$8^{k + 1} - 1 = 8 \cdot 8^k - 1 = 8 \cdot 8^k - 8 + 7 = 8\left(8^k - 1\right) + 7.$

Podstawiamy $8^k - 1 = 7m$:

$8^{k + 1} - 1 = 8 \cdot 7m + 7 = 7(8m + 1).$

Liczba $8m + 1$ jest całkowita, więc $8^{k + 1} - 1$ dzieli się przez $7$.

Odpowiedź. Na mocy zasady indukcji matematycznej $7 \mid 8^n - 1$ dla każdego $n \ge 1$.

Sztuczka „odejmij i dodaj” ($-8 + 7$) to standardowy ruch w dowodach podzielności: chodzi o to, żeby w wyrażeniu dla $k + 1$ pojawiło się wyrażenie z założenia. Ten sam wynik daje też wzór $a^n - b^n = (a - b)(a^{n-1} + \ldots + b^{n-1})$ dla $a = 8$, $b = 1$.