The weighted sets \(A\) and \(B\) are isomorphic; thus, there exists an isomorphism \(\rho :A\rightarrow B\). Consider this \(\rho \). Then, \(\rho \) is a bijection and preserves the weight (since \(\rho \) is an isomorphism of weighted sets). The latter property says that we have

Now, the definition of \(\overline{B}\) yields

Comparing this with

we obtain \(\overline{A}=\overline{B}\).

The formal definition of \(A+B\) says that \(A+B=\left( \left\{ 0\right\} \times A\right) \cup \left( \left\{ 1\right\} \times B\right) \). Thus, the set \(A+B\) is the union of the two disjoint sets \(\left\{ 0\right\} \times A\) and \(\left\{ 1\right\} \times B\) (indeed, these two sets are clearly disjoint, since \(0\neq 1\)).

Let us first check that \(A+B\) is finite-type.

For each \(n\in \mathbb {N}\), there are only finitely many \(a\in A\) having weight \(\left\vert a\right\vert =n\) (since \(A\) is finite-type), and there are only finitely many \(b\in B\) having weight \(\left\vert b\right\vert =n\) (since \(B\) is finite-type). Hence, there are only finitely many \(c\in A+B\) having weight \(\left\vert c\right\vert =n\) (because any such \(c\) either has the form \(\left( 0,a\right) \) for some \(a\in A\) having weight \(\left\vert a\right\vert =n\), or has the form \(\left( 1,b\right) \) for some \(b\in B\) having weight \(\left\vert b\right\vert =n\)). In other words, the weighted set \(A+B\) is finite-type.

Let us now check that \(\overline{A+B}=\overline{A}+\overline{B}\). Indeed, the definition of \(\overline{A+B}\) yields

The proof that \(A\times B\) is finite-type is easy: Let \(n\in \mathbb {N}\). We must prove that there are only finitely many pairs \(\left( a,b\right) \in A\times B\) having weight \(\left\vert \left( a,b\right) \right\vert =n\). Since \(\left\vert \left( a,b\right) \right\vert =\left\vert a\right\vert +\left\vert b\right\vert \), these pairs have the property that \(a\in A\) has weight \(k\) for some \(k\in \left\{ 0,1,\ldots ,n\right\} \), and that \(b\in B\) has weight \(n-k\) for the same \(k\). This leaves only finitely many options for \(k\), only finitely many options for \(a\) (since \(A\) is finite-type and thus has only finitely many elements of weight \(k\)), and only finitely many options for \(b\) (since \(B\) is finite-type and thus has only finitely many elements of \(n-k\)). Altogether, we thus obtain only finitely many options for \(\left( a,b\right) \).

Now, the definition of \(\overline{A\times B}\) yields

By induction on \(k\). The base case \(k = 0\) is straightforward: \(A^0\) consists of a single element (the empty tuple) with weight \(0\), so \(\overline{A^0} = 1 = \overline{A}^0\).

For the inductive step, we observe that \(A^{k+1} \cong A \times A^k\) as weighted sets (via the isomorphism that splits a \((k{+}1)\)-tuple into its last entry and the remaining \(k\)-tuple). By Proposition 1.403, their generating functions are equal. By Proposition 1.407, \(\overline{A \times A^k} = \overline{A} \cdot \overline{A^k}\). By the induction hypothesis, \(\overline{A^k} = \overline{A}^k\). Hence \(\overline{A^{k+1}} = \overline{A} \cdot \overline{A}^k = \overline{A}^{k+1}\).

The isomorphism sends a \((n{+}1)\)-tuple \((a_0, a_1, \ldots , a_n)\) to the pair \((a_n, (a_0, \ldots , a_{n-1}))\). It preserves weight because the sum of entries is unchanged.

If every element has weight \(\geq 1\), then a tuple of length \(n\) has total weight \(\geq n\). Therefore, for any fixed weight \(m\), we only need to consider tuples of length \(\leq m\). For each such length, there are only finitely many tuples of weight \(m\) (since \(A^k\) is finite-type by Proposition 1.409). Hence the disjoint union is finite-type.

The decomposition is defined by cutting the tiling along its faults. Given a tiling \(T\) of \(R_{n,2}\):

• If \(n = 0\) (empty tiling), the decomposition is the empty \(0\)-tuple.

• If \(T\) has no faults, the decomposition is the \(1\)-tuple \((T)\).

• If \(T\) has faults, let \(k\) be the smallest fault position. Cut \(T\) at position \(k\) to obtain a faultfree left part (a tiling of \(R_{k,2}\)) and a right part (a tiling of \(R_{n-k,2}\)). Recursively decompose the right part, and prepend the left part.

The composition (inverse map) concatenates a tuple of faultfree tilings horizontally by shifting each component to the appropriate position. The weight-preservation property follows because the total width of the concatenated rectangle equals the sum of the widths of the components.

The proof that these two maps are inverse to each other requires showing:

1. Composing and then decomposing recovers the original tuple (by showing that faults in the composed tiling occur exactly at the partial width sums).

2. Decomposing and then composing recovers the original tiling (by showing that cutting at faults and reassembling gives back the original domino set).

For horizontal dominos, the fault condition directly gives that both cells lie on the same side. For vertical dominos, both cells share the same \(x\)-coordinate, so they are trivially on one side.

Pairwise disjointness is inherited from \(T\). For coverage: every cell \((x,y)\) with \(1 \le x \le k\) is covered by some domino \(d \in T\), and by Lemma 1.414, \(d\) lies entirely in the left part.

Each right-part domino is shifted by \(-k\) in the \(x\)-coordinate. Disjointness is preserved since shifting is injective. Coverage follows because every cell \((x,y)\) with \(k+1 \le x \le n\) is covered by a right-part domino.

A fault at \(j {\lt} k\) in the left restriction would induce a fault at \(j\) in the original tiling \(T\) (since all horizontal dominos in the left part are also in \(T\)). But \(k\) is the minimum fault, so no fault at \(j {\lt} k\) exists in \(T\).

Dominos from different components have disjoint \(x\)-coordinate ranges (Lemma 1.419), so they are pairwise disjoint. Coverage follows because each point in the total rectangle lies in some component’s range and is covered by that component’s shifted dominos.

For \(i_1 {\lt} i_2\), the partial width sum satisfies \(\sum _{j {\lt} i_1} m_j + m_{i_1} \le \sum _{j {\lt} i_2} m_j\), so the \(x\)-coordinate ranges \([1 + \text{offset}_{i_1}, m_{i_1} + \text{offset}_{i_1}]\) and \([1 + \text{offset}_{i_2}, m_{i_2} + \text{offset}_{i_2}]\) do not overlap.

Well-founded recursion on \(n\): at each fault \(k\), the right part has width \(n - k {\lt} n\).

By strong induction on \(n\). The key step shows that the set of dominos of \(T\) equals the union of the left restriction’s dominos and the shifted right restriction’s dominos (Lemma 1.422), and by the induction hypothesis the right part reconstructs correctly.

Every domino is in the left or right part. Left-part dominos are unchanged. Right-part dominos are shifted by \(-k\) and then back by \(+k\), recovering the original.

By strong induction on \(k\). For \(k = 0\) and \(k = 1\) the result is immediate. For \(k \ge 2\): the composed tiling has a fault at position \(m_1 = |t_1|\) (Lemma 1.424); no earlier fault exists (Lemma 1.425); the minimum fault is \(m_1\) (Lemma 1.426); the left restriction equals \(t_1\) (Lemma 1.427); and the right restriction equals the composition of the tail \((t_2, \ldots , t_k)\) (Lemma 1.428). The induction hypothesis on the tail completes the proof.

The width \(m_1 {\gt} 0\) (since faultfree tilings are nonempty) and \(m_1 {\lt} m_1 + m_2 + \cdots \) (since \(k \ge 2\) and \(m_2 {\gt} 0\)). Each horizontal domino from component \(0\) has both \(x\)-coordinates \(\le m_1\); each horizontal domino from component \(i \ge 1\) has both \(x\)-coordinates \(\ge m_1 + 1\).

Every domino from component \(0\) that is also in the composed tiling at position \(p\) witnesses the same crossing in the first component. But the first component is faultfree, so no such fault exists.

There is a fault at \(m_1\) (Lemma 1.424) and no fault at any \(p {\lt} m_1\) (Lemma 1.425).

Dominos in the left part at position \(m_1\) come exactly from component \(0\) (since components \(i \ge 1\) have \(x \ge m_1 + 1\)), and the partial width sum for component \(0\) is \(0\), so no shifting occurs.

The dominos in the right part come from components \(i \ge 1\). After unshifting by \(m_1\), each component \(i\)’s partial width sum decreases by \(m_1\), matching the partial width sums of the tail composition.

Follows from \(\mathrm{compose}(\mathrm{decompose}(T)) = T\) (Lemma 1.421) and the fact that \(\mathrm{compose}\) produces a tiling whose width is the sum of the component widths.

Consider any faultfree tiling of a height-\(2\) rectangle \(R_{n,2}\) with \(n \geq 3\). Look at the domino that covers the cell \((1,1)\). If it is a vertical domino \(\{ (1,1),(1,2)\} \), then this vertical domino constitutes the entire first column, so there is a fault at position \(1\) – contradiction. If it is a horizontal domino \(\{ (1,1),(2,1)\} \), then there must be a horizontal domino \(\{ (1,2),(2,2)\} \) stacked above it, and these two dominos cover the first two columns entirely, so there is a fault at position \(2\) – contradiction.

By the classification lemma, there is exactly one faultfree tiling of width \(1\) (the single vertical domino) and exactly one faultfree tiling of width \(2\) (the two horizontal dominos), and no faultfree tilings of any other width. Hence \(\overline{F} = x + x^2\).

We construct a bijection \(\mathrm{Tiling}(R_{n+2,2}) \simeq \mathrm{Tiling}(R_{n,2}) \sqcup \mathrm{Tiling}(R_{n+1,2})\) by classifying tilings according to what covers the cell \((1,1)\):

• If a vertical domino \(\{ (1,1),(1,2)\} \) covers \((1,1)\), then removing it and shifting gives a tiling of \(R_{n+1,2}\).

• If a horizontal domino \(\{ (1,1),(2,1)\} \) covers \((1,1)\), then \(\{ (1,2),(2,2)\} \) must also be present; removing both and shifting gives a tiling of \(R_{n,2}\).

The inverse maps are given by prepending a vertical domino (resp. a pair of horizontal dominos) and shifting the remaining dominos.

The cell \((1,1) \in R_{n,2}\) is covered by the tiling. By the coverage condition, some domino in \(T\) contains \((1,1)\).

A horizontal domino covering \((1,1)\) must be \(\{ (1,1),(2,1)\} \) since extending left to \((0,1)\) would leave the rectangle. A vertical domino covering \((1,1)\) must be \(\{ (1,1),(1,2)\} \) since extending down to \((1,0)\) would leave the rectangle.

The cell \((1,2)\) must be covered. The vertical domino \(\{ (1,1),(1,2)\} \) would overlap with \(\{ (1,1),(2,1)\} \). So \((1,2)\) must be covered by a horizontal domino \(\{ (1,2),(2,2)\} \).

The vertical domino covers both cells of column \(1\). Any other domino covering a cell in column \(1\) would overlap with the vertical domino. Hence all other dominos have \(x\)-coordinates \(\ge 2\), giving a fault at \(1\).

By Lemma 1.435, \(\{ (1,2),(2,2)\} \) is also present. These two dominos cover all four cells of columns \(1\)–\(2\). Any other domino must avoid all these cells, forcing all \(x\)-coordinates \(\ge 3\).

Disjointness holds because the vertical domino covers column \(1\) and the shifted dominos have \(x \ge 2\). Coverage: column \(1\) is covered by the vertical domino; columns \(2\) through \(m+1\) are covered by the shifted dominos.

Disjointness holds because the two horizontal dominos cover columns \(1\)–\(2\) (and are disjoint from each other since they cover different rows) and the shifted dominos have \(x \ge 3\). Coverage is verified similarly to Lemma 1.438.

A tiling is determined by its set of dominos, which is a subset of the (finite) set of all dominos that fit inside \(R_{n,m}\).

By strong induction on \(n\). Base cases: \(d_{0,2} = 1 = f_1\) and \(d_{1,2} = 1 = f_2\). Inductive step: \(d_{n+2,2} = d_{n,2} + d_{n+1,2}\) (Lemma 1.432) \(= f_{n+1} + f_{n+2}\) (induction hypothesis) \(= f_{n+3}\) (Fibonacci recurrence).

The elements of weight \(n\) in \(D\) are exactly the tilings of \(R_{n,2}\).

The \(n\)-th coefficient is the number of elements of weight \(n\) in \(D\), which is \(d_{n,2} = f_{n+1}\).