אינדוקציה: הוכחת התחלקות

דוגמה: נוכיח ש-$5^n - 1$ מתחלק ב-4 לכל n טבעי.
בסיס: $5^1 - 1 = 4$, שמתחלק ב-4.
הנחה: מניחים ש-$5^k - 1$ מתחלק ב-4.
מעבר: $5^{k+1} - 1 = 4 \cdot 5^k + (5^k - 1)$.
שני האיברים מתחלקים ב-4, לכן גם הסכום מתחלק ב-4.

מציבים $n = 1$ בביטוי ומחשבים את התוצאה.
בודקים שהתוצאה מתחלקת במחלק ללא שארית.
לדוגמה עבור $5^n - 1$: מציבים ומקבלים 4, שמתחלק ב-4.
לדוגמה עבור $8^n - 8$: מציבים ומקבלים 0, שמתחלק ב-7.

המגמה: לכתוב את מקדם החזקה כסכום שמכיל את המחלק, כדי לבודד את ביטוי ההנחה.
לדוגמה: $5 \cdot 5^k - 1 = (4+1) \cdot 5^k - 1 = 4 \cdot 5^k + (5^k - 1)$.
הביטוי $4 \cdot 5^k$ מתחלק ב-4 בבירור.
הביטוי $5^k - 1$ מתחלק ב-4 לפי ההנחה.

כותבים שקיבלנו שני ביטויים שכל אחד מהם מתחלק ב-4, לכן גם סכומם מתחלק ב-4.
מסיימים: הוכחנו שאם הטענה נכונה עבור $n = k$.
אזי היא נכונה גם עבור $n = k+1$, לכן היא נכונה לכל n טבעי.

ממירים לטענת התחלקות: שארית r שקולה לכך שהביטוי פחות r מתחלק ב-m.
לדוגמה: חלוקת $8^n - 5$ ב-7 נותנת שארית 3.
ממירים ומוכיחים ש-$8^n - 8$ מתחלק ב-7.
הבסיס: $8^1 - 8 = 0$ מתחלק ב-7.