Last week we looked at introductory explanations of what mathematical induction is, including answers to some misunderstandings of the concept. But we only looked at one trivial example of such a proof; for a real understanding of the technique, we need some fuller examples. For that purpose, I have chosen a few questions we have answered with relatively full explanations: two summations, and two divisibility proofs.
Sum of squares
The first question is from 1998:
The Sum of the First N Squares I don't know where to begin. I have to formulate a formula for the sum of the first N squares (i.e. 1^2 + 2^2 + 3^2 + ... + N^2) by mathematical induction.
Doctor Sonya answered, first clarifying the problem:
Hi, Rob: I'm not quite sure what exactly you are supposed to do in this problem. To "formulate" means to find a formula. You never use mathematical induction to find a formula, only to prove whether or not a formula you've found is actually true. Therefore I'll assume that you want to find a formula for the sum of the first n squares, and then prove that the formula is right using mathematical induction.
This is an important distinction to understand: Induction is used to prove that a formula you may have just guessed, is indeed correct. Induction, in fact, often seems unsatisfying because it doesn’t give even a hint as to how the thing being proved could have been discovered. So this assignment is not well worded.
What is induction? (reprise)
Next, a quick overview of what we saw last week:
First, let me give you a brief account of how "mathematical induction" works. a) When do we use "mathematical induction"? Well, we sometimes encounter such problems where the behavior of a series of numbers or expressions SEEMS to change in a fixed manner. Here, I emphasize "SEEMS" because we do not know for sure if a certain formula works or not. For example, after looking at some numbers, I might guess that the sum of the first n squares can be found by the formula: (1/2)(n^2 + 14). However, I cannot say that this formula works for every n, because I really didn't try it with EVERY n, just with some of them. In such cases that involve natural numbers (1,2,3...), mathematical induction is a way to find a proof without having to spend eternity plugging values of n into the formula.
That “guess”, by the way, is intentionally wrong, and you can easily see that by trying a number of two. Disproving a guess is often very easy; proving it takes a lot more work!
b) What are the steps of a typical "mathematical induction"?
1) To show that when n = 1, the formula is true.
2) Assuming that the formula is true when n = k.
3) Then show that when n = k+1, the formula is also true.
According to the previous two steps, we can say that
for all n greater than or equal to 1, the formula has
been proven true.
“Guessing” a formula
Now, you may find the above explanation too abstract. So, let's just take your question as an example.
We want to find the formula for 1^2+2^2+3^2+...+n^2. Now, I'm going to assume that you have already thought a lot about this problem, and you have a pretty good guess that the sum of the first n squares is:
n (n + 1) (2*n + 1)
------------------
6 (N.B. 2*n means "2 times n")
However, we still don't know if this formula is true for all n, because we never tried it with n = 1,235,822 or n = 677,331 or millions of others. That's where proof by induction comes in: it will allow us to say that this formula it true for ALL n without having to test them all.
You would never come up with that formula just by random guessing, would you? For some ways you might discover this formula, see
Sum of Consecutive Squares Formula for Sum of First N squares
Doing the induction
Now, we're ready for the three steps. 1. When n = 1, the sum of the first n squares is 1^2 = 1. Using the formula we've guessed at, we can plug in n = 1 and get: 1(1+1)(2*1+1)/6 = 1 So, when n = 1, the formula is true.
This step is usually pretty easy.
2. Now we'll assume that when n = k (for some k that's greater than or equal to 1), the formula is also true. What this means is that we're just going to declare that our formula is true for k. 1^2 + 2^2 + 3^2 + ... + k^2 = k(k+1)(2*k+1)/6
This step takes no real work; it’s just a matter of replacing the general variable n with a specific k so we can make an assumption. (You can carry out the work without renaming the variable, but you might forget that you haven’t yet proved the general claim!)
3. Now we're going to try to prove, using the assumption from step 2, that the formula is true for n = k + 1. The series we need to compute is 1^2 + 2^2 + 3^2 + ... + k^2 + (k+1)^2. Since we already made an assumption about the sum of the first n squares (step 2), we can replace the part before (k+1)^2 by k*(k+1)*(2*k+1), and get the following: 1^2 + 2^2 + 3^2 + ... + k^2 + (k+1)^2 = k(k+1)(2*k+1)/6 + (k+1)^2 Now we work on the right part of the equation to try to make it into our formula for n = k+1. I would like to leave this part of the work to you. Just remember that our formula says that the sum of the first k+1 squares is: (k+1)*((k+1)+1)*(2*(k+1)+1)/6)
Since Rob has had over 20 years to work on it, we can go ahead and do it now. I like to start this step by writing out what our goal is: to show that $$\frac{k(k+1)(2k+1}{6} + (k+1)^2 = \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}$$ It will help if we simplify the RHS (right-hand side) a bit: $$\frac{k(k+1)(2k+1}{6} + (k+1)^2 = \frac{(k+1)(k+2)(2k+3)}{6}$$
Keep in mind that we don’t know this yet; it is what we want to prove!
How can we do that? We can either transform the LHS (left-hand side) into the RHS step by step; or we can just simplify both sides and show that they are equal to the same thing. Looking at the simplified version above, I see \((k + 1)\) in every term, so I’m going to keep those while combining the two terms on the LHS: $$\frac{k(k+1)(2k+1)}{6} + (k+1)^2 = \\ \frac{k(k+1)(2k+1)+6(k+1)^2}{6} = \\ \frac{(k+1)\left[k(2k+1)+6(k+1)\right]}{6} = \\ \frac{(k+1)\left[2k^2+7k+6\right]}{6} = \\ \frac{(k+1)(k+2)(2k+3)}{6}$$
My last step was to factor \(2k^2+7k+6\), but that was easy because I kept my eye on the goal and just had to check that it was equal to what I expected, \((k+2)(2k+3)\)!
4. Now, say what you've proved.
We’ve shown that the formula holds for n = 1, and that if it holds for any k, then it also holds for k + 1. Therefore, we have proved that for any positive integer n, $$1^2+2^2+3^2+\cdots +n^2 = \frac{n(n+1)(2n+1}{6}$$
Sum of consecutive odd numbers
Next, we have a question from 1996, where a pattern has been observed, and we want to show that it is “real”:
Sum of n Odd Numbers Dear Dr. Math: I am in the 9th grade, and taking trig. I was thinking about patterns in numbers one day and I came up with a peculiar law. It gives you every perfect, real, integral, square! (1,4,9,16,25.....) This is how it works: Start with 1. Now think of the set of odd numbers. Add the first odd number that isn't 1.(3). what do you get? 4....a perfect square! now add the next odd number to 4. What do you get? (4+5=9) A perfect square. Keep adding the odd numbers to the perfect squares. (9+7=16...16+9=25...25+11=36...36+13=49...etc. etc. Now, to me, this is a simple pattern. I'm no genius, so someone must've thought of this law. Right? Your mission - find out who? I'd appreciate any help you could give.
If we keep adding consecutive odd numbers, we get a perfect square; this implies a formula for the sum of odd numbers. It is actually so well known that no name is attached to it; it is a special case of the general concept of an arithmetic series.
Doctor Luis answered:
You're very perceptive! To have noticed this simple pattern. Indeed, this pattern works as follows:
1 + 3 + 5 + ... + (2n-1) = n^2
That is, the sum of all odd numbers, up to the odd number (2n-1) is n^2. To illustrate this, think of the following example: What is 1 + 3 + 5 + ... + 997 + 999 ?
Well, 999 is of the form 2(500)-1, so n, in this case, is 500, so the sum of all odd numbers (from 1) up to 999 is 500^2 or 250,000.
The first step in proving a claim is to state it as clearly as possible. Here, we might have looked at the examples and seen, say, that we get the square of 7 when the last number added was 13, which is 2(7) – 1.
Another overview of induction
The above theorem can be proven quite easily by a method called induction, which is a very powerful technique used in mathematics to prove statements about the natural numbers. Since by now I probably have you interested, I'll explain a tad more about induction, and prove a basic relation involving, again, the natural numbers: Induction (a variation of it, at least) involves three steps in proving a statement. The first one is called the Basis Step, and it just involves the assertion that the given statement is true for the natural number 1. The second step involves the assumption that the statement is true for all natural numbers less than or equal to some integer k, and, not surprisingly, is called the Hypothesis Step. The third step is the Inductive Step, and it involves proving that: if the statement is true for the integer k, then it is true for the integer k+1. This step usually comprises the bulk of inductive proofs.
An example
As always, a good example clarifies a general concept. You’ll observe that Doctor Luis will, as we like to do, offering a different example to work through, so that our anonymous asker can enjoy doing his own. He will prove the simplest arithmetic series, one that is very well known (called the triangular number formula):
Just in case you got confused whilst trying to read what I wrote :), I'll prove the following relation (by induction, of course):
1 + 2 + 3 + 4 + 5 + ... + n = n(n+1)/2
Proof:
Let S(n) be the sum of all integers from 1 to n, inclusive.
So the statement to prove (I'll label it 'a') is that
S(n) = n(n+1)/2 (a)
As we saw last week, it can be helpful to label the nth statement symbolically; here, the label is not for the nth proposition, but for the nth sum. This will make it easier to write about the next one.
Now that I know what it is I'm trying to prove, I'll follow the steps I told you about above.
[Basis step]
S(1) is clearly 1 (by definition).
Let's see if statement (a) is true:
S(1) = 1(1+1)/2
= 2/2
= 1 (so the Basis Step holds)
Some readers might be curious about the fact that S(1) means “the sum of natural numbers from 1 through 1 is 1”! The notation “\(1 + 2 + 3 + 4 + 5 + … + n\)” doesn’t mean that n is greater than 5, but is illustrative of “the sum of the first n natural numbers”. Mathematicians get used to treating 1 just like any other number, and not worrying about grammatical oddities (“the first one natural numbers”??). But the base case is generally special like that.
Strong and weak induction
[Hypothesis]
Assume that the statement
S(n) = n(n+1)/2
is true for the natural numbers n = 1,2,...,k.
Until now we have assumed that our proposition is true for n = k, not for all numbers up to k. What Doctor Luis is stating here is technically called “strong induction“, meaning that we are making a stronger assumption than in ordinary “weak induction“. Usually weak induction is all we need, but sometimes it is easier to do the proof by making the stronger assumption. (Here it isn’t necessary.)
Weak induction says, “If it worked last time, it will work this time;” strong induction says, “If it’s always worked so far, it will work this time.”
Weak induction is represented well by the domino analogy, where each is knocked over by the one before it; strong induction is represented well by the stair analogy, where each step is supported by all the steps below it.
The two forms are equivalent: Anything that can be proved by strong induction can also be proved by weak induction; it just may take extra work. We’ll see a couple applications of strong induction when we look at the Fibonacci sequence, though there are also many other problems where it is useful.
The core of the proof
[Inductive Step]
This is the tricky part of the proof. Here, you need to prove that if the statement in the hypothesis is true for the integer k then it is true for the integer k+1. I'll proceed as follows:
By hypothesis,
S(k) = k(k+1)/2
Now, I'll add (k+1) to both sides, and obtain
S(k) + (k+1) = k(k+1)/2 + (k+1)
= k(k+1)/2 + 2(k+1)/2
= [k(k+1) + 2(k+1)]/2
= [(k+1)(k+2)]/2
This is the same kind of reasoning we used for the sum of squares, and in fact for any summation formula; the only difference is that the goal wasn’t stated first, so it may have been harder to see why we are doing what we do, and that we have, in fact, finished the work! Once again, we wanted a factored form, so the common factor of \((k+1)\) was useful.
Ok. So far, we have S(k) + (k+1) = (k+1)(k+2)/2 Remember that S(n) is, by definition, the sum of all integers from 1 to n. Now, look at the left side of the equation. Therefore S(k) + (k+1) is simply S(k+1) ! Thus, S(k+1) = (k+1)(k+2)/2 which is what you obtain if you substitute n by (k+1) in statement (a)! What I have just proven is the Inductive Step, and this completes the proof.
This is the part I like to do ahead of time, to set up my target.
I have tried my best to explain the proof thoroughly so that you may be able to prove for yourself the interesting pattern you discovered. Hope this helped :)
I, too, will leave it to you to prove the formula for the sum of odd numbers. You’ll find that the algebra is far easier than what we just did!
Two divisibility proofs
This question is also from 1999:
Proof by Mathematical Induction I must prove the following statement by mathematical induction: For any integer n greater than or equal to 1, x^n - y^n is divisible by x-y where x and y are any integers with x not equal to y. I am confused as to how to approach this problem. Reading the examples in my textbook have not helped explain divisibility. Can you shed some light on this and get me going in the right direction?
What is to be proved here could be thought of as factoring of polynomials, as we know for example that \(x^3-y^3=(x-y)(x^2+xy+y^2)\); but it is stated of numbers, as for example if \(x=5\) and \(y=3\), then \(x^4-y^4=625-81=544\) is divisible by \(x-y=5-3=2\).
A simpler example
Doctor Marykim answered, starting with a proof of divisibility by a fixed number:
Hi James, Since you are not familiar with divisibility proofs by induction, I will begin with a simple example. The main point to note with divisibility induction is that the objective is to get a factor of the divisor out of the expression. As you know, induction is a three-step proof: Prove 4^n + 14 is divisible by 6 Step 1. When n = 1: 4 + 14 = 18 = 6 * 3 Therefore true for n = 1, the basis for induction.
It is assumed that n is to be any positive integer. The base case is just to show that \(4^1+14=18\) is divisible by 6, and we showed that by exhibiting it as the product of 6 and an integer.
Step 2. Assume true for n = k
i.e.: 4^k + 14 = 6 * A, where A is a positive integer.
Rearranging this we get: 4^k = 6A - 14
Now consider n = k+1:
4^(k+1) + 14 = 4*(4^k) + 14
= 4(6A-14) + 14 (from our assumption)
= 24A - 56 + 14
= 24A - 42
= 6(4A-7)
Therefore, if true for n = k, then true for n = k+1
Doctor Marykim is taking the 3 steps a little differently than others, taking the second to include the inductive step proper, and step 3 to be the statement of the conclusion. What she has done here is to use the assumption, in the form \(4^k=6A-14\), to show that the next case, \(4^{k+1}+14\), is also a multiple of 6 by rewriting it and factoring out 6.
Step 3. However, the statement was proved true for n = 1 (Step 1) So the statement is true for n = 1+1 = 2 (step 2) Thus the statement is true for n = 2+1, 3+1, ... (iterating step 2) Therefore the statement is true for all positive integral n
This explains how induction works, as a chain of implications.
The requested proof
That was provided as an example, focusing on what it takes to prove divisibility. Now James gets to try it himself:
Now back to your original question: Prove (x^n) - (y^n) is divisible by x - y Step 1. This is a trivial step, so I'll leave it up to you. Step 2. Assume true for n = k, i.e.: x^k - y^k = (x-y)A, where A is a positive integer. If you follow the same steps as in the example above, you should be able to get a common factor of x-y in your final expression. Step 3. This will be exactly the same as in the other example.
Let’s do it. Keep in mind that x and y are just arbitrary integers; induction involves n, which can be any positive integer.
Base case: For n = 1, we are claiming that \(x^1-y^1=x-y\) is divisible by \(x-y\), which is obvious, as any number is divisible by itself. But to practice how we prove such things, the proof is $$x-y=1(x-y) \text{ for any }x\text{ and }y $$
Induction hypothesis: We assume that \(x^k – y^k = A(x-y)\) for some integer A, for all integers x and y. Our goal is to show that \(x^{k+1} – y^{k+1} = B(x-y)\) for some integer B.
Inductive step: We need to factor out \((x-y)\) from \(x^{k+1} – y^{k+1} = x\cdot x^k-y\cdot y^k\). One useful trick for factoring (equivalent to long division) is to insert a pair of equal terms in the middle, chosen so that we can factor by grouping: $$x\cdot x^k-y\cdot y^k = \\x\cdot x^k\boldsymbol{-y\cdot x^k+y\cdot x^k}-y\cdot y^k =\\(x-y)x^k+y(x^k-y^k) = \\(x-y)x^k+yA(x-y) = \\(x-y)(x^k+yA)$$ That does the job, since \(B = (x^k+yA)\) is an integer.
Conclusion: We have shown that \(x^n – y^n\) is divisible by \((x-y)\) for all integers x and y, when \(n=1\), and for any subsequent value of n, and therefore for all positive integers n.
Pingback: Inductive Proofs: More Examples – The Math Doctors
Pingback: Summing Squares: Finding or Proving a Formula – The Math Doctors