1. what structure to do the induction over

2. how to decompose the claim for n+1 so as to invoke the inductive hypothesis

Examples of such simple uses of induction include proving the sum-of-squares-(cubes, etc.) formula, and proving that if a language L is context-free then so is its reversal L^R.

We the instructors somewhat lament this state of affairs, as it gives a misleading impression of induction. A student might dismiss induction as trivial and vacuous, or on the contrary, come away believing that induction is a magical, all-powerful tool that does proofs for you, relieving you of the burden of thought.

So we looked hard for examples of clever use of induction. Here's a good problem to start with:

Let f_p(n) be the sum of the first n powers of p:

f_p(n) = 1^p + 2^p + 3^p + ... + n^p.

For any given p (say, p=3), it is straightforward to verify (by trivial induction!) the f_3(n) is a 4th degree polynomial in n. It's a lot trickier to prove that for

**all**p, f_p(n) is a polynomial in n of degree (p+1). Can you do it? No need to invoke Bernoulli numbers here -- we're not asking for the coefficients of that polynomial. There are a couple of elementary, self-contained proofs -- using clever induction! -- can you find one?

Actually, all of my difficult proofs have been by induction. Various concentration of measure results (Talagrand, Marton, yours truly) have induction at their core. It's a shame we can't present these in a typical undergraduate class (too much overhead), since their use of induction is rather non-trivial.

Do people have more examples of nontrivial proofs by induction?

## 6 comments:

I am not sure I get your f_p(n) examle - isn't this polynomial BY DEFINITION? [At least this is how I read it in

http://mathworld.wolfram.com/Polynomial.html]

If not, what's your definition of "polynomial"?

f_p(n), for some fixed p, is a function of n:

f_p(n) = 1^p + 2^p + 3^p + ... + n^p.

By contrast, a k-degree polynomial in n would be of the form:

a_k n^k + a_{k-1} n^{k-1} + ... + a_1 n + a_0. (*)

Notice that it has at most k+1 terms -- a number that does

notdepend on n, while f_p(n), as written, has n terms. So showing that f_p(n) is of the form (*) with k=p+1 does require some work.Got it. I was definitely wrong about f_p(n) being polynomial "by definition" - it's NOT. But how much work is to proof that (n+1)^p is polynomial in n? Should be easy by yet another [nested] induction ... By the way, we used to joke about proving the Ferma theorem "by induction": assume x^n+y^n=z^n, now switch from n to (n+1) and then take the first derivative {smile}, you'll get:

(n+1)x^n+(n+1)y^n=(n+1)z^n and then divide by (n+1) to comply with the assumtion

It's not enough to show that (n+1)^p is polynomial in n; you must show that the *sum* over i ranging from 1 to n of i^p is polynomial in n. How much work is this? I assigned it as an (extra credit) homework problem in my class and a couple of folks even got it; but it can take a good few hours...

I like the proof of Fermat!

}}you must show that the *sum* over i ranging from 1 to n of i^p is polynomial in n.

Wouldn't that be part of the "assumption" for n?

Induction over n is easy -- it's the induction over p that's hard.

Post a Comment