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,
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.