Inductive Proofs for Divisibility Results

We will now look at how mathematical induction can be used to prove a number of divisibility results.

Often the tricky part is to algebraically manipulate the assumption $A_k$Ak​ into the $A_k\Rightarrow A_{k+1}$Ak​⇒Ak+1​ part of the proof. You'll see what this means in the first example:

 

Example 1:

Prove that $8^n-3^n$8n−3n, for $n$n a positive integer, is always divisible by $5$5.

Checking the truth of the assertion for $n=1$n=1, the expression $8^n-3^n$8n−3n becomes $8^1-3^1=5$81−31=5, and thus is clearly divisible by $5$5.

Before we proceed further, we note that if the expression $8^n-3^n$8n−3n is divisible by $5$5, then we must be able to write down the equation $8^n-3^n=5p$8n−3n=5p, where $t$t is some integer. Going the other way, if we can write an equation like $8^n-3^n=5p$8n−3n=5p, then we know that $8^n-3^n$8n−3n is divisible by $5$5. 

Assuming $A_k:$Ak​:

If we assume that, for some $k$k, $8^k-3^k$8k−3k is divisible by $5$5, then we can write (and use in our proof) the equation $8^k-3^k=5p$8k−3k=5p.

To prove $A_{k+1}:$Ak+1​:

We need to prove that $8^{k+1}-3^{k+1}$8k+1−3k+1 is also divisible by $5$5.

Now look carefully at lines $3$3 and $4$4, where we manipulate the expression to incorporate the assumption $A_k$Ak​:

$8^{k+1}-3^{k+1}$8k+1−3k+1	$=$=	$8^k\times8^1-3^k\times3^1$8k×81−3k×31
	$=$=	$8\times8^k-3\times3^k$8×8k−3×3k
	$=$=	$\left(8\times8^k-8\times3^k\right)+5\times3^k$(8×8k−8×3k)+5×3k
	$=$=	$8\left(8^k-3^k\right)+5\left(3^k\right)$8(8k−3k)+5(3k)
	$=$=	$8\left(5p\right)+5\left(3^k\right)$8(5p)+5(3k)
	$=$=	$5q$5q

Note that each part of $8\left(5p\right)+5\left(3^k\right)$8(5p)+5(3k) is divisible by $5$5, which means that the entire expression is divisible by $5$5. This explains the very last line, with $q$q being some integer.

Therefore if it is true for $n=k$n=k, then it is also true for $n=k+1$n=k+1. Since it is true for $n=1$n=1, it is also true for $n=2$n=2, and in turn for $n=3$n=3 etc. Therefore it is true for all $n$n.  

Dropping the formalities

Often with inductive proofs, we drop the formality of naming the assertions $A_1,A_k,A_{k+1}$A1​,Ak​,Ak+1​ etc, and simply show that we are substituting $n=1$n=1, $n=k$n=k, $n=k+1$n=k+1 etc into the given expression. We do however continue to show all three steps in the manner shown with example $2$2.

 

Example 2

Prove that, for $n$n a positive integer, $x^n-1$xn−1 is divisible by $\left(x-1\right)$(x−1).

Clearly when $n=1$n=1, $x^1-1$x1−1 is divisible by $\left(x-1\right)$(x−1).

Also, when $n=2$n=2 we have $x^2-1=\left(x-1\right)\left(x+1\right)$x2−1=(x−1)(x+1) and is therefore divisible by $(x-1)$(x−1).

Assume, for $n=k$n=k, $x^k-1$xk−1 is divisible by $\left(x-1\right)$(x−1), so that  $x^k-1=P\left(x\right)\times\left(x-1\right)$xk−1=P(x)×(x−1), where $P\left(x\right)$P(x) is some polynomial in $x$x.

We need to prove that $x^{k+1}-1$xk+1−1 is also divisible by $\left(x-1\right)$(x−1).

Thus:

$x^{k+1}-1$xk+1−1	$=$=	$x\left(x^k\right)-1$x(xk)−1
	$=$=	$x\left(x^k\right)-x+x-1$x(xk)−x+x−1
	$=$=	$x\left(x^k-1\right)+\left(x-1\right)$x(xk−1)+(x−1)

Now, by our assumption, $\left(x^k-1\right)=P\left(x\right)\left(x-1\right)$(xk−1)=P(x)(x−1) so that:

$x^{k+1}-1$xk+1−1	$=$=	$xP\left(x\right)\left(x-1\right)+\left(x-1\right)$xP(x)(x−1)+(x−1)
	$=$=	$\left(x-1\right)\left[xP\left(x\right)+1\right]$(x−1)[xP(x)+1]

 This is clearly divisible by $\left(x-1\right)$(x−1).

Since it is true for $n=1$n=1, it is also true for $n=2$n=2, and in turn for $n=3$n=3 etc. Therefore it is true for all $n$n. 

 

Example 3

Prove that $3^{3n}+2^{n+2}$33n+2n+2 is divisible by $5$5.

Checking $n=1$n=1, we have $3^3+2^3=35$33+23=35, and $35$35 is divisible by $5$5

Assume it is true for $n=k$n=k. That is to say, $3^{3k}+2^{k+2}=5p$33k+2k+2=5p where $p$p is an integer.

We need to prove that $3^{\left[3\left(k+1\right)\right]}+2^{\left(k+1\right)+2}$3[3(k+1)]+2(k+1)+2 is divisible by $5$5.

This means, after a simplification, we need to prove that $3^{3k+3}+2^{k+3}$33k+3+2k+3 is divisible by $5$5.

Hence:

$3^{3k+3}+2^{k+3}$33k+3+2k+3	$=$=	$27\times3^{3k}+2\times2^{k+2}$27×33k+2×2k+2
	$=$=	$25\times3^{3k}+2\times3^{3k}+2\times2^{k+2}$25×33k+2×33k+2×2k+2
	$=$=	$25\times3^{3k}+2\left(3^{3k}+2^{k+2}\right)$25×33k+2(33k+2k+2)
	$=$=	$25\times3^{3k}+2\left(5p\right)$25×33k+2(5p)
	$=$=	$5\left[5\left(3^{3k}\right)+2p\right]$5[5(33k)+2p]
	$=$=	$5q$5q

Thus we have shown that the expression $3^{3k+3}+2^{k+3}$33k+3+2k+3 is divisible by $5$5.

Since it is true for $n=1$n=1, it is also true for $n=2$n=2, and in turn for $n=3$n=3 etc. Therefore it is true for all $n$n.