When we teach proofs by induction in high school or early undergrad, they tend to be rather simple. Or rather, the induction tends to be "trivial" in the sense that it's obvious
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?
Subscribe to:
Post Comments (Atom)
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 not depend 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