Proof by Induction: Divisibility

Let's look at an example of Proof by Induction with 'divisibility'.

Example

We want to prove that $2^{5n}-2^{n}{\text{ is divisible by 60 for }}n\in \mathbb {N} ,n\geq 2$.

As usual with proof by induction, we'll need:

• a base case
• an induction step
• a conclusion

Divisibility Notation

We are considering the statement: "$2^{5n}-2^{n}$ is divisible by 60".

Since the statement is given in words, "... is divisible by 60", I would prefer to reflect the same use of language, and I'll talk about divisibility using the same words.

There is notation for divisibility that can be used instead. You would say:

$60|2^{5n}-2^{n}$

The pipe symbol, a perfectly vertical line, is representing the idea of divisibility here. You can read $|$ out loud as the word "divides", and say "60 divides $2^{5n}-2^{n}$".

All of these statements are equivalent ways of saying the same thing, remembering that we are talking here about integers:

• 60 divides $2^{5n}-2^{n}$,
• 60 is a factor of $2^{5n}-2^{n}$,
• 60 is a divisor of $2^{5n}-2^{n}$,
• 60 goes into $2^{5n}-2^{n}$ perfectly,
• $2^{5n}-2^{n}$ is divisible by 60,
• $2^{5n}-2^{n}$ is a multiple of 60,
• $2^{5n}-2^{n}$ is in the 60-times table,
• $2^{5n}-2^{n}=60k$.

When we say $a|b$, you might expect that $a\leq {}b$. You can imagine that the times table goes $a,2a,3a,4a,...$, and $b$ must be one of these. But, be careful about this, since it is not exactly true: $0$ is in the 60-times table, and so is $-60,-120,$ and so on.

When trying to prove that something is divisible by 60, it can be nice to take out a factor of 60, explicitly showing that every term (as you have written it) is divisible by 60.

Proof by Induction

$2^{5n}-2^{n}{\text{ is divisible by 60 }}(*){\text{ for }}n\in \mathbb {N} ,n\geq 2$

Base Case

Note! The proof asks us to start with $n=2$.

In fact, the statement is not true for $n=1$, so we can't have a base case of $n=1$: our whole proof will collapse, like the bottom of a house of cards. We have to start our base case with $n=2$, and then our proof will build from there.

Consider $n=2$.

${\begin{aligned}2^{5n}-2^{n}&=2^{10}-2^{2}\\&=1024-4\\&=1020\\&=60\times 17{\text{ which is divisible by 60}}\end{aligned}}$

This proves that $(*)$ is true for the "base case" of $n=2$.

When writing this out for an examiner, you'll notice that:

• I have explicitly taken out a factor of 60, and,
• I wrote "which is divisible by 60", reflecting the language of the question and completing the statement in the same way as $(*)$.

Induction Step

In this step, we forget about $n=2$ and focus on the general idea: if we know the statement is true for one integer, can we prove it's true for the next integer.

Induction Step: Assumption

We always start the induction step with an assumption: that the statement $(*)$ is true for a particular value, $n=k$.

So, here, we assume that $2^{5n}-2^{n}{\text{ is divisible by 60 for }}n=k$. In other words:

$2^{5k}-2^{k}{\text{ is divisible by 60 }}\quad (\dagger )$

We expect to use this assumption in the "meat" below, but we may not see it immediately - we may have to "force" the algebra, or un-simplify it, to be able to use the assumption.

Induction Step: Goal

We now want to show that the statement $(*)$ is true for $n=k+1$, whenever our assumption is true.

So, we want to show that $2^{5(k+1)}-2^{k+1}{\text{ is divisible by 60}}$.

As usual, I like to write the goal in a cloud to the side of my work, and treating it as a "show that" question. I must be careful to not use the goal in my work - or this creates circular logic.

I want to start with the statement $2^{5(k+1)}-2^{k+1}$ on the first line, and end on the last line saying "which is divisible by 60".

Induction Step: "The Meat"

I have to start with$2^{5(k+1)}-2^{k+1}$, and I want to force $2^{5k}-2^{k}$ to appear out of it, so I can use then the assumption seen above at $(\dagger )$.

${\begin{aligned}2^{5(k+1)}-2^{k+1}&=2^{5k+5}-2^{k+1}\\&=32\times 2^{5k}-2\times 2^{k}&{\text{using rules of powers/exponents}}\\&=(30(2^{5k})+2(2^{5k}))-2(2^{k})&{\text{split the first term to force the assumption to appear}}\\&=30(2^{5k})+2(2^{5k}-2^{k})&{\text{the assumption from }}(\dagger ){\text{ shown explicitly}}\\&=60(2^{5k-1})+2(2^{5k}-2^{k})&{\text{make 60 more visible, allowed since }}5k-1\geq 0\\\end{aligned}}$

Since the first term is shown to be divisible by 60, and our assumption says that $2^{5k}-2^{k}$ is divisible by 60, the whole thing is divisible by 60. QED.

Note: this only proves the induction step. We still need to have an overall conclusion.

Conclusion(s)

As in all Proofs by Induction, we need our three lines of conclusion:

1. The statement $(*)$ is true for $n=2$.
2. If the statement $(*)$ is true for $n=k$, then it is true for $n=k+1$.
3. Therefore, the statement $(*)$ is true for all n such that $n\in \mathbb {N} ,n\geq 2$.

Alternative using Function Notation

With a bit of extra set-up, and function notation, we can reduce the amount of writing. Here is the same proof again, with the setup carefully defining the function $f$:

Let $f(n)=2^{5n}-2^{n}$.

Alternative: Base Case

$f(2)=2^{10}-2^{2}=1020=60\times 17$

So, $f(2)$ is divisible by 60.

Alternative: Induction Step

Assume that f(k) is divisible by 60. Then:

${\begin{aligned}f(k+1)&=2^{5k+5}-2^{k+1}\\&=32\times 2^{5k}-2\times 2^{k}\\&=30(2^{5k})+2(2^{5k})-2(2^{k})\\&=60(2^{5k-1})+2(f(k)){\text{ which is divisible by 60}}\\\end{aligned}}$

Therefore, if f(k) is divisible by 60, then f(k+1) is also divisible by 60.

Alternative: Conclusion

We still need three points of conclusion, but we have written two of them clearly already.

Therefore, f(n) is divisible by 60 for $n\in \mathbb {N} ,n\geq 2$.

More Proofs by Induction

Proof by Induction is a very powerful tool and "the meat" can look slightly different in different contexts. It's worth it to look at further examples:

• Proof by Induction
• Proof by Induction: Divisibility
• Proof by Induction: Recursion
• Proof by Induction: Matrices
• Proof by Induction: Inequalities
• Proof by Induction: "Strong" Induction