Zeilberger on induction

Yesterday Doron Zeilberger talked at the British Combinatorial Conference.

As always it was a stimulating performance, challenging the audience’s assumptions (not least about whether it is permissible to use electronic equipment during a lecture). I won’t discuss the whole thing, but the idea seems worth commenting on.

Suppose you ask your students to prove that the sum of squares of the first n natural numbers is n(n+1)(2n+1)/6. Probably they will say: this is true for n = 0 (the empty sum is equal to (0·1·1)/6), and then verify that if it is true for a value n then it is true for n+1 (by adding (n+1)2 to both sides of the equation). There is also, as he said, quite a good chance that they will not really understand what they are doing, but simply try to parrot what their professor told them.

On the other hand, a student who wrote

  • empty sum = 0 = (0·1·1)/6
  • 12 = 1 = (1·2·3)/6
  • 12+22 = 5 = (2·3·5)/6
  • 12+22+32 = 14 = (3·4·7)/6

would get 9 out of 10 from Doron, because all you have to do is mutter an incantation and this is a perfectly valid proof.

In this case, the incantation [my word, he just muttered “mutter something”] is: “both sides are obviously polynomials of degree 3; if they agree at four points then they are the same”.

In a slightly more elevated form, this principle applies to a lot of mathematics. He claims that many papers are published proving results which could be done just be a finite calculation. In his words, every theorem is trivial in God’s eyes, so no paper should be rejected on the grounds of triviality; but some papers, like cigarette packets, should carry warnings that the theorem can be proved by calculation.

His opinion of the Riemann hypothesis is: Odlyzko proved that the first billion Riemann zeros have real part 1/2; sometime in the next fifty years someone will come up with the appropriate incantation to show that only a finite amount of calculation is needed, maybe as few as 50 zeros, so Odlyzko did far more than was necessary.

As usual with Doron’s lectures, I was entertained but not convinced.

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in doing mathematics and tagged . Bookmark the permalink.

4 Responses to Zeilberger on induction

  1. D. Eppstein says:

    Ok, so why is $\sum_{i=0}^n i^2$ “obviously a polynomial of degree three? It doesn’t have the syntactic form of a polynomial. I mean, yes, I know it’s a polynomial of degree three but seeing the word “obvious” makes me suspicious. It seems like it’s hiding a theorem about “sums of polynomials are polynomials” that (when made more explicit) might already have the result you’re trying to prove as a special case, so that invoking the theorem and then listing some examples is no more powerful than invoking the theorem without the examples.

    • Sorry, a bit of sleight of hand on my part. Looking at differences you can see that a polynomial of degree d satisfies a (d+1)-term recurrence; then sums of sequences satisfying a recurrence theselves satisfy a recurrence. But I agree that something is hidden here; that is one of my problems with this philosophy (it regards this kind of argument as less deep than the laundry-list calculation).

  2. Doron Zeilberger says:

    First, thank to Peter for this nice account of my talk. Regarding David Eppstein’s remark, you prove
    ONE and FOR ALL a GENERAL theorem

    The indefinite sum of a polynomial of degree d is d+1

    this can be done in several ways. My favorite is to use the fact that the natural basis
    for discrete math are the polynomials f_k(n):=binomial(n,k) and then this fact follows
    from the Pascal triangle recurrence. Another way is linear algebra use undetmined coefficients
    writing a generic polynomial of degree d+1 and then solving a system of linear equations
    with d+2 unknowns and d+1 equations.

    This general theorem may one day completely proved by computer, once there is an infra-structure (it may be already in ATP efforts, that I am not familiar with, but that’s not the point)
    But ONCE this theorem is established ANY statement of the form

    Sum(f(i),i=1..N)= F(N)

    is checkable by checking if for 0<=n<=N+1 .

    Another way, by the DEFINITION of indefinite sum any such statement is
    equivalent to

    F(N)-F(N-1)=f(N), and F(0)=0

    where both sides are polynomials of degree d.

    But that's just a trivial metaphor. In my talk I talked about the C-finite ansatz and there
    are lots of papers (and books) that prove identities amongsts them, see

    Click to access cfinite.pdf

    and references therein, and the survey based on my talk

    Click to access ritsuf.pdf

    BUT even this is a trivial metaphor. There are many other (some already known,
    e.g. the holonomic ansatz and Silviu Radu's beautiful work on automating
    Ramanujan-type congruences), and some yet-to-be discovered, including the
    fact that that to prove that the real part of all the non-trivial zeros of zeta(s)
    equal 1/2 follow from the fact that is is true for the first one hundred (or whatever).

    -Doron Zeilberger

    • Doron, Thanks for your comments, your very stimulating talk at Royal Holloway, and for several conversations there – and for this comment. Peter.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.