# 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.