The C-finite Ansatz

By Doron Zeilberger


.pdf   .ps   .tex  
First written: July 16, 2011.

This version: April 30, 2012.


a sanitized version appeared in Ramanujan Journal 31(2013), 23-32.
[In a special issue in honor of Mourad Ismail and Dennis Stanton]

Dedicated with friendship and admiration to Mourad Ismail and Dennis Stanton
This is (mostly) a meta-trivial paper about trivial mathematics. In spite of my constant preachings, (e.g. pages 10-12 of this article and elsewhere!), many people still "prove" these trivial identities by so-called ("complete") mathematical induction, whereas these are all provable using "in-complete" empirical induction, by checking just a few special cases. Other people (myself included!), like mathemagician Art Benjamin "waste" their talent getting admittedly elegant combinatorial proofs, but they should be honest and mention, in the abstract, that what they are proving so eloquently is utterly trivial (as I have already said here).

Some smart people like Herb Wilf, Curtis Greene, Peter Paule, Manuel Kauers, Christoph Koutschan, of course know that, and the recently published masterpiece (by Manuel Kauers and Peter Paule) makes my point very clearly, but the set of people who know it, is still of measure zero.

Recall that a C-finite sequence is a sequence satisfying a linear recurrence equation with constant coefficients (the most famous one being the Fibonacci sequence).

While it is trivial to multiply two C-finite sequences (just like integers), it is not quite so trivial to "factorize" them, or to decide whether they are "prime". The former is plain linear algebra, while the latter is heavy-duty non-linear algebra, getting hairy systems of algebraic equations that can be solved, in principle, using Gröbner bases and the Buchberger algorithm, but, alas, sooner or later it becomes too hard even for the fastest and largest computers.

The main technical novely of this article is a fast "algorithm" (it cheats and uses floating-point arithmetic, please don't tell anyone!) for deciding whether a given C-finite sequence can be written as a product of C-finite sequences of lower order (Procedur IsProdG in the Maple package Cfinite).


Maple Package

While both the mathematics and the meta-mathematics are trivial (in some sense), it was a highly non-trivial task to write the accompaning Maple package Cfinite. What is so nice about it is that most of its procedures are based on pure-guessing, i.e. empirical conjecturing, nevertheless by "general nonsense linear algebra" all the "conjectured" output is ipso-factor completely proved (since it all stays in the decidable C-finite ansatz!).

Sample Input and Output for Cfinite

  • If you want to see an example of procedure KefelR that finds the Hadamard product of two given rational functions, the input gives the output.

  • If you want to see an example of procedure IsProdG that empirically (but very reliably!) determines whether a rational function is the Hadamard product of several smaller rational functions,
    the input gives the output.

  • If you actually want to find the Hadamard factorization, and see examples of procedure Facrotize,
    the input gives the output.

  • If you want to discover factorizations of integer C-finite sequences into products of integer C-fintie sequences of lower order, using procedure FactorizeI1, letting the computer discover, in less than half a second, everything discovered in this paper (as pointed out in this parody, and further elaborated in the present article the proofs are purely routine),
    the input gives the output.

  • If you want to have the same as above repeated verbosely
    the input gives the output.

  • If you you don't like the phrase "the proof is routine", and would like to have everything spelled-out, and get "proofs in the spirit of Zeilberger" (as Mike Hirschhorn would say), to the three identities humanly-proved by James Sellers (in fact, only two of them were proved by him, the third one was left to the reader (assuming that it is correct!). So in particular Shalosh proved a 2002 conjecture of Sellers!.
    The input gives the output.

  • If you want to discover non-linear (polynomial) recurrences of order 1 (for the 2nd-order C-finite sequence of Fibonacci numbers), of order 2 (for the 3rd-order C-finite sequence of Tribonacci numbers), and of order 3 (for the 4th-order C-finite sequence of Quadrobonacci numbers),
    the input gives the output.

  • If you want the C-finite representation for the Binomial Transform of the Fibonacci sequence
    the input gives the output.

  • If you want to see the explicit factorizations for the C-finite sequence of order 4 for the number of perfect matchints of a 4 by n rectangle and for the C-finite sequence of order 8 for the number of perfect matchints of a 6 by n rectangle
    the input gives the output.

  • If you want to get proofs of the identities proved combinatorially in this trivial paper
    the input gives the output.

  • Here is a full dicovery and proof of Louis Shapiro's generating function for proudcts Chebychev polynomials of the second kind, given in his article "A combinatorial proof of a Chebyshev polynomial identity, Discrete Math. 34 (1981), pages 203-206".
    the input gives the output.

  • If you want the product-of-three-Chebychev-polynomials analog of Lou Shapiro's result (discovery and proof!)
    the input gives the output.

  • If you want to see a fully computer-generated book of Fibonacci identities in the style of Curtis Greene and Herb Wilf, as described in this neat article, where the summand is a product of TWO Fibonacci's
    the input gives the output.

  • If you want to see a fully computer-generated book of Fibonacci identities in the style of Curtis Greene and Herb Wilf, as described in this neat article, where the summand is a product of THREE Fibonacci's
    the input gives the output.

  • If you want to see a fully computer-generated book of Fibonacci identities in the style of Curtis Greene and Herb Wilf, as described in this neat article, where the summand is a product of FOUR Fibonacci's
    the input gives the output.


Doron Zeilberger's List of Papers

Doron Zeilberger's Home Page