Hadamard Products and Tilings

Jong Hyun Kim Department of Mathematics Brandeis University Waltham, MA 02454-9110 USA

                      jhkim@brandeis.edu

Abstract Shapiro gave a combinatorial proof of a bilinear generating function for Chebyshev

polynomials equivalent to the formula

\frac{1}{1 − ax − x^{2}} ∗ \frac{1}{1 − bx − x^{2}} = \frac{1 − x^{2}}{1 − abx − (2 + a^{2} + b^{2})x^{2} − abx^{3} + x^{4}} ,

where ∗ denotes the Hadamard product. In a similar way, by considering tilings of a 2 × n rectangle with 1 × 1 and 1 × 2 bricks in the top row, and 1 × 1 and 1 × n bricks in the bottom row, we find an explicit formula for the Hadamard product

\frac{1}{1 − ax − x^{2}} ∗ \frac{x^{m}}{1 − bx − x^{n}} .

1 Introduction

The Fibonacci numbers (\underline{A000045}) are defined by F_{0} = 0, F_{1} = 1, and for n ≥ 2, F_{n} = F_{n−1} + F_{n−2}. It is convenient to write f_{n} for F_{n+1} so that f_{n} is the number of ways to tile a 1 × n strip with 1 × 1 square bricks and 1 × 2 rectangular bricks [1]. The number of tilings of a 1×n strip with k bricks is the coefficient of x^{n} in (x+x^{2})^{k}, so we know that the generating function [2] for Fibonacci numbers is

∑_{n=0}^{∞} f_{n}x^{n} = \frac{1}{1 − x − x^{2}} .

We now define the polynomial f_{n}(a) by

\frac{1}{1 − ax − x^{2}} = ∑_{n=0}^{∞} f_{n}(a)x^{n}.  (1)

Then we have that f_{n}(1) = f_{n} and f_{n}(a) can be interpreted as the sum of the weights of tilings of a 1 × n strip with 1 × 1 square bricks weighted by a and 1 × 2 rectangular bricks weighted by 1. By applying the geometric series and binomial series to (1 − ax − x^{2})^{−1} we obtain that (\underline{A011973})

f_{n}(a) = \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ k=0 \end{matrix} \binom{n − k}{k}a^{n−2k}.  (2)

So, f_{0}(a) = 1, f_{1}(a) = a, f_{2}(a) = 1 + a^{2}, f_{3}(a) = 2a + a^{3}, f_{4}(a) = 1 + 3a^{2} + a^{4}, etc.

Louis W. Shapiro [5] gave a combinatorial proof of a bilinear generating function for Chebyshev polynomials equivalent to

∑_{n=0}^{∞} f_{n}(a)f_{n}(b)x^{2n} = \frac{1 − x^{4}}{1 − abx^{2} − (2 + a^{2} + b^{2})x^{4} − abx^{6} + x^{8}} .  (3)

The Hadamard product G ∗ H of the power series G(x) = ∑_{k≥0} g(k)x^{k} and H(x) = ∑_{k≥0} h(k)x^{k} is defined by

G ∗ H = ∑_{k≥0} g(k)h(k)x^{k}.

If G(x) and H(x) are rational power series, then so is the Hadamard product G ∗ H [6, p. 207].

Using the notation of Hadamard product, we can rewrite (3) as

\frac{1}{1 − ax − x^{2}} ∗ \frac{1}{1 − bx − x^{2}} = \frac{1 − x^{2}}{1 − abx − (2 + a^{2} + b^{2})x^{2} − abx^{3} + x^{4}} .  (4)

In this paper, I will review Shapiro’s proof of (4), and extend this approach to find an explicit formula for the Hadamard product

\frac{1}{1 − ax − x^{2}} ∗ \frac{x^{m}}{1 − bx − x^{n}} .

The MacMahon operator Ω_{≥} is defined on Laurent series by

Ω_{≥} ∑_{n=−∞}^{∞} a_{n}x^{n} = ∑_{n=0}^{∞} a_{n}.

We can express the MacMahon operator Ω_{≥} in terms of Hadamard products. Let G(x) = ∑_{i≥0} g(i)x^{i} and H(x) = ∑_{j≥0} h(j)x^{j} be power series. Then

G(x)H(x^{−1}) = ∑_{i≥0} ∑_{j≥0} g(i)h(j)x^{i−j}.

Since ∑_{i≥0}(∑_{j≤i} h(j))x^{i} = H(x)/(1 − x), we have that

Ω_{≥}G(x)H(x^{−1}) = ∑_{i=0}^{∞} ∑_{j=0}^{i} g(i)h(j) = (G(x) ∗ \frac{H(x)}{1 − x})|_{x=1}.  (5)

In [3], G.-N. Han used computer algebra to show that

Ω_{≥} \frac{1}{(1 − zx − zx^{2})(1 − y/x − y/x^{2})} = \frac{1 + z^{2}y}{(1 − 2z)(1 − 3zy − z^{2}y − zy^{2})}.

We will derive Han’s result from our formula for 1/(1 − ax − x^{2}) ∗ 1/(1 − bx − x^{3}).

2 Hadamard products

Now we review Shapiro’s [5] proof of a formula for the Hadamard product

\frac{1}{1 − ax − x^{2}} ∗ \frac{1}{1 − bx − x^{2}} = ∑_{k=0}^{∞} f_{k}(a)f_{k}(b)x^{k}.  (6)

We consider (6) as counting pairs of tilings. The coefficient f_{k}(a)f_{k}(b) of x^{k} counts tilings of a 2 × k rectangle with 1 × 1 square bricks weighted by a and 1 × 2 rectangular bricks weighted by 1 in the top row, and 1 × 1 square bricks weighted by b and 1 × 2 rectangular bricks weighted by 1 in the bottom row, as in the following figure:

\begin{matrix}a & & & a & & a & a & a & & & a & a \\ b & b & b & & b & & & & b & b & & b \end{matrix}

The vertical line segments passing from top to bottom serve to factor these tilings into tilings of smaller length. For example, the following figure shows the factorization of the above figure.

\begin{matrix}a & & & a & & a & a & a & & & a & a \\ b & b & b & & b & & & & b & b & & b \end{matrix}

Let’s define a prime block to be a tiling that cannot be factored any further without cutting it through the middle of some brick. So these prime blocks can be classified as follows:

The prime block of length 1:

The prime blocks of length 2:

,  ,

The prime blocks of length 2k + 1 ≥ 3, together with the result of interchanging the two rows:

\begin{aligned}⋯ \\ & ⋯ \end{aligned}

The prime blocks of length 2k ≥ 4, together with the result of interchanging the two rows:

\begin{aligned}⋯ \\ & ⋯ \end{aligned}

Thus the generating function P_{2}(x) for the weighted prime blocks of the Hadamard product is

P_{2}(x) = abx + (1 + a^{2} + b^{2})x^{2} + ∑_{k=1}^{∞} 2abx^{2k+1} + ∑_{k=2}^{∞}(a^{2} + b^{2})x^{2k}

= abx + (1 + a^{2} + b^{2})x^{2} + \frac{2abx^{3}}{1 − x^{2}} + \frac{(a^{2} + b^{2})x^{4}}{1 − x^{2}}

= \frac{abx + (1 + a^{2} + b^{2})x^{2} + abx^{3} − x^{4}}{1 − x^{2}} .

Since any tiling can be factored uniquely as a sequence of prime blocks [4, p. 1027–1030], we have (1 − ax − x^{2})^{−1} ∗ (1 − bx − x^{2})^{−1} = 1/(1 − P_{2}(x)). So we obtain the following explicit formula:

\frac{1}{1 − ax − x^{2}} ∗ \frac{1}{1 − bx − x^{2}} = \frac{1 − x^{2}}{1 − abx − (2 + a^{2} + b^{2})x^{2} − abx^{3} + x^{4}} ,  (7)

which is equivalent to Shapiro’s result. Letting a = 1 and b = 1 in the above equation (7), we have [6, p. 251] (\underline{A007598})

∑_{n=0}^{∞} f_{n}^{2}x^{n} = \frac{1 − x}{1 − 2x − 2x^{2} + x^{3}} .

As noted by Shapiro [5], (7) can be written as an identity for Chebyshev polynomials. The Chebyshev polynomials of the second kind U_{n}(a) (n ≥ 0) (\underline{A093614}) can be defined by the generating function

\frac{1}{1 − 2az + z^{2}} = ∑_{n=0}^{∞} U_{n}(a)z^{n}.

By substituting −2ai for a and iz for x in the equation (1) we have the relation U_{n}(a) = i^{n}f_{n}(−2ai), and from the identity (2) we have

U_{n}(a) = \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ k=0 \end{matrix} \binom{n − k}{k}(−1)^{k}(2a)^{n−2k}.

By replacing a, b, and x with −2ai, −2bi, and −z respectively in the equation (7) we can obtain the Chebyshev polynomial identity

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

We now want to prove an identity which we will use later.

Lemma 2.1. For m ≥ −1 and n ≥ −1,

f_{m}(a)f_{n+1}(a) − f_{m+1}(a)f_{n}(a) = (−1)^{min(m,n+1)}f_{|m−n|−1}(a),  (8)

where f_{−1}(a) = 0.

Proof. Fix m > n > 0 and let A be the set of tilings of a 1 × m strip and a 1 × (n + 1) strip with 1 × 1 square bricks weighted by a and 1 × 2 rectangular bricks weighted by 1. Then there are f_{m}(a)f_{n+1}(a) weighted tilings in A. Similarly, let B be the set of tilings of a 1 × (m + 1) strip and a 1 × n strip with 1 × 1 square bricks weighted by a and 1 × 2 rectangular bricks weighted by 1. Then there are f_{m+1}(a)f_{n}(a) weighted tilings in B. Now we will find a bijection from a subset A to the set B if n is odd, a bijection from a subset of B to the set A if n is even that proves (8). Let’s consider a tiling in A drawn in two rows so that the top row is a 1 × m strip and the bottom row is a 1 × (n + 1) strip indented m − n spaces, as follows:

\begin{aligned}& & & ⋯ \\ ⟵ & m−n & ⟶ & & ⋯ \end{aligned}

Let’s find the rightmost vertical line segment, if there is one, that passes through both strips without cutting through the middle of some brick. We call the part of the tiling to the right of this line the tail of the tiling. In the following figure the tail is separated.

\begin{aligned}⋯ \\ & ⋯ \end{aligned}

Switching the two rows of the tail of this tiling produces the following tiling in B:

\begin{aligned}& & & ⋯ \\ ⟵ & m−n & ⟶ & & ⋯ \end{aligned}

where the top row is a 1 × (m + 1) strip and the bottom row is a 1 × n strip indented m − n spaces.

When n is odd, this tail switching pairs up every element of A with every element of B except for the tilings in A of the form:

\begin{aligned}& · · · · · · & & ⋯ \\ ⟵ & m−n & ⟶ & & ⋯ \end{aligned}

where the top row is a 1×m strip, the bottom row is a 1×(n+1) strip indented m−n spaces,

· · · · · · represents any strip of length m−n−1 tiled with 1×1 square bricks and 1×2 rectangular bricks, and every other brick is 1×2. In this case, tail switching cannot be applied to the tiling. So there are f_{m−n−1}(a) weighted tilings in the set A which cannot matched with those in the set B by tail switching. Therefore we have f_{m}(a)f_{n+1}(a) − f_{m+1}(a)f_{n}(a) = f_{m−n−1}(a).

When n is even, tail switching pairs up every element of A with every element of B except for the tilings in B of the form:

\begin{aligned}& · · · · · · & & ⋯ \\ ⟵ & m−n & ⟶ & & ⋯ \end{aligned}

where the top row is a 1×(m+1) strip, the bottom row is a 1×n strip indented m−n spaces,

· · · · · · represents any strip of length m−n−1 tiled with 1×1 square bricks and 1×2 rectangular bricks, and every other brick is 1×2. In this case, tail switching cannot be applied to the tiling. So there are f_{m−n−1}(a) weighted tilings in the set B which cannot matched with those in the set A by tail switching. Therefore we have f_{m}(a)f_{n+1}(a) − f_{m+1}(a)f_{n}(a) = −f_{m−n−1}(a).

In the case m > n = 0, the definition of the tail must be modified slightly. We leave the details to the reader. Now suppose n > m. Let D(m, n) = f_{m}(a)f_{n+1}(a) − f_{m+1}(a)f_{n}(a). Then D(m, n) = −D(n, m) = (−1)^{m}f_{n−m−1}(a). This is equivalent to the desired formula. In the other cases in which m or n is −1 or m = n, we can easily see that the equation (8) is true because f_{−1}(a) = 0.

A special case of the identity (8) for m = n + 1 and a = 1 is Cassini’s Fibonacci identity f_{n+1}^{2} − f_{n+2}f_{n} = (−1)^{n+1} which was proved in the same way in [1, p. 8] and [7].

Next, we can use this combinatorial method to obtain an explicit formula for Hadamard product (1 − ax − x^{2})^{−1} ∗ (1 − bx − x^{n})^{−1}.

Theorem 2.1. The Hadamard product

\frac{1}{1 − ax − x^{2}} ∗ \frac{1}{1 − bx − x^{n}}

is equal to

\frac{1 − f_{n−2}x^{n}}{1 − abx − b^{2}x^{2} − (f_{n} + f_{n−2})x^{n} − (2bf_{n−1} − abf_{n−2})x^{n+1} + (−1)^{n}x^{2n}}

where f_{n} represents f_{n}(a), f_{−1} = 0, and n ≥ 2.

Proof. We now consider the Hadamard product

\frac{1}{1 − ax − x^{2}} ∗ \frac{1}{1 − bx − x^{n}}  (9)

as counting tilings, using 1 × n rectangular bricks instead of 1 × 2 rectangular bricks in the bottom row. In this setting a prime block cannot have a 1 × 1 square brick in the bottom row anywhere except at the beginning or end. The possible prime blocks can be classified as follows:

The prime block of length 1:

The prime blocks of length n:

\begin{matrix}⨂ \\ ⨂ \\ ⨂ \\ ⨂ \\ ⨂ \end{matrix}

The prime blocks of length nk (k ≥ 2):

\begin{aligned}⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⋯ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ \\ & & & ⋯ \end{aligned}

The prime blocks of length nk + 1 (k ≥ 1):

\begin{aligned}⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⋯ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ \\ & & & ⋯ \end{aligned}

\begin{aligned}⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⋯ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ \\ & & & ⋯ \end{aligned}

The prime blocks of length nk + 2 (k ≥ 0):

\begin{aligned}⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⋯ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ \\ & & & ⋯ \end{aligned}

where\begin{matrix}⨂ \\ ⨂ \\ ⨂ \end{matrix},\begin{matrix}⨂ \\ ⨂ \\ ⨂ \\ ⨂ \end{matrix}, and\begin{matrix}⨂ \\ ⨂ \\ ⨂ \\ ⨂ \\ ⨂ \end{matrix}represent any strips of length n − 2, n − 1, and n respectively tiled with 1 × 1 square bricks and 1 × 2 rectangular bricks.

Thus the generating function P_{n}(x) for the weighted prime blocks of the Hadamard product (9) is

P_{n}(x) = abx + f_{n}(a)x^{n} + ∑_{k=1}^{∞} 2bf_{n−1}(a)f_{n−2}(a)^{k−1}x^{nk+1}

+ ∑_{k=0}^{∞} b^{2}f_{n−2}(a)^{k}x^{nk+2} + ∑_{k=2}^{∞} f_{n−1}(a)^{2}f_{n−2}(a)^{k−2}x^{nk}

= abx + f_{n}(a)x^{n} + \frac{2bf_{n−1}(a)x^{n+1}}{1 − f_{n−2}(a)x^{n}} + \frac{b^{2}x^{2}}{1 − f_{n−2}(a)x^{n}} + \frac{f_{n−1}(a)^{2}x^{2n}}{1 − f_{n−2}(a)x^{n}}

= \frac{abx + b^{2}x^{2} + f_{n}(a)x^{n} + (2bf_{n−1}(a) − abf_{n−2}(a))x^{n+1} + (−1)^{n−1}x^{2n}}{1 − f_{n−2}(a)x^{n}}

where we have used the identity f_{n−1}(a)^{2} −f_{n}(a)f_{n−2}(a) = (−1)^{n−1} obtained by substituting n−1 for m and n−2 for n in the identity (8) of Lemma 2.1. Since any tiling can be factored uniquely as a sequence of prime blocks, we obtain that (1 − ax − x^{2})^{−1} ∗ (1 − bx − x^{n})^{−1} = 1/(1 − P_{n}(x)). This is equivalent to the desired formula.

Note that Theorem 2.1 also holds for n = 1. The polynomials f_{n}(a)+f_{n−2}(a) in Theorem 2.1 are Lucas polynomials (\underline{A114525}).

Using (5) we can prove Han’s result

Ω_{≥} \frac{1}{(1 − zx − zx^{2})(1 − y/x − y/x^{2})} = \frac{1 + z^{2}y}{(1 − 2z)(1 − 3zy − z^{2}y − zy^{2})},  (10)

by computing the Hadamard product 1/(1 − zx − zx^{2}) ∗ 1/((1 − yx − yx^{2})(1 − x)) and then setting x = 1. Substituting z^{1/2} for a and z^{1/2}x for x in 1/(1 − ax − x^{2}) gives 1/(1 − zx − zx^{2}), and substituting (y + 1)/(−y)^{1/3} for b and (−y)^{1/3}x for x in 1/(1 − bx − x^{3}) gives 1/(1 − (y + 1)x + yx^{3}). Making these substitutions in Theorem 2.1 and using the fact that if f(x) ∗ g(x) = h(x) then f(αx) ∗ g(βx) = h(αβx), we have that the Hadamard product

\frac{1}{1 − zx − zx^{2}} ∗ \frac{1}{1 − (y + 1)x + yx^{3}}

is equal to

\frac{1 + z^{2}yx^{3}}{1 − (zy + z)x − z(y + 1)^{2}x^{2} + (3z^{2}y + z^{3}y)x^{3} + (z^{3}y + 2z^{2}y)(y + 1)x^{4} − z^{3}y^{2}x^{6}} .

Then setting x = 1 gives Han’s result (10), which he proved in a more complicated way.

We now modify the above setting to obtain a formula for the Hadamard product 1/(1 − ax − x^{2}) ∗ x^{m}/(1 − bx − x^{2}).

Theorem 2.2. The Hadamard product

\frac{1}{1 − ax − x^{2}} ∗ \frac{x^{m}}{1 − bx − x^{2}}

is equal to

\frac{f_{m}(a)x^{m} + bf_{m−1}(a)x^{m+1} − f_{m−2}(a)x^{m+2}}{1 − abx − (2 + a^{2} + b^{2})x^{2} − abx^{3} + x^{4}}

where f_{−1}(a) = 0, and f_{−2}(a) = 1.

Proof. When m = 0, the formula reduces to (7). When m ≥ 1, we consider the Hadamard product

\frac{1}{1 − ax − x^{2}} ∗ \frac{x^{m}}{1 − bx − x^{2}}

as counting tilings. We modify the tilings of a 2 × k rectangle so that the bottom row starts with a 1 × m rectangular brick to account for the factor x^{m} in x^{m}/(1 − bx − x^{2}). In this setting the first block where the bottom row starts with a 1 × m rectangular brick will be different from all the others, but the following blocks can be built up from a sequence of prime blocks which are exactly the same as the prime blocks in the Hadamard product (1 − ax − x^{2})^{−1} ∗ (1 − bx − x^{2})^{−1}. The first blocks can be classified as follows:

The first blocks of length m:

\begin{matrix}⨂ \\ ⨂ \\ ⨂ \\ ⨂ \\ ⨂ \end{matrix}

The first blocks of length m + 2k (k ≥ 1):

\begin{aligned}⨂ & ⨂ & ⨂ & ⨂ & ⋯ \\ & ⋯ \end{aligned}

The first blocks of length m + 2k + 1 (k ≥ 0):

\begin{aligned}⨂ & ⨂ & ⨂ & ⨂ & ⋯ \\ & ⋯ \end{aligned}

where \begin{matrix}⨂ \\ ⨂ \\ ⨂ \\ ⨂ \end{matrix} and \begin{matrix}⨂ \\ ⨂ \\ ⨂ \\ ⨂ \\ ⨂ \end{matrix} represent any strips of length m − 1 and m respectively tiled with 1 × 1 square bricks and 1 × 2 rectangular bricks. So the generating function Q_{m,2}(x) where m ≥ 2 for weighted first blocks is

Q_{m,2}(x) = f_{m}(a)x^{m} + ∑_{k=1}^{∞} af_{m−1}(a)x^{m+2k} + ∑_{k=0}^{∞} bf_{m−1}(a)x^{m+2k+1}

= f_{m}(a)x^{m} + \frac{af_{m−1}(a)x^{m+2}}{1 − x^{2}} + \frac{bf_{m−1}(a)x^{m+1}}{1 − x^{2}}

= \frac{f_{m}(a)x^{m} + bf_{m−1}(a)x^{m+1} − f_{m−2}(a)x^{m+2}}{1 − x^{2}} .

Since any tiling can be factored uniquely as a first block followed by a sequence of prime blocks, we have 1/(1 − ax − x^{2}) ∗ x^{m}/(1 − bx − x^{2}) = Q_{m,2}(x)/(1 − P_{2}(x)) where m ≥ 1. This is equivalent to the desired formula.

Now we can generalize the previous theorem by computing an explicit formula for the Hadamard product 1/(1 − ax − x^{2}) ∗ x^{m}/(1 − bx − x^{n}).

Theorem 2.3. The Hadamard product

\frac{1}{1 − ax − x^{2}} ∗ \frac{x^{m}}{1 − bx − x^{n}}

is equal to

\frac{f_{m}x^{m} + bf_{m−1}x^{m+1} + (−1)^{min(m−1,n−1)}f_{|m−n+1|−1}x^{m+n}}{1 − abx − b^{2}x^{2} − (f_{n} + f_{n−2})x^{n} − (2bf_{n−1} − abf_{n−2})x^{n+1} + (−1)^{n}x^{2n}}

where f_{n} represents f_{n}(a), f_{−1} = 0, m ≥ 0, and n ≥ 2.

Proof. When m = 0, Theorem 2.3 reduces to Theorem 2.1. Let’s consider the Hadamard product

\frac{1}{1 − ax − x^{2}} ∗ \frac{x^{m}}{1 − bx − x^{n}}

as counting pairs of tilings where m ≥ 1 and n ≥ 2. We slightly modify the above tiling by using 1 × n rectangular bricks instead of 1 × 2 rectangular bricks in the bottom row. In this setting, the first block where the bottom row starts with a 1 × m rectangular brick will be different from all the others, but the following blocks can be built up from a sequence of prime blocks whick are exactly the same as the prime blocks in the Hadamard product (1−ax−x^{2})^{−1} ∗(1−bx−x^{n})^{−1}. The possible first blocks can be classified as follows:

The first blocks of length m:

\begin{matrix}⨁ \\ ⨁ \\ ⨁ \\ ⨁ \\ ⨁ \\ ⨁ \end{matrix}

The first blocks of length m + nk (k ≥ 1):

\begin{aligned}⨁ & ⨁ & ⨁ & ⨁ & ⨁ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⋯ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ \\ & & & ⋯ \end{aligned}

The first blocks of length m + nk + 1 (k ≥ 0):

\begin{aligned}⨁ & ⨁ & ⨁ & ⨁ & ⨁ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⋯ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ \\ & & & ⋯ \end{aligned}

where \begin{matrix}⨂ \\ ⨂ \\ ⨂ \end{matrix}, \begin{matrix}⨂ \\ ⨂ \\ ⨂ \\ ⨂ \end{matrix}, \begin{matrix}⨁ \\ ⨁ \\ ⨁ \\ ⨁ \\ ⨁ \end{matrix}, \begin{matrix}⨁ \\ ⨁ \\ ⨁ \\ ⨁ \\ ⨁ \\ ⨁ \end{matrix} represent any strips of length n − 2, n − 1, m − 1 and m respectively tiled with 1 × 1 square bricks and 1 × 2 rectangular bricks.

So the generating function Q_{m,n}(x) where m ≥ 1 and n ≥ 2 for the weighted first blocks is

Q_{m,n}(x) = f_{m}(a)x^{m} + ∑_{k=1}^{∞} f_{m−1}(a)f_{n−1}(a)f_{n−2}(a)^{k−1}x^{m+nk}

+ ∑_{k=0}^{∞} bf_{m−1}(a)f_{n−2}(a)^{k}x^{m+nk+1}

= f_{m}(a)x^{m} + \frac{f_{m−1}(a)f_{n−1}(a)x^{m+n}}{1 − f_{n−2}(a)x^{n}} + \frac{bf_{m−1}(a)x^{m+1}}{1 − f_{n−2}(a)x^{n}}

= \frac{f_{m}(a)x^{m} + bf_{m−1}(a)x^{m+1} + (f_{m−1}(a)f_{n−1}(a) − f_{m}(a)f_{n−2}(a))x^{m+n}}{1 − f_{n−2}(a)x^{n}}

= \frac{f_{m}(a)x^{m} + bf_{m−1}(a)x^{m+1} + (−1)^{min(m−1,n−1)}f_{|m−n+1|−1}(a)x^{m+n}}{1 − f_{n−2}(a)x^{n}}

where we use the identity f_{m−1}(a)f_{n−1}(a) − f_{m}(a)f_{n−2}(a) = (−1)^{min(m−1,n−1)}f_{|m−n+1|−1}(a) obtained by substituting m − 1 for m and n − 2 for n in the identity (8) of Lemma 2.1. Since any tiling can be factored uniquely as a first block followed by a sequence of prime blocks, we have that 1/(1 − ax − x^{2}) ∗ x^{m}/(1 − bx − x^{n}) = Q_{m,n}(x)/(1 − P_{n}(x)) where m ≥ 1 and n ≥ 2. This is equivalent to the desired formula.

Note that Theorem 2.3 also holds for n = 1. In Theorem 2.3, there are some special cases: when b = 0, we have that

∑_{k≥0} f_{m+nk}(a)x^{m+nk} = \frac{f_{m}(a)x^{m} + (−1)^{min(m−1,n−1)}f_{|m−n+1|−1}(a)x^{m+n}}{1 − (f_{n}(a) + f_{n−2}(a))x^{n} + (−1)^{n}x^{2n}} .

In particular, when n = 1 and b = 0, we have that

∑_{k≥m} f_{k}(a)x^{k} = \frac{f_{m}(a)x^{m} + (−1)^{min(m−1,0)}f_{m−1}(a)x^{m+1}}{1 − ax − x^{2}} .

Using a similar method, we can also compute an explicit formula for the Hadamard product x^{m}/(1 − ax − x^{2}) ∗ 1/(1 − x^{n}).

Theorem 2.4. For positive integer m ≥ 1 and n ≥ 2, the Hadamard product

\frac{x^{m}}{1 − ax − x^{2}} ∗ \frac{1}{1 − x^{n}}

is equal to

\frac{f_{n−r}(a)x^{(q+1)n} + (−1)^{n−r−1}f_{|r−1|−1}(a)x^{(q+2)n}}{1 − (f_{n}(a) + f_{n−2}(a))x^{n} + (−1)^{n}x^{2n}}

if m = qn + r for some positive integers q and r with 0 < r < n, and is equal to

\frac{x^{m} − f_{n−2}(a)x^{m+n}}{1 − (f_{n}(a) + f_{n−2}(a))x^{n} + (−1)^{n}x^{2n}}

if m = qn for some positive integer q.

Proof. Let’s consider the Hadamard product

\frac{x^{m}}{1 − ax − x^{2}} ∗ \frac{1}{1 − x^{n}}

as counting pairs of tilings. We modify the tilings of a 2×k rectangle in the proof of Theorem 2.3 so that the top row starts with a 1 × m rectangular brick to account for the factor x^{m} in x^{m}/(1 − ax − x^{2}). In this setting the first block where the top row starts with a 1 × m rectangular brick will be different from all the others, but the following blocks can be built up from a sequence of prime blocks whick are exactly the same as the prime blocks in the Hadamard product 1/(1 − ax − x^{2}) ∗ 1/(1 − x^{n}). The possible first blocks can be classified as follows:

The first blocks of length (q + 1)n:

\begin{matrix}⨁ \\ ⨁ \\ ⨁ \end{matrix}

The first blocks of length (q + k)n (k ≥ 2):

\begin{aligned}⨁ & ⨁ & ⋯ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ & ⨂ \\ & ⋯ \end{aligned}

where \begin{matrix}⨁ \\ ⨁ \end{matrix}, \begin{matrix}⨁ \\ ⨁ \\ ⨁ \end{matrix}, \begin{matrix}⨂ \\ ⨂ \\ ⨂ \\ ⨂ \end{matrix}, \begin{matrix}⨂ \\ ⨂ \\ ⨂ \\ ⨂ \\ ⨂ \end{matrix} represent any strips of length n − r − 1, n − r, n − 2 and n − 1 respectively tiled with 1 × 1 square bricks and 1 × 2 rectangular bricks.

So the generating function R_{m,n}(x) where m = qn + r and 0 < r < n for the weighted first blocks is

R_{m,n}(x) = f_{n−r}(a)x^{(q+1)n} + ∑_{k=2}^{∞} f_{n−1−r}(a)f_{n−1}(a)f_{n−2}(a)^{k−2}x^{(q+k)n}

= f_{n−r}(a)x^{(q+1)n} + \frac{f_{n−1−r}(a)f_{n−1}(a)x^{(q+2)n}}{1 − f_{n−2}(a)x^{n}}

= \frac{f_{n−r}(a)x^{(q+1)n} + (f_{n−1}(a)f_{n−r−1}(a) − f_{n−2}(a)f_{n−r}(a))x^{(q+2)n}}{1 − f_{n−2}(a)x^{n}}

= \frac{f_{n−r}(a)x^{(q+1)n} + (−1)^{min(n−r−1)}f_{|r−1|−1}(a)x^{(q+2)n}}{1 − f_{n−2}(a)x^{n}}

where we use the identity f_{n−1}(a)f_{n−r−1}(a) − f_{n−2}(a)f_{n−r}(a) = (−1)^{min(n−r−1,n−1)}f_{|r−1|−1}(a) obtained by substituting n − 2 for m and n − r − 1 for n in the identity (8) of Lemma 2.1. Since any tiling can be factored uniquely as a first block followed by a sequence of prime blocks, we have that x^{m}/(1 − ax − x^{2}) ∗ 1/(1 − x^{n}) = R_{m,n}(x)/(1 − P_{n}(x)) where b = 0. This is equivalent to the desired formula.

When m = qn, we have only one first block of length m:

So the generating function R_{m,n}(x) for the weighted first blocks is R_{m,n}(x) = x^{m}. Therefore we have that x^{m}/(1 − ax − x^{2}) ∗ 1/(1 − x^{n}) = x^{m}/(1 − P_{n}(x)) where b = 0. This is equivalent to the desired formula

Note that Theorem 2.4 also holds for n = 1.

References

[1] A. T. Benjamin and J. J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, Mathematical Association of America, Washington, DC, 2003.

[2] D. Foata and G.-N. Han, Nombres de Fibonacci et polynômes orthogonaux, in M. Morelli and M. Tangheroni, eds., Leonardo Fibonacci: Il Tempo, Le Opere, L’Eredità Scientifica, Pacini, Rome, 1994, pp. 179–208.

[3] G.-N. Han, A general algorithm for the MacMahon omega operator, Ann. Combin. 7 (2003) 467–480.

[4] I. M. Gessel and R. P. Stanley, Algebraic enumeration, in R. L. Graham, M. Grötschel, and L. Lovász, eds., Handbook of Combinatorics, Vol. 2, Elsevier and MIT Press, 1995, pp. 1021–1062.

[5] L. Shapiro, A combinatorial proof of a Chebyshev polynomial identity, Discrete Math. 34 (1981) 203–206.

[6] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 2002.

[7] M. Werman and D. Zeilberger, A bijective proof of Cassini’s Fibonacci identity, Discrete Math. 58 (1986) 109.

2000 Mathematics Subject Classification: Primary 05A15; Secondary 05A18. Keywords: Hadamard product, Fibonacci polynomial.

(Concerned with sequences \underline{A000045}, \underline{A007598}, \underline{A011973}, \underline{A093614}, and \underline{A114525}.)

Received March 3 2009; revised version received October 20 2009. Published in Journal of Integer Sequences, October 21 2009.

Return to Journal of Integer Sequences home page.