Proof By Induction

This is, I believe, a first year algebra topic; I find it rather interesting since it's a way of performing a mathematical proof which appears, at first glance, to rely on circular reasoning, but in fact does not. When this topic is first presented in an algebra course, extra care needs to be taken to show what's going on, and why it's not circular.

Apologies for the bad 'text-based math'.

Let's use the usual example, which is the expression S(n), being the sum of all the integers 1 through n, with n being an integer ≥ 1.

Generally, for an inductive proof you need to know beforehand exactly what you intend to prove.

So first, we'll find S(n) with an informal discussion:

Make a table with n rows and 2 columns.

The first column has the values 1 through n.

The second column has the same values in reverse order (from n down to 1).

So, each row adds to n+1; there are n rows; the total of all the numbers in the table is thus n(n+1). The table contains two copies of the list, so

S(n) = n(n+1)/2

Now, we'll prove that by induction. To avoid making an error of deduction, we're going to define these two functions:

S(n) = the sum of the numbers from 1 to n

H(n) = n(n+1)/2

H(n) being a 'hypothesis' function; and we will forget that we already know that they are the same. I.e. we won't rely on that knowledge in the proof.

So, to prove by induction that S(n) = H(n) for all integer n ≥ 1:

1. first prove that this is true for n=1
2. then, prove that if it's true for n=j, then it must also be true for n=j+1.

If we manage to prove both of these, we will have proven it's true for n=2, since we can set j=1, and then the second step says "if S(1)=H(1), then also S(2)=H(2). And, thus, by setting j=2, it's proven for S(3)=H(3). And inductively -- not circularly -- we prove S(n)=H(n) for all higher integers.

The first part is easy:

S(1) = sum of { 1 } = 1

H(1) = n(n+1)/2 for n = 1, which is (1)(2)/2 = 1

So, we have proven it for n=1. We will step carefully through the second part of the proof, to avoid making any circular inferences.

Let 'j' be any value of n for which we know that S(n) = H(j).

So:

S(j) = H(j) [ given ]

but:

S(j+1) = S(j) + (j+1) [ adding the next integer to the sequence]
S(j+1) =H(j) + j+1 [ since S(j) = H(j) ]

S(j+1) = j(j+1)/2 + j + 1 [ substitute H(j) ]

S(j+1) = ( j*j + j + 2*j + 2)/2 [expand and collect terms over 2 ]

S(j+1) = ( j*j + 3*j + 2 ) /2 [collect terms]

S(j+1) = (j+1)(j+2)/2 [ factor the quadratic ]

S(k) = k(k+1)/2 [ substitute k = j+1 ]

S(k) = H(k) [ substitute H(k) ]

So, we are back where we started with S(j)=H(j)? No, because j is not just a parameter, it's the specific value for which we (by premise) know that S and H are the same. Since k=j+1, we've proven something we didn't have before. Let's eliminate k to make this clearer:

S(j+1) = H(j+1)

So we've shown, using only specific knowledge of S(n)'s properties, and the definition of H(n), that if S(n)=H(n) for n=j, it must also hold for n=j+1

So, we've proven this for all integer n ≥ 1.

If you don't like having to do the factoring to 'come up with' H(j+1) -- in a sense it seems like this requires you to anticipate the result -- you can finish like this instead:

S(j+1) = ( j*j + 3*j + 2 ) /2 [as before]

.. and note that

H(j+1) = (j+1)(j+1+1)/2 [ sub n=j+1 into H(n) ]

.. thus the difference between these is

H(j+1)-S(j+1) = ((j*j + 3*j+2) - (j*j + 3*j+2))/2 [expand, subtract, collect over 2]

H(j+1)-S(j+1) = 0 [ since all terms cancel]

Thus, again, H(j+1) = S(j+1). Somewhat less satisfying, but more amenable to 'brute force' algebra.

If these seem too 'magic' or self-fulfilling - "Can't you just do that with any function?" a good way to assure yourself that it really works is to try 'proving' something else, something which isn't right (because no, you can't just do that with any function). I'm going to replace H(n) with this 'wrong' hypothesis function

W(n) = n(n-1)+1

So, as before, we start by trying to prove W(1) = S(1):

W(1) = (1)(0) + 1 = 1 = S(1)

Hey, that works! In fact it works for n=2 as well: W(2)=S(2) = 3, I've deliberately chosen a good 'wrong' function to make it more interesting.

So, on to the second part of our (hopefully doomed-to-failure) proof. We want to show that if W(j)=S(j), then W(j+1) = S(j+1).

S(j) = W(j) [ given ]

but:

S(j+1) = S(j) + (j+1) [ adding the next integer to the list]

S(j+1) =W(j) + j+1 [ since S(j) = W(j) ]

S(j+1) = j(j-1)+1 + j + 1 [ substitute W(j) ]

S(j+1) = (j*j - j +1) + j + 1 [expand ]

S(j+1) = ( j*j +2) [collect terms]

Note, there's no error in this; it's perfectly valid; if S(j)=W(j) then S(j+1)= (j*j+2), and we know that the premise is true for j=1 and j=2 at least. But how to work this towards S(j+1)=W(j+1)? I'll use the second approach above and subtract:

W(j+1) = (j+1)(j+1-1) + 1 [substitute]

W(j+1) = j*j + j + 1 [ expand and collect terms]

... thus the difference is

W(j+1) - S(j+1) = (j*j+ j + 1) - (j*j+2 ) [difference]

W(j+1) - S(j+1) = j - 1 [simplify]

Again, this is all correct, no errors, but we have simply failed to show that W(j+1)=S(j+1) for all j. In fact, we've shown that is only true for j=1. So from this, and from W(1)=S(1), we can indeed conclude that W(2)=S(2), but from there it goes no further, the inductive proof has failed.

This amounts to testing our method of testing things; if I had been able to prove the W(n) function using a methodology - and we know W(n) is wrong - I would have no choice but to conclude that my methodology of proof was flawed.

To a mathematician, this exercise with W(n) is utterly superfluous, and you are thus unlikely to find it any textbook. Because the 'proof-by-induction' is simply a strategy for applying the general method of mathematical proofs - any particular use of it will stand (or fail) on that basis -- and of course, showing that a particular methodology fails to prove one non-true hypothesis doesn't mean it will fail to prove all others. But I'm primarily an engineer, we sometimes like to deliberately test faulty things just to be sure that the test will in fact find them to be faulty. And often the way in which things fail gives you insight into how they are supposed to work.

Etymology

I don't know exactly why this is called 'by induction'; the word seems to generally refer to something causing something else ("How can fire induce stone?"- Wormtongue), electrical e1ngineers talk about magnetic fields inducing current in conductors. in the mathematical sense, each proof 'induces' the proof of its neighbor, but there's definitely an implication that this process carries on to an infinite -- or at least arbitrarily long -- extent, and this element is not present in other uses of the word.