# Mathematical Induction Divisibility Proofs

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 the step 2.

## Practice Questions of Mathematical Induction Divisibility

### Basic Mathematical Induction Divisibility

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

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.

### Related Topics

**Best Examples of Mathematical Induction Inequality**

**Mathematical Induction Fundamentals**

**Mathematical Induction Inequality Proof with Factorials**

**Mathematical Induction Inequality Proof with Two Initials**