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} \require{AMSsymbols} \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.
Algebra Algebraic Fractions Arc Binomial Expansion Capacity Common Difference Common Ratio Differentiation Double-Angle Formula Equation Exponent Exponential Function Factorials Factorise Functions Geometric Sequence Geometric Series Index Laws Inequality Integration Kinematics Length Conversion Logarithm Logarithmic Functions Mass Conversion Mathematical Induction Measurement Perfect Square Perimeter Prime Factorisation Probability Product Rule Proof Quadratic Quadratic Factorise Ratio Rational Functions Sequence Sketching Graphs Surds Time Transformation Trigonometric Functions Trigonometric Properties Volume
