Proof by Induction: Divisibility

Let's look at an example of Proof by Induction with 'divisibility'^[1].

Example

We want to prove that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{5n} - 2^{n} \text{ is divisible by 60 for } n\in\mathbb{N}, n\ge2} .

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

a base case
an induction step
a conclusion

Divisibility Notation

We are considering the statement: "Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 60 | 2^{5n} - 2^{n}}

The pipe symbol, a perfectly vertical line, is representing the idea of divisibility here. You can read Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |} out loud as the word "divides", and say "60 divides Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{5n} - 2^{n}} ,
60 is a factor of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{5n} - 2^{n}} ,
60 is a divisor^[2] of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{5n} - 2^{n}} ,
60 goes into Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{5n} - 2^{n}} perfectly,
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{5n} - 2^{n}} is divisible by 60,
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{5n} - 2^{n}} is a multiple of 60,
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{5n} - 2^{n}} is in the 60-times table,
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{5n} - 2^{n} = 60k} .

When we say Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a|b} , you might expect that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a\le{}b} . You can imagine that the times table goes Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a, 2a, 3a, 4a,...} , and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} must be one of these. But, be careful about this, since it is not exactly true: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} is in the 60-times table, and so is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{5n} - 2^{n} \text{ is divisible by 60 } (*) \text{ for } n\in\mathbb{N}, n\ge2 }

Base Case

Note! The proof asks us to start with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=2} .

In fact, the statement is not true for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=1} , so we can't have a base case of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=1} : our whole proof will collapse, like the bottom of a house of cards. We have to start our base case with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=2} , and then our proof will build from there.

Consider Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=2} .

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} 2^{5n} - 2^{n} &= 2^{10} - 2^{2}\\ &= 1024 - 4\\ &= 1020\\ &= 60\times17 \text{ which is divisible by 60}\end{align}}

This proves that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (*)} is true for the "base case" of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (*)} .

Induction Step

In this step, we forget about Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (*)} is true for a particular value, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=k} .

So, here, we assume that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{5n} - 2^{n} \text{ is divisible by 60 for } n=k} . In other words:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Assume } 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (*)} is true for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=k+1} , whenever our assumption is true.

So, we want to show that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 withFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{5(k+1)}-2^{k+1}} , and I want to force Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{5k}-2^{k}} to appear out of it, so I can use then the assumption seen above at Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\dagger)} .

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} 2^{5(k+1)}-2^{k+1} &= 2^{5k+5} - 2^{k+1} \\ &= 32\times2^{5k} - 2\times2^{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\ge0\\ \end{align} }

Since the first term is shown to be divisible by 60, and our assumption says that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{5k} - 2^{k}} is divisible by 60, the whole thing is divisible by 60. QED^[3].

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:

The statement Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (*)} is true for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=2} .
If the statement Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (*)} is true for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=k} , then it is true for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=k+1} .
Therefore, the statement Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (*)} is true for all n such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n\in\mathbb{N}, n\ge2} .

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^[4].

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:

Footnotes

↑ Divisibility proofs can typically also be done without induction, but A-Level examiners may ask you to do this with induction.
↑ chiefly American, I think.
↑ Latin for "quod erat demonstrandum", i.e. "that which was to be demonstrated". We have done what we planned to do, according to our goal. There are other ways of notating this including a small square $_{\square }$ .
↑ You may notice that we can also say the same about 120. However, we shouldn't, because this isn't what we are trying to prove. The base case does not support this, so our proof would have no foundation.

[1] Divisibility proofs can typically also be done without induction, but A-Level examiners may ask you to do this with induction.

[2] y American, I think.

[3] Latin for "quod erat demonstrandum", i.e. "that which was to be demonstrated". We have done what we planned to do, according to our goal. There are other ways of notating this including a small square $_{\square }$ .

[4] You may notice that we can also say the same about 120. However, we shouldn't, because this isn't what we are trying to prove. The base case does not support this, so our proof would have no foundation.

[1]

[2]

[3]

[4]