Mathematical Induction Divisibility can be used to prove divisibility, such as divisible by 3, 5 etc. Same as Mathematical Induction Fundamentals, hypothesis/assumption is also made at step 2.

## Basic Mathematical Induction Divisibility

Prove \( 6^n + 4 \) is divisible by \( 5 \) by mathematical induction, for \( n \ge 0 \).

Step 1: Show it is true for \( n=0 \).

\( 6^0 + 4 = 5 \), which is divisible by \(5\)

Step 2: Assume that it is true for \( n=k \).

That is, \( 6^k + 4 = 5M \), where \( M \in I \).

Step 3: Show it is true for \( n=k+1 \).

That is, \( 6^{k+1} + 4 = 5P \), where \( P \in I \).

\( \begin{aligned} \displaystyle \require{color}

6^{k+1} + 4 &= 6 \times 6^k +4 \\

&= 6 (5M – 4) + 4 \ \ \ \color{red} 6^k = 5M – 4 \ \ \ \ \text{ by Step 2} \\

&= 30M – 20 \\

&= 5(6M-4), \text{ which is divisible by 5} \\

\end{aligned} \)

Therefore it is true for \( n=k+1 \) assuming that it is true for \( n=k \).

Therefore \( 6^n + 4 \) is always divisible by \(5\).

## Increasing More Than One

Prove \( n(n+2) \) is divisible by \( 4 \) by mathematical induction, if \(n\) is any even positive integer.

Step 1: Show it is true for \( n=2 \). \( \require{color} \color{red} \ \ \text{ 2 is the smallest even number.} \)

\( 2(2+2) = 8\), which is divisible by 4.

Therefore it is true for \(n=2\).

Step 2: Assume that it is true for \( n=k \).

That is, \( k(k+2) = 4M \).

Step 3: Show it is true for \( n=k+2 \). \( \require{color} \color{red} \ \ \text{ Even numbers increase by 2.} \)

That is, \( (k+2)(k+4) \) is divisible by 4.

\( \begin{aligned} \displaystyle

(k+2)(k+4) &= (k+2)k + (k+2)4 \\

&= 4M + 4(k+2) \color{red} \ \ \text{ by assumption at Step 2} \\

&= 4\big[M + (k+2)\big] \color{red} \text{, which is divisible by 4} \\

\end{aligned} \)

Therefore it is true for \( n=k+2 \) assuming that it is true for \( n=k \).

Therefore \( n(n+2) \) is always divisible by \( 4 \) for any even numbers.

## Two Indices

Prove \( 5^n + 2 \times 11^n \) is divisible by \( 3 \) by mathematical induction.

Step 1: Show it is true for \( n=0 \). \( \require{color} \color{red} \ \ \text{ 0 is the first number for being true.} \)

\( 5^0 + 2 \times 11^0 = 3 \), which is divisible by \( 3 \).

Therefore it is true for \(n=0\).

Step 2: Assume that it is true for \( n=k \).

That is, \( 5^k + 2 \times 11^k = 3M \).

Step 3: Show it is true for \( n=k+1 \).

That is, \( 5^{k+1} + 2 \times 11^{k+1} \) is divisible by \( 3 \).

\( \begin{aligned} \displaystyle \require{color}

5^{k+1} + 2 \times 11^{k+1} &= 5^{k+1} + 2 \times 11^k \times 11 \\

&= 5^{k+1} + (3M-5^k) \times 11 \ \ \ \ \color{red} 2 \times 11^k = 3M – 5^k \ \ \ \text{ by assumption at Step 2} \\

&= 5^k \times 5 +33M – 5^k \times 11 \\

&= 33M – 5^k \times 6 \\

&= 3(11M – 5^k \times 2), \text{ which is divisible by 3} \\

\end{aligned} \)

Therefore it is true for \( n=k+1 \) assuming that it is true for \( n=k \).

Therefore \( 5^n + 2 \times 11^n \) is always divisible by \( 3 \) for \(n \ge 0\).

## Three Indices

Prove \( 4^n + 5^n + 6^n \) is divisible by \( 15 \) by mathematical induction, where \(n\) is odd integer.

Step 1: Show it is true for \( n=1 \). \( \require{color} \color{red} \ \ \text{ 1 is the smallest odd number.} \)

\( 4^1 + 5^1 + 6^1 = 15 \), which is divisible by \( 15 \).

Therefore it is true for \(n=1\).

Step 2: Assume that it is true for \( n=k \).

That is, \( 4^k + 5^k + 6^k = 15M \).

Step 3: Show it is true for \( n=k+2 \). \( \require{color} \color{red} \ \ \text{ Odd numbers increase by 2.} \)

That is, \( 4^{k+2} + 5^{k+2} + 6^{k+2} \) is divisible by \( 15 \).

\( \begin{aligned} \displaystyle \require{color}

4^{k+2} + 5^{k+2} + 6^{k+2} &= 4^k \times 4^2 + 5^k \times 5^2 + 6^k \times 6^2 \\

&= (15M – 5^k – 6^k) \times 4^2 + 5^k \times 5^2 + 6^k \times 6^2 \\

&= 240M – 16 \times 5^k – 16 \times 6^k + 25 \times 5^k + 36 \times 6^k \\

&= 240M + 9 \times 5^k + 20 \times 6^k \\

&= 240M + 9 \times 5 \times 5^{k-1} + 20 \times 6 \times 6^{k-1} \\

&= 240M + 45 \times 5^{k-1} + 120 \times 6^{k-1} \\

&= 15\big[16M + 3 \times 5^{k-1} + 8 \times 6^{k-1}\big], \text{ which is divisible by 15} \\

\end{aligned} \)

Therefore it is true for \( n=k+2 \) assuming that it is true for \( n=k \).

Therefore \( 4^n + 5^n + 6^n \) is always divisible by \( 15 \) for all odd integers.

Absolute Value Algebra Algebraic Fractions Arithmetic Sequence Binomial Expansion Chain Rule Circle Geometry Common Difference Common Ratio Compound Angle Formula Compound Interest Cyclic Quadrilateral Differentiation Discriminant Double-Angle Formula Equation Exponent Exponential Function Factorials Factorise Functions Geometric Sequence Geometric Series Inequality Integration Kinematics Logarithm Logarithmic Functions Mathematical Induction Perfect Square Prime Factorisation Probability Product Rule Proof Quadratic Quadratic Factorise Quotient Rule Rational Functions Sequence Sketching Graphs Surds Transformation Trigonometric Functions Trigonometric Properties Volume