By Doron Zeilberger
This version: April 30, 2012.
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).
Added Sept. 29, 2018: Watch the lecture
at the CUNY Kolchin seminar, delivered Sept. 28, 2018.
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,
If you actually want to find the Hadamard factorization, and see examples of
procedure Facrotize,
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),
If you want to have the same as above repeated verbosely
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!.
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),
If you want the C-finite representation for the Binomial Transform of the Fibonacci sequence
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
If you want to get proofs of the identities proved combinatorially in this
trivial paper
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".
If you want the product-of-three-Chebychev-polynomials analog of Lou Shapiro's result (discovery and proof!)
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
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
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
.pdf
.ps
.tex
First written: July 16, 2011.
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).
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
the
input
gives the output.
the input
gives the output.
the
input
gives the output.
the
input
gives the output.
The
input
gives the output.
the
input
gives the output.
the
input
gives the output.
the
input
gives the output.
the
input
gives the output.
the
input
gives the output.
the
input
gives the output.
the
input
gives the output.
the
input
gives the output.
the
input
gives the output.
Doron Zeilberger's List of Papers