Mathematical Induction

I haven't done a math post in a while, so let's talk about mathematical induction. This isn't related to inductive reasoning; it's more akin to deductive reasoning with recursion.

Suppose I came to a programmer and asked him to write a function that returns the sum of numbers cubed up to a given number. That is,

[math]sum\_cubes(n) = 1 + 2^3 + 3^3 + ... + n^3[/math]

Being a Scheme programmer, his first solution might be something like this:

(define (cube x) (* x x x))



(define (sum-cubes n)

  (if (= n 1)

    1

    (+ (cube n) (sum-cubes (- n 1)))))

"What's sum-cubes(10)?", I ask. "3025," he responds, after waiting unnoticeably long. "What's sum-cubes(415)?", I ask. "7,451,142,400," he responds, again waiting unnoticeably long. "And sum-cubes(416)?" "Uh... Stack overflow?" He wrote it recursively, but he neglected to remember that all languages have a recursion depth limit.

"Hold on," he says. Meanwhile, programmers used to a C-like language are smirking, knowing exactly how to implement this thing in a for-loop that runs quite fast and doesn't ever have a stack overflow problem.

"Okay, I'm back," says the Scheme programmer. (You see, Scheme doesn't have for or while loops.)

(define (sum-cubes2 n)

  (define (sum-iter total n)

    (if (= n 0)

      total

      (sum-iter (+ total (cube n)) (- n 1))))

  (sum-iter 0 n))

"And sum-cubes2(416) is 7,523,133,696. sum-cubes(1000) is 250,500,250,000. I can do whatever you want!"

"Okay, what's sum-cubes2(10 million)?"

He types it in, and waits an annoyingly long period of time as his Core i7 processor cranks the loop (which is completely equivalent to a for or while loop, so don't get smug other-language guys. There's no points taken off here for recursion; iteration is just a special case of recursion). "2500000500000025000000000000", he says after the time has passed.

"And a billion?"

"Look, I'm not going to waste my time calculating that!"

And he shouldn't. I laugh, and give him the following function:

(define (square x) (* x x))



(define (sum-cubes3 n)

  (square (/ (* n (+ n 1)) 2)))

(For those of you unable to grok Lisp well:)
[math]sum\_cubes3(n) = \left(\frac{n * (n + 1)}{2} \right)^2 [/math]

He calculates it for a few things, and sees that it produces the same output regardless of the given n he tries. One billion isn't even a struggle, for this algorithm runs in constant time. He returns "250000000500000000250000000000000000", but he just assumes it's correct since he's not going to test it with his other functions he knows will always give the right answer.

"How do you know this works for any given input?" he asks, "Maybe it stops working after 200 million."

"I can prove that it will work for any given input," I say.

"How can you do that? You'd have to check it works for every positive number, and there are infinitely many positive numbers! Graham's Number is a positive integer, you know. Good luck checking your answer with a computer that can't even represent a number close to Graham's!"

At this point it's time to introduce mathematical induction. Proving statements about infinitely many numbers such as the positive integers is what it was made for. The intuition pump is this: if you can prove that your statement, or proposition, P(n) is true for k, and that fact implies that P(k + 1) is also true, then for every integer k the statement is true. (Because having it true for k means k+1 is true, but having it true for k+1 means it's true for some integer j, which means j+1 is true, which is simply k+2, thus all numbers after k are true.)

So let's prove our little equation up there. Induction is performed with two steps: the basis step, and the inductive step.

Definitions: Let P(n) be the function we wish to prove is true for the set of all positive integers. Let P(n) be defined as such:

[math]P(n) = \left(\frac{n * (n + 1)}{2}\right)^2 [/math]

Basis Step: Show that the base case, usually P(0) or P(1), is true. (Note: you may have to show more than one base case, such as P(2) or P(3), and you don't have to start with 0 or 1 unless you're proving for all positive integers (which includes 1).)

[math]\begin{eqnarray}P(1) &=& \left(\frac{1 * (1 + 1)}{2}\right)^2 = \left(\frac{2}{2}\right)^2 &=& 1^2 &=& 1 &=& 1^3\end{eqnarray}[/math]

Check.

Inductive Hypothesis: We are going to assume that P(k) is true. We already showed that P(k) is true when k = 1, so we're going to assume it's true for any k and try to imply that P(k+1) is also true. (If P(k+1) is true, then we don't have to check P(2), P(3), etc.)

Inductive Step:

[math]\begin{eqnarray}
P(k) &=& 1 + 2^3 + 3^3 + ... + k^3 \\
&=& \left(\frac{k * (k + 1)}{2}\right)^2 \\
&& is\ true\ by\ the\ inductive\ hypothesis,\ thus: \\
P(k + 1) &=& 1 + 2^3 + 3^3 + ... + k^3 + (k+1)^3 \\
&=& \left(\frac{ (k + 1) * (k + 2)}{2}\right)^2 \\
&& Let's\ try\ to\ recover\ the\ right\ side\ with \\
&& left\ side\ manipulations. \\
P(k + 1) &=& 1 + 2^3 + 3^3 + ... + k^3 + (k+1)^3 \\
&=& P(k) + (k+1)^3 \\
&=& \left(\frac{k * (k + 1)}{2}\right)^2 + (k+1)^3 \\
&& Distribute\ the\ squaring: \\
&=& \frac{k^2 * (k + 1)^2}{4} + (k + 1)^3 \\
&& Multiply\ the\ second\ term\ by\ \frac{4}{4}\ to \\
&& combine\ fractions: \\
&=& \frac{k^2 * (k + 1)^2 + 4 * (k + 1)^3}{4} \\
&& We\ can\ factor\ a\ (k+1)^2\ and\ simplify: \\
&=& \frac{(k+1)^2 * (k^2 + 4 * (k + 1)}{4} \\
&=& \frac{(k+1)^2 * (k^2 + 4k + 4)}{4} \\
&& Factor\ the\ polynomial: \\
&=& \frac{(k+1)^2 * (k + 2)^2}{4} \\
&& Take\ out\ the\ common\ squaring: \\
&=& \left(\frac{(k+1) * (k + 2)}{2}\right)^2 \\
&& QED
\end{eqnarray}
[/math]

There's the right hand side. Pretty easy, no? A trickier problem is in proving that for any n >= 8, you can compose it of multiples of 3 and/or 5. The base step for that is in showing p(8), p(9), and p(10) are true, then you can continue the inductive step.

Another form of mathematical induction is Strong Induction, which is logically equivalent. The base step is the same, but the inductive step must show this:

[math][P(1)\ and\ P(2)\ and\ ...\ and\ P(k)] \to P(k+1).[/math]

It is logically equivalent to normal induction, however, so it's simply a way to use induction that is sometimes more convenient with notation and such. (Such as in the last mentioned problem, or part of the fundamental theorem of arithmetic that states for any integer greater than 1, it is either prime or can be expressed as a product of primes.)

How are they equivalent? Let Q(n) is a statement we are proving with normal induction, and P(n) is the same statement we wish to prove with strong induction. Obviously the base cases are the same: Q(1) = P(1). If Q(n) implies Q(n+1) by normal induction, that means that P(n) which is [P(1) and P(2) and ... and P(n)] is known to be true by normal induction, and thus P(n+1) is also true.

Wikipedia's Page on induction isn't bad, but I wouldn't call it good. Nevertheless, if you're further interested it's not a bad place to start.

---

Posted on 2010-04-03 by Jach

Tags: math, programming

Permalink: https://www.thejach.com/view/id/85

Trackback URL: https://www.thejach.com/view/2010/4/mathematical_induction

Back to the top