Proof by mathematical induction

Proof method: Strong Induction

As I promised in the Proof by induction post, I would follow up to elaborate on the proof by induction topic. Here is part of the follow up, known as the proof by strong induction.  What I covered last time, is sometimes also known as weak induction.

In weak induction the induction step goes:

Induction step: If P(k) is true then  P(k+1) is true as well.

Strong induction expands the concept to:

Induction step: If P(m), P(m+1), P(m+2)… P(k) is true then  P(k+1) is true as well for some k > m.

The difference between the two methods is what assumptions we need to make in the induction step. To switch to the metaphor of dominoes again – in the weak induction we need to know that the previous domino is toppled, then the next one will topple as well. In strong induction we need to know that all the previous ones has toppled before we can ensure that the next one will fall as well.

Both methods have the same logical strength when we apply them, since in order to get to the k’th domino we need to topple 1,2,3,…k-1 anyway. However, sometimes strong induction makes the proof of the induction step easier.

Strong Induction Example 1

I have shamelessly stolen this example from Hammack since I think it brilliantly shows when strong induction is better to use. But lets first see what happens if we try to use weak induction on the following:

Proposition: if , then 12|(n4 – n2)

Weak induction

Base case: we need to prove that 12|(14 – 12) = 12|(1- 1) = 0, which is divisible by 12 by definition.

Induction step: We assume that the 12|(k4 – k2) is true such that (n4 – n2) = 12a for some . We then need to show that ((k+1)4 – (k+1)2) = 12b for some .

My approach would be to a direct proof such that

(k+1)4 – (k+1)2 = k4 + 4k3 + 6k2 + 4k + 1 – (k2 + 2k + 1) =  (k4 – k2) + 4k3 + 6k2 + 2k = 12a + 4k3 + 6k2 + 2k

How do we proceed from there? I don’t have a clue. If you can show me how to continue of this road I would be glad to hear it.

Strong induction

The weak induction method failed. However, we can show that n = k-5 implies that the statement is true for k+1, so we need to expand the base case to include everything up to n = 6.

Base case: 
n = 1:  12|(14 – 12) = 12|(1- 1) = 0 = 012
n = 2:  12|(24 – 22) = 12|16-12 = 12 = 1
12
n = 3:  12|(34 – 32) = 12|(81 – 9) = 72  = 612
n = 4:  12|(44 – 42) = 12|(256- 16) = 240 = 20 * 12
n = 5:  12|(54 – 52) = 12|(625- 25) = 600 = 50
12
n = 6:  12|(64 – 62) = 12|(1296- 36) = 1260 = 105*12

So far it fits really well.

Induction step: let and assume that 12|(m4 – m2) for , now we need to prove that 12|((k+1)4 – (k+1)2)  is true as well.

Let us define l =  k-5 for which we assume the proposition to be true such that  (l4 -l2) = 12a for some value of a. We need to show that 12|((l+6)4 – (l+6)2) is true.  So let us try with a direct approach

(l+6)4 – (l+6)2= (l4 +24l3 + 180l2 + 864l + 1296) – (l2 + 12l + 36) = (l4 – l2) +24l3 + 180l2 + 852l + 1260 = 12a +12(2l3 + 15l2 + 71l + 105).

This statement is clearly divisible by 12, and thus proofs the proposition.

QED

So in order to prove it for n = k+1 = 7 we need n = k-5 = 1 to prove it, but that is handled in the base case, same goes for all the n = 8,9,10,11,12 and then we start to rely on the fact that we can prove n= 8 through the induction step.

Image Credits

The metaphor of dominoes also gave rise to the chosen post photo, which was kindly shared under the creative common license by Malkav. My crop of the photo is of course shared under the same conditions.

Posted by Kristian

15 comments

Graph Theorist

An interesting issue.

Two comments, however:
1) In the 12|(n^4-n^2) example, the proof is elementary, without any iductions. You have to demonstrate n^4-n^2 is disible by 12, that is, by 4 and by 3. Both parts are done by cases (1,2 modulo 3, 1,2,3 modulo 4) and there are 6 non-trivial cases to deal with, arguably easier and clearer than the proof by strong induction you’ve given. The argument can be shaped to fit weak induction structure (what you started to do), and then one has to do the cases-trick for 4k^3+6k^2+2k. Works as well.

So this example fails to show the power of strong induction. Better examples are abundant in group theory, f.e. in proofs regarding composition chains.

2) The true, deep difference between the two inductions as I understand it is the assumption about the initial point. The “weak” induction requires a starting stone, the “strong” one doesn’t! That is, the statement “if blablabla is true for all natural m<k, it's correct for k" doesn't need the basic step in order to work! This nuance is relevant (although, AFAIK, not in a dramatic fashion) in set theory, when we deal with transfinite inductions.

Graph Theorist

Returning to the question in order to procrastinate, :), there’s an even simpler, immediate way to show that 12|(n^4-n^2) – just write n^4-n^2 = n*(n-1)*n*(n+1) and we’re done! The product of any three consecutive integers is divisible by 3, and either n^2 or n^2-1 is divisble by 4.

A question for the deeply intrigued: investigate the factoring of n^k-n^(k-2). For k = 4, we have our case. For k = 3, it’s easy to have 6/(k^3-k), yielding yet another formulation of the proof of the original question. What about k = 5? There’s a (non-surprising) common divisor, but what about k = 6? k^6-k^2?

Hi

First of all thanks for your comments. I must admit that strong induction is not one of my strong points. I was mainly writing about weak induction when I discovered it and thought I would mention it, and hopefully inspire you guys to read more on it.

I am aware that the proposition can be proven in other ways. I chose an example which I believe everyone can follow and where strong induction works well unlike weak induction. However, I am sure there are other examples that may show some sides of strong induction better. I will have to look up on that and maybe return to the subject later on.

Regarding your second comment, most of the sources I have checked to read up strong induction includes the base case to prove a starting point. However, wikipedia mentions that you don’t need it. So if you have some more on this, or have some examples I would be really happy to see them and learn why it works, since it would be a relevant detail to explore.

Regarding your other comment. Once you have written n4-n2 = n*(n-1)*n*(n+1), we can argue that it has the prime factors 2,2 and 3. Your argument holds for 3 and if n is odd then n-1 and n+1 will both be divisible by two. If n is even then we have that n and n is divisible by two. This proving the proposition.

The last thing I will let stand unanswered in the hope that someone will bite the hook and spawn more discussion 🙂 Very nice question though.

/Kristian

Hi ,I’m not a very bright math student who’s still trying to understand strong induction.
How did you know that you needed to expand the base case to 6? Wouldn’t other numbers sort of work too?

Hi Alice

First of all, I seriously think that you are not very bright. I know what it feels like being in the middle of a course. But you don’t reach a level where you need to understand strong induction unless you are either pretty bright, or good at faking 🙂

And now for your question. We need the 6 base cases since we trying to prove something for k+1 and we then define l = k-5 (meaning a distance of 6) and we assume that the proposition is true for l. We can only make this assumption and continue if we have actually proven it for all the cases k=1 to k=6. Otherwise there could be one of those values where the proof fails.

haha thanks
but I still don’t get it! How did you know what to define I as? or can it be any number?

The reason for defining l as k-5 is the fact that ((l+6)^4 – (l+6)^2 gives us a polynomial where we can isolate 12 from all parts. And thus easily show that it is divisible by 12. This is where the practice and experience comes in. However, for most other values of l we would end up with a final expression where it is hard to prove that the expression is divisible by 12.

For the ordinary induction proof, what remains is to be shown that [latex]4k^3+6k^2+2k[/latex] is a multiple of 12.
Show this by factoring as [latex]2k(k+1)(2k+1)[/latex].
The factor of three comes from looking at the factors as [latex]k(k+1)(k+2+3k)[/latex].

What a great example with dominions, thank you for the analogy. Totally understand the difference between the two.

Not to beat a dead horse, but … Before I read the comments, I tried figuring why 12 | n^4-n^2. I’m not a math major but I sometimes need to write proofs for computer science classes and I find it excruciating. Still, it took me just a couple of minutes to work out the proof of n * n * n – 1 * n + 1 in the way stated above. But more importantly, it really *proved* it to *me*, i.e., explained it in a plain, obvious, indisputable way. Something about induction always leaves me unsatisfied.

Thank you. This is useful. I just started a discrete math course and strong induction is challenging.

FYI: I think you made a mistake for your multiplication of polynomials. (l+6)^4 should be: i^4 + 24i^3 + 216i^2 +864i + 1296. The good news is that this does affect your proof.

You gave up on the weak induction too quickly, it can be done pretty easily, you just run into proving another nested divisibility statement also by weak induction and when that is done, the outer proof is done as well.

Also, strong and weak induction are logically equivalent, which means there is nothing you could prove by only one principle and not the other, it just might be more difficult with one of them.

[…] learned about strong induction, and had a couple questions. First, on sites such as this one: http://www.mathblog.dk/strong-induction/ , it is said that using strong induction requires more bases case. (This makes sense to me, as you […]

@ relick’s comment: Fundamental Thm of Arithmetic: every positive integer can be expressed as a product of powers of primes, product being unique up to order of factors in product. Weak induction is no help (writing n as a product of primes does nothing for doing the same to n+1); strong induction works very well, it kicks in in the case that n+1 is not a prime already.
I should not post at 2:22am, above could be crazy talk. I have the beginning of a sore throat and I’m afraid of going to sleep…

Qingguang

Prove $12|(n^4-n^2),n=0,1,…$. Suppose $12|(k^4-k^2),k=0,1,…n$. We need to prove $12|[(n+1)^4-(n+1)^2]$ is true. Note that $(n+1)^4-(n+1)^2=(n+1)^4-(n+1)^2-(n^4-n^2)+(n^4-n^2)$. Since $12|(n^4-n^2)$ is true by the induction assumption, we only prove $12|[(n+1)^4-(n+1)^2-(n^4-n^2)]$ is true. Considering
$(n+1)^4-(n+1)^2-(n^4-n^2)=2n(n+1)(2n+1)$ we only prove $6|n(n+1)(2n+1)$ by induction. We now prove $6|n(n+1)(2n+1)$. Suppose it is true for all $k\leq n$. We want to prove $6|(n+1)(n+1+1)(2(n+1)+1)$ is true.
We discuss in two cases: $n=2m$ and $n=2m+1$(note $m\leq n$ for both cases).
It is easy to find $(n+1)(n+1+1)(2(n+1)+1)=8m(m+1)(2m+1)+6(m+1)(2m+1)$ if $n=2m$ and
$(n+1)(n+1+1)(2(n+1)+1)=8m(m+1)(2m+1)+6(m+1)(6m+5)$ if $n=2m+1$. Since $m\leq n$ and $6|m(m+1)(2m+1)$, we have that $6|(n+1)(n+1+1)(2(n+1)+1)$ is true for both cases. Done

Leave a Reply