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


    and references therein, and the survey based on my talk


    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 )

Google+ photo

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

Connecting to %s