The C-FINITE ANSATZ

Doron ZEILBERGER^{1}

Dedicated with friendship and admiration to Mourad Ismail and Dennis Stanton

Apology

While this article is dedicated to both Mourad Ismail and Dennis Stanton, it does not directly reference any of their works. The main reason is that I only talk about the most trivial kind of recurrences: linear and constant coefficients. But try searching Ismail AND Recurrences or

Stanton AND Recurrences in the database MathSciNet (or Google Scholar) and you would see

that both Mourad and Dennis are great gurus in recurrences, so the subject matter of this paper is not entirely inappropriate as a tribute to them. The present work is also largely experimental, and Dennis Stanton is a great pioneer in computer experimentations!

PROLOGUE

Before starting the paper itself, let me very briefly mention what I talked about at the wonderful conference

q-Series 2011: An International Conference on q-Series, Partitions and Special Functions,

“honouring Mourad Ismail and Dennis Stanton for their valuable contributions to Number theory and Special Functions throughout their careers”, that took place on March 14-16, 2011 at Georgia Southern University, and perfectly organized by Drew Sills. My plenary talk was entitled

“Some Golden Oldies of Mourad Ismail and Dennis Stanton”

and the abstract was short and sweet:

“This is the time to recall some of the beautiful mathematics that I learned from Dennis and Mourad”.

I talked, inter alia, about Dennis Stanton’s amazing article

“A short proof of a generating function for Jacobi polynomials”, that appeared in Proc. Amer. Math. Soc. 80 (1980), 398-400, where he used an idea that he attributed to his advisor, Dick Askey, but that Askey modestly claims goes back to Hermite, to give a very soft and elegant proof of a very hairy formula of Bailey.

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg at math dot rutgers dot edu , http://www.math.rutgers.edu/~zeilberg/ . First written: July 16, 2011. This version: May 1, 2012. Accompanied by Maple package Cfinite downloadable from http://www.math.rutgers.edu/~zeilberg/tokhniot/Cfinite . Supported in part by the NSF.

Another thing that I talked about was Mourad Ismail’s gorgeous article

“A simple proof of Ramanujan’s _{1}ψ_{1} sum”,

that contained the proof-from-the-book of Ramanujan’s lovely formula

∑_{n=−∞}^{∞} \frac{(a)_{n}}{(b)_{n}} t^{n} = \frac{(b/a)_{∞}(at)_{∞}(q/at)_{∞}(q)_{∞}}{(q/a)_{∞}(b/at)_{∞}(b)_{∞}(t)_{∞}} ,

(where, as usual (A)_{n} := (1 − A) ⋯ (1 − q^{n−1}A), if n ≥ 0, (A)_{n} := 1/((1 − q^{−1}A) ⋯ (1 − q^{n}A)), if n < 0, and (A)_{∞} := (1 − A)(1 − qA)(1 − q^{2}A) ⋯) .

Mourad’s article appeared in the proceedings (of the AMS) three years earlier (PAMS 63 (1977), 185-186.) This proof was already immortalized and canonized (and shrunk to half a page!) in Appendix C of George Andrews’ classic monograph, CBMS #66, that appeared in 1986 and was based on ten beautiful lectures delivered at an NSF-CBMS conference that took place in 1985, at Arizona State University, and organized by Mourad Ismail and Ed Ihring.

In my talk, I mentioned that while Mourad’s proof certainly qualifies to be included in “God’s book”, since, like Mourad and George, God is, by definition, an infinitarian, it does not qualify to be included in my book. It said (in George’s rendition, my emphasis)

“Regarding the left-hand side as an analytic function of b for |b| < 1 … ” .

Then one plugs-in b = q^{N} (N = 0, 1, 2, …), getting the trivial q-binomial theorem, and one sees that the left side minus the right side vanishes for “infinitely” many values of b and then uses the “fact” that an “analytic” function inside |b| < 1 that vanishes on a “convergent” “infinite” sequence “must” be identically zero.

Of course, to finitists like myself, this proof is entirely non-rigorous, since it uses fictional things like so-called analytic functions, and uses heavy guns from a sophisticated (and flawed!) “infinite” theory.

But don’t despair! It is very easy to translate Mourad’s flawed proof and make it entirely legit, and in the process make it even nicer. Replace the phrase

“analytic function of b defined in |b| < 1”

by

“bilateral formal power series in t whose coefficients are rational functions of b” ,

and note that the difference of the left and right sides is a bilateral formal power series (in t) whose coefficients are rational functions of b (and of course also of a and q but that’s irrelevant). A rational function of b, whose degree of the numerator is, say, m, is identically zero if it vanishes at m + 1 distinct values of b, so the “infinitely” many points b = q^{N} (N = 0, 1, 2 …) are more than enough.

[We leave it to the readers to convince themselves that everything makes finitistic sense here, even though it is true (as an infinitiarian referee pointed out) that sometimes the product of two bilateral formal power series is nonsense (e.g. (∑_{n=−∞}^{∞} t^{n})^{2}) everything here makes perfect sense, since the “infinite sums” that show up are legitimate formal power series in the parameters.]

FEATURE PRESENTATION

The Maple package Cfinite

This article is accompanied by the Maple package Cfinite downloadable directly from

http://www.math.rutgers.edu/~zeilberg/tokhniot/Cfinite,

or from the “front”

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/cfinite.html,

where one can find links to fifteen sample input and output files, some of which are mentioned throughout this paper.

C-finite Sequences

Recall that a C-finite sequence {a(n)}, n = 0, 1, … is a sequence that satisfies a linear-recurrence equation with constant coefficients. It is known (but not as well-known as it should be!) and easy to see (e.g. [Z2],[KP]) that the set of C-finite sequences is an algebra. Even though a Cfinite sequence is an “infinite” sequence, it is in fact, like everything else in mathematics (and elsewhere!) a finite object. An order-L C-finite sequence a(n) is completely specified by the coefficients c_{1}, c_{2}, …, c_{L} of the recurrence

a(n) = c_{1}a(n − 1) + c_{2}a(n − 2) + … + c_{L}a(n − L) ,

and the initial conditions

a(0) = d_{1} , …, a(L − 1) = d_{L} .

So a C-finite sequence can be coded in terms of the 2L “bits” of information

[[d_{1}, …, d_{L}], [c_{1}, …, c_{L}]] .

For example, the Fibonacci sequence is written:

[[0, 1], [1, 1]].

Since this ansatz (see [Z2]) is fully decidable, it is possible to decide equality, and evaluate ab initio, wide classes of sums, and things are easier than the holonomic ansatz[Z1]. The wonderful new book by Manuel Kauers and Peter Paule[KP] also presents a convincing case. See [HX][GW][Kau][KZ] for very interesting and efficient algorithms.

Rational Generating Functions

Equivalently, a C-finite sequence is a sequence {a(n)} whose ordinary generating function, ∑_{n=0}^{∞} a(n)z^{n}, is rational and where the degree of the denominator is more than the degree of the numerator. These come up a lot in combinatorics and elsewhere (e.g. formal languages). See the old testament[St2], chapter 4, and the new testament[KP], chapter 4.

[To go from a C-finite representation to a rational function, use CtoR(C,z); in Cfinite. To go the other way, do RtoC(f,z); .]

Etymology

I coined the term C-finite sequence in [Z1], as a hybrid analog of Richard Stanely’s [St1] names “Dfinite function” and “P -recursive sequence”. If I had to do it over I would call them “C-recursive sequences”, but it is too late now since the term C-finite already made it into the wonderful undergraduate textbook [KP], and it is also in the title of the important paper [GW].

Zeilberger-style proofs: You (Often) CAN generalize from FINITELY Many Cases

The conventional wisdom of mathematics (at least for the last 2500 years), preached to us by our teachers and that, in turn, we preach to our students, is that you can’t generalize from finitely many cases. While this is certainly true sometimes, it is not always true. Many times you can generalize from finitely many cases, just like natural scientists.

Michael Hirschhorn kindly called this style of proof “in the spirit of Zeilberger”, see his beautiful proof[H] of an amazing identity of Ramanujan, that gives infinitely many “almost” counterexamples to Fermat’s Last Theorem for n = 3, namely infinitely many triples {(a, b, c)} such that a^{3}+b^{3}+c^{3} = ±1.

But not Everyone Knows About this Style of Proof

Everybody knows that numerical identities like 2 + 7 = 3 × 3 are routinely provable, using standard algorithms. But many smart people are not fully aware that identities amongst C-finite sequences are equally routine. There are hundreds (possibly thousands) of articles like this in the literature, sometimes giving “elegant” proofs of such trivial results. While it is always nice to have elegant proofs, honesty requires that the authors state clearly, in the abstract, that the result that they are elegantly proving is routinely provable. See my opinion [Z4].

The First Reason for This Article: Educating Since so many people are not (fully) aware of the triviality of the C-finite ansatz (or more politely, there being an algorithmic proof theory for it), and in spite of the articles and book cited above, I thought that it is a good idea to make it better known. The Second Reason for This Article: Implementation While Curtis Greene and Herb Wilf [GW] and Manuel Kauers[Kau] (see also [KZ]) already have Mathematica implementations of many operations on C-finite sequences, and possibly also Maple ones, I thought that it is a good idea to design a C-finite calculator, that also enables one to discover new identities. The novelty, in that part, is the approach, pure guessing! (that is justified a posteriori). The Third Reason for This Article: Factorization The truly novel part (I believe) is in addressing the problem of factorization. See below. The C-finite Calculator In order to decipher a C-finite sequence where the first few terms are given, all you need is use linear algebra to “guess” (using the ansatz) the c’s (you already know the d’s). See Procedure GuessRec in Cfinite. If you have two C-finite sequences C_{1} and C_{2} of order L_{1} and L_{2}, you don’t need any fancy footwork to figure out the sequence C_{1} + C_{2} (of order ≤ L_{1} + L_{2}) and the sequence C_{1}C_{2} (of order ≤ L_{1}L_{2}). All you need is to crank out 2(L_{1} + L_{2} + 4) (the +4 is for safety reasons) and 2(L_{1}L_{2} + 4) terms, respectively, and let the computer guess the C-finite description, completely by guessing, using undetermined coefficients that is implemented by Procedure GuessRec in Cfinite.

[ I thank one of the referees for pointing out that the “guessing” of C-finite sequences may be handled efficiently by the Berlekamp-Massey algorithm, see the wikipedia article, but for us naive linear algebra suffices].

So it is (very!) easy to multiply C-finite sequences, in other words, from the C-finite descriptions of C_{1} and C_{2} get the C-finite description of C_{1}C_{2} (by C_{1}C_{2} we mean the sequence whose n-th term is C_{1}(n)C_{2}(n), in terms of their generating functions it is called the Hadamard product).

Procedures Khibur and Kefel of Cfinite

In order to add two C-finite sequences C1 and C2, simply type

Khibur(C1,C2); .

In order to multiply type:

Kefel(C1,C2); ,

and for a verbose version, presenting fully detailed proofs in the spirit of Zeilberger, type

KefelV(C1,C2); .

An Example of Using Procedure Kefel Let {U_{n}(x)}_{n=0}^{∞} be the sequence of Chebyshev polynomials of the second kind, i.e. the sequence of polynomials in x defined by

∑_{n=0}^{∞} U_{n}(x)t^{n} = \frac{1}{1 − 2xt + t^{2}} .

Typing CtoR(Kefel(Ux(a),Ux(b)),t); would give you, in a few seconds, the following result[Sh] Lou Shapiro’s Product-Of-Two-Chebyshev-Polynomials Identity

∑_{n=0}^{∞} U_{n}(a)U_{n}(b) t^{n} = \frac{1 − t^{2}}{1 − 4 abt − (−4 a^{2} + 2 − 4 b^{2}) t^{2} − 4 abt^{3} + t^{4}} .

Typing

CtoR(Kefel(Kefel(Ux(a),Ux(b)),Ux(c)),t);

yields, in a few more seconds, the following much deeper result Shalosh B. Ekhad’s Product-Of-Three-Chebyshev-Polynomials Identity

∑_{n=0}^{∞} U_{n}(a)U_{n}(b)U_{n}(c)t^{n} = \frac{N(t)}{D(t)} ,

where the polynomials N(t) are D(t) are as follows.

N(t) = 1 + (−4 a^{2} − 4 b^{2} − 4 c^{2} + 3) t^{2} + 16 abct^{3} + (−4 a^{2} − 4 b^{2} − 4 c^{2} + 3) t^{4} + t^{6} ,

D(t) = t^{8}−8 abct^{7}+(16 a^{2}b^{2} + 16 a^{2}c^{2} − 8 a^{2} + 16 b^{2}c^{2} − 8 b^{2} − 8 c^{2} + 4) t^{6}+(−32 a^{3}bc + 40 abc − 32 ab^{3}c − 32 abc^{3}) t^{5}+ (16 a^{4} + 64 a^{2}b^{2}c^{2} − 16 a^{2} + 16 b^{4} − 16 b^{2} + 6 + 16 c^{4} − 16 c^{2}) t^{4}+(−32 a^{3}bc + 40 abc − 32 ab^{3}c − 32 abc^{3}) t^{3}

+ (16 a^{2}b^{2} + 16 a^{2}c^{2} − 8 a^{2} + 16 b^{2}c^{2} − 8 b^{2} − 8 c^{2} + 4) t^{2} − 8 abct + 1 .

The (Computationally) Hard Problem of Factoring C-finite Sequences

[Note: we are only treating here the generic case where the characteristic polynomial of the recurrence, (alias the denominator of the rational function) has distinct roots. The case of multiple roots, (in particular, polynomial sequences, where the multiple root is 1), should require an extension.]

Alas, going backwards (just like in integer factorization, that makes our ATM cards hopefully secure) is not so easy! If you are given a C-finite sequence of order L, say, and L is composite, L = L_{1}L_{2}, (with L_{1}, L_{2} > 1) you would like to know whether there exist C-finite sequence C_{1} and C_{2} such that C = C_{1}C_{2}, and if they do, find them. One way, that works for small L, is to do symbolic multiplication of generic C-finite sequences, and then try to solve, by matching coefficients, the resulting non-linear system of algebraic equations, using the Buchberger algorithm. [This is implemented in procedure Factorize of the Maple package Cfinite .] But for larger orders this is hopeless!

Procedure FactorizeI1 does the same by brute force, but only handles integer sequences. While it can’t go very far, it discovered, ab initio, in less than half a second, the three factorizations in [Se]. See

http://www.math.rutgers.edu/~zeilberg/tokhniot/oCfinite4 .

For a more verbose version see

http://www.math.rutgers.edu/~zeilberg/tokhniot/oCfinite5 ,

and for a completely spelled-out proofs, in the spirit of Zeilberger, see

http://www.math.rutgers.edu/~zeilberg/tokhniot/oCfinite5a .

Why is this problem interesting?

Two great landmarks of Statistical Physics are the Onsager[O] solution of the two-dimensional Ising model and the Kasteleyn[Kas]- Temperley-Fisher[TF] solutions of the dimer problem. They use lots of human (ad-hoc) ingenuity to first get an explicit answer for a finite strip of arbitrary (symbolic) width. They then take the so-called thermodynamic limit. It turns out that in either case, the m-wide strip sequence is a C-finite sequence of order 2^{m}. Surprisingly, in both cases they happen to be products of m C-finite sequences of order 2 (different, but closely related).

Since nowadays computers can automatically, completely rigorously, figure out the C-finite description for each strip of width m, for specific, numeric m, ([EZ],[Z3]) (in practice easily for m ≤ 10), knowing how to “factorize” them explicitly, would lead one to conjecture both solutions, with fully rigorous proofs for m ≤ 10, and with larger computers, beyond. Since physicists are not as hung-up as mathematicians about rigorous proofs, that would have been a great breakthrough, even without the human proofs for general m. Besides, the explicit “conjecture” discovered by the computer might suggest and inspire (to obtuse mathematicians) a formal proof.

The “Cheating” Algorithm

Since it is so hard to factorize explicitly, it is still nice to know, as fast as possible, whether or not the inputted C-finite sequence is factorizable. If it is not, it would be stupid to waste efforts in trying to factorize it. If it is, then it is worthwhile applying for time on a bigger computer.

Recall (Binet) that “generically” every C-finite sequence [[d_{1}, …, d_{L}], [c_{1}, …, c_{L}]] of order L can be written as a linear combination

C(n) = ∑_{i=1}^{L} a_{i}α_{i}^{n} ,

where the a_{i}’s depend on the initial conditions, and the α_{i}’s are the roots of the characteristic equation

z^{L} − ∑_{i=1}^{L} c_{i}z^{L−i} = 0 .

So if C := C_{1}C_{2} and the roots of C_{1} and C_{2} are α_{1}, …, α_{L_{1}}, and β_{1}, …, β_{L_{2}} respectively, then the roots of C, let’s call them γ_{1}, …, γ_{L_{1}L_{2}}, consist of the Cartesian product

{α_{i}β_{j} | 1 ≤ i ≤ L_{1} , 1 ≤ j ≤ L_{2}} .

with L := L_{1}L_{2} elements.

If this is indeed the case, then the set of L^{2} ratios

\{\frac{γ_{i}}{γ_{j}} | 1 ≤ i, j ≤ L\} ,

would have a certain profile of repetitions that the computer can easily figure out for arbitrary symbols α_{1}, …, α_{L_{1}} and β_{1}, …, β_{L_{2}}.

Procedure ProdIndicator of the Maple package Cfinite

Procedure ProdIndicator(m,n) yields the profile of repetitions indicative of the characteristic roots of a C-finite sequence that happens to be the product of a C-finite sequence of order m and a C-finite sequence of order n.

For example, ProdIndicator(2,2) yields:

[1, 1, 1, 1, 2, 2, 2, 2, 4] .

To understand what is going on, let’s work it out by hand.

γ_{1} = α_{1}β_{1} , γ_{2} = α_{1}β_{2} , γ_{3} = α_{2}β_{1} , γ_{4} = α_{2}β_{2} .

So

\frac{γ_{1}}{γ_{1}} = \frac{α_{1}β_{1}}{α_{1}β_{1}} = 1 , \frac{γ_{1}}{γ_{2}} = \frac{α_{1}β_{1}}{α_{1}β_{2}} = \frac{β_{1}}{β_{2}} , \frac{γ_{1}}{γ_{3}} = \frac{α_{1}β_{1}}{α_{2}β_{1}} = \frac{α_{1}}{α_{2}} , \frac{γ_{1}}{γ_{4}} = \frac{α_{1}β_{1}}{α_{2}β_{2}} ,

\frac{γ_{2}}{γ_{1}} = \frac{α_{1}β_{2}}{α_{1}β_{1}} = \frac{β_{2}}{β_{1}} , \frac{γ_{2}}{γ_{2}} = \frac{α_{1}β_{2}}{α_{1}β_{2}} = 1 , \frac{γ_{2}}{γ_{3}} = \frac{α_{1}β_{2}}{α_{2}β_{1}} , \frac{γ_{2}}{γ_{4}} = \frac{α_{1}β_{2}}{α_{2}β_{2}} = \frac{α_{1}}{α_{2}} ,

\frac{γ_{3}}{γ_{1}} = \frac{α_{2}β_{1}}{α_{1}β_{1}} = \frac{α_{2}}{α_{1}} , \frac{γ_{3}}{γ_{2}} = \frac{α_{2}β_{1}}{α_{1}β_{2}} , \frac{γ_{3}}{γ_{3}} = \frac{α_{2}β_{1}}{α_{2}β_{1}} = 1 , \frac{γ_{3}}{γ_{4}} = \frac{α_{2}β_{1}}{α_{2}β_{2}} = \frac{β_{1}}{β_{2}} ,

\frac{γ_{4}}{γ_{1}} = \frac{α_{2}β_{2}}{α_{1}β_{1}} , \frac{γ_{4}}{γ_{2}} = \frac{α_{2}β_{2}}{α_{1}β_{2}} = \frac{α_{2}}{α_{1}} , \frac{γ_{4}}{γ_{3}} = \frac{α_{2}β_{2}}{α_{2}β_{1}} = \frac{β_{2}}{β_{1}} , \frac{γ_{4}}{γ_{4}} = \frac{α_{2}β_{2}}{α_{2}β_{2}} = 1 .

We see that the multi-set of all 16 ratios has: four occurrences of 1, two occurrences each of \frac{β_{1}}{β_{2}} ,\frac{β_{2}}{β_{1}} , \frac{α_{1}}{α_{2}} ,\frac{α_{2}}{α_{1}} , and four singletons, namely \frac{α_{2}β_{2}}{α_{1}β_{1}} , \frac{α_{2}β_{1}}{α_{1}β_{2}} and their reciprocals.

Now for the proposed C-finite sequence of order L, find (in floating point!, but with Digits:=100;) approximations to the roots of its characteristic equation, then form these L^{2} ratios, and group them into classes with the “same” value (up to the agreed-on approximation). If you get the same pattern of repetition, then you have proved (empirically) that the given C-finite sequence C, of order L = L_{1}L_{2}, is indeed the product of C-finite sequences of orders L_{1} and L_{2}. Procedure IsProd in Cfinite implements this algorithm. See the source code for more details.

If C has order L = L_{1}L_{2} ⋯ L_{r}, and you want to find out whether C is a product of r C-finite sequences of orders L_{1}, …, L_{r} you do the analogous thing. Procedure IsProdG in Cfinite implements this more general scenario.

Output

Using the output from [EZ] we confirmed that the straight enumeration dimer problems for strips of width ≤ 10 are indeed products of C-finite sequences of order 2. See

http://www.math.rutgers.edu/~zeilberg/tokhniot/oCfinite2 .

Using the output from [Z3] we confirmed that the weighted enumeration dimer problem for strips of width ≤ 10 indeed are products of C-finite sequences of order 2 for many random numerical assignments of the weights.

As for the actual factorization, we were, on our modest computer, only able to find them (from scratch, without peeking at the answer) for m ≤ 7, but a more clever implementation, and a larger computer, no doubt would be able to conjecture ab initio (without any human ad-hocery!) the exact solution of the dimer problem derived and proved in [Kas] and [TF]. Ditto for Onsager’s [O] (human) tour-de-force.

Sample output for some of the other procedures (e.g BT for the Binomial Transform and GuessNLR for finding non-linear (polynomial) recurrences of lower-order than the (linear) order of a given C-finite sequence) can be obtained from the front of the present article:

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/cfinite.html .

Encore: 1142 beautiful and deep Greene-Wilf-style Fibonacci identities in less than 4400 seconds See the computer-generated webbook

http://www.math.rutgers.edu/~zeilberg/tokhniot/oCfinite13 .

For simpler identities see also

http://www.math.rutgers.edu/~zeilberg/tokhniot/oCfinite11 and
http://www.math.rutgers.edu/~zeilberg/tokhniot/oCfinite12 .

These fascinating new identities can keep bijective combinatorialists busy for the next one hundred years. Each of these identities cries out for an insightful, elegant, combinatorial proof! Acknowledgement: I’d like to thank the referees for their insightful remarks and minor corrections. References

[EZ] Shalosh B. Ekhad and Doron Zeilberger, Automatic Generation of Generating Functions for Enumerating Matchings, Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, April 29,

2011, http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/shidukhim.html .

[GW] Curtis Greene and Herbert S. Wilf, Closed form summation of C-finite sequences, Trans. Amer. Math. Soc. 359(2007), 1161-1189, http://arxiv.org/abs/math/0405574 .

[H] M.D. Hirschhorn, A proof in the spirit of Zeilberger of an amazing identity of Ramanujan, Math. Mag. 4 (1996), 267-269.

[HX] Qing-Hu Hou and Guoce Xin Constant term evaluation for summation of C-finite sequences, DMTCS proc. AN, 2010, 761-772.

[Kas] P. W. Kasteleyn, The statistics of dimers on a lattice: I. The number of dimer arrangements in a quadratic lattice, Physica 27 (1961), 1209-1225.

[Kau] Manuel Kauers, SumCracker: A package for manipulating symbolic sums and related objects, Journal of Symbolic Computation 41 (2006), 1039-1057,

http://www.risc.uni-linz.ac.at/people/mkauers/publications/kauers06h.pdf .

[KP] Manuel Kauers and Peter Paule, “The Concrete Tetrahedron”, Springer, 2011.

[KZ] Manuel Kauers and Burkhard Zimmermann, Computing the algebraic relations of C-finite sequences and multisequences, Journal of Symbolic Computation 43 (2008), 787-803.

[O] Lars Onsager, Crystal statistics, I. A two-dimensional model with an order-disorder transition, Phys. Rev. 65(1944), 117-149.

[Se] James A. Sellers, Domino Tilings and Products of Fibonacci and Pell Numbers, Journal of Integer Sequences, 5(2002), 02.1.2,

http://www.cs.uwaterloo.ca/journals/JIS/VOL5/Sellers/sellers4.pdf .

[Sh] Louis Shapiro, A combinatorial proof of a Chebyshev polynomial identity, Discrete Math. 34(1981), 203-206 .

[St1] Richard Stanley, Differentiably finite power series, European Journal of Combinatorics 1(1980),

175-188, http://www-math.mit.edu/~rstan/pubs/pubfiles/45.pdf .

[St2] Richard Stanley, “Enumerative combinatorics”, volume 1, Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986, second printing, Cambridge University Press, Cambridge, 1996.

[TF] H. Temperley and M. Fisher, Dimer Problems in Statistical Mechanics-an exact result, Philos. Mag. 6 (1961), 1061-1063.

[Z1] Doron Zeilberger, A Holonomic Systems Approach To Special Functions, J. Computational and Applied Math 32(1990), 321-368,

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/holonomic.pdf .

[Z2] Doron Zeilberger, An Enquiry Concerning Human (and Computer!) [Mathematical] Understanding in: C.S. Calude ,ed., “Randomness and Complexity, from Leibniz to Chaitin”, World Scientific, Singapore, Oct. 2007,

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/enquiry.html .

[Z3] Doron Zeilberger, Automatic CounTilings, Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, Jan. 20, 2006; also published in Rejecta Mathematica 1 (2009), 10 -17,

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/tilings.html .

[Z4] Doron Zeilberger, Opinion 89: Mental Math Whiz [And Very Good Mathematician] Art Benjamin Should be Aware that not only his Night Job, but also some parts of his “Day Job” should be clearly labeled “For Entertainment Only” ,

http://www.math.rutgers.edu/~zeilberg/Opinion89.html .