Best Examples of Mathematical Induction Divisibility

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