Examples: Linear Recurrences and Rational Generating Functions

If $F(x)={\sum }_{n\ge 0}{F}_n{x}^n$, coefficient extraction using [L1] gives $(1-x-x^2)F(x)=x$; [L2] therefore gives the displayed rational generating function.

The polynomial $t^2-t-1$ factors as $(t-\varphi )(t-\widehat{\varphi })$ in $\mathbb{Q}(\sqrt{5})[t]$, in agreement with [L4].

By [L3], $F_n=A{\varphi }^n+B{\widehat{\varphi }}^n$. The equations $A+B=F_0=0$ and $A\varphi +B\widehat{\varphi }=F_1=1$ give $A=1\mathrm{/}\sqrt{5}$ and $B=-1\mathrm{/}\sqrt{5}$.

Substitution in step 2.1 proves Binet's formula, including $n=0$ and $n=1$.

For $L(x)={\sum }_{n\ge 0}{L}_n{x}^n$, [L1] gives $(1-x-x^2)L(x)=L_0+(L_1-L_0)x=2-x$, so [L2] proves the generating-function formula.

Since $t^2-t-1=(t-\varphi )(t-\widehat{\varphi })$, [L3] gives $L_n=A{\varphi }^n+B{\widehat{\varphi }}^n$.

The initial equations $A+B=2$ and $A\varphi +B\widehat{\varphi }=1$ have the solution $A=B=1$, because $\varphi +\widehat{\varphi }=1$.

Substitution in step 2.1 proves the displayed closed form for all $n\ge 0$.

Apply [L1] with $j=2$ and $\lambda =2$; since $\left(\genfrac{}{}{0px}{}{n+1}{1}\right)=n+1$, this gives the displayed series.

Direct substitution gives $a_{n+2}-4a_{n+1}+4a_n=2^n(4n+12-8n-16+4n+4)=0$.

By [L3], the recurrence polynomial is $t^2-4t+4=(t-2{)}^2$, and [L2] matches it to the given double pole.

By [L1] the recurrence is $F_{n+2}-F_{n+1}-F_n=0$, so $d=2$ and $c_1=c_2=-1$. Unfolding [L4] gives $C_{0,1}=1$, $C_{1,0}=-c_2=1$ and $C_{1,1}=-c_1=1$, with $C_{0,0}=0$, which is the displayed matrix $C$; [L2] then gives its state-vector identity.

At $n=1$, the proposed power formula reads $C=\left(\begin{array}{cc}{F}_0& F_1\\ F_1& F_2\end{array}\right)$, which follows from [L1].

Multiplying the proposed matrix for $C^n$ on the right by $C$ replaces each row $(F_{k-1},F_k)$ by $(F_k,F_{k-1}+F_k)=(F_k,F_{k+1})$ using [L1], so it gives the proposed matrix for $C^{n+1}$.

By [L3], ${\chi }_C(t)=t^2-t-1$.

Steps 1.2 and 1.3 prove the power identity for every $n\ge 1$.

There is one empty tiling and one one-cell tiling, so $T_0=T_1=1$. For $n\ge 2$, the last tile is uniquely a monomer after a tiling of length $n-1$ or a domino after one of length $n-2$, so $T_n=T_{n-1}+T_{n-2}$.

In the two-state encoding, $1\to 1$ places a monomer, $1\to 0$ starts a domino, and $0\to 1$ completes it. Thus board tilings are in bijection with length-$n$ walks from state $1$ back to state $1$, and [L2] gives $T_n=(C^n{)}_{11}$.

Comparing the initial values and recurrence in step 1.1 with [L1] gives $T_n=F_{n+1}$ for every $n\ge 0$.

Since $I-xC=\left(\begin{array}{cc}1& -x\\ -x& 1-x\end{array}\right)$ has determinant $1-x-x^2$ and the relevant cofactor is $1$, [L3] gives the displayed generating function.

The transitions $1\to 1$, $1\to 0$, and $0\to 1$ respectively place a monomer, start a domino, and finish that domino. Closing the state walk matches the boundary conditions at the marked seam, giving the asserted cyclic-tiling encoding and the stated counts for $n=0,1,2$.

The matrix $C$ is invertible, has characteristic polynomial $t^2-t-1$, and has $\mathrm{tr}(C^0)=2$ and $\mathrm{tr}(C)=1$. Thus [L3] and [L1] give $\mathrm{tr}(C^n)=L_n$ for every $n\ge 0$.

By [L2], the cyclic-tiling series is the trace series. Directly, $\mathrm{adj}(I-xC)$ has trace $2-x$ and $\det (I-xC)=1-x-x^2$, so the trace formula in [L2] gives the displayed quotient.

By [L1], $A=J-I$. The all-ones vector $\mathbf{1}$ satisfies $A\mathbf{1}=(p-1)\mathbf{1}$, while $A(e_i-e_0)=-(e_i-e_0)$ for $1\le i<p$.

The list $\mathbf{1},e_1-e_0,\dots ,e_{p-1}-e_0$ is linearly independent over $\mathbb{Q}$: a relation has coordinates $\alpha +{\beta }_i=0$ for $i\ge 1$ and $\alpha -{\sum }_i{\beta }_i=0$, hence $p\alpha =0$. Since $p\mathrm{\ne }0$ in $\mathbb{Q}$, every coefficient is zero. It is therefore a basis of ${\mathbb{Q}}^p$.

In the basis of step 1.2, $A$ is diagonal with entries $p-1,-1,\dots ,-1$, so ${\chi }_A(t)=(t-(p-1))(t+1{)}^{p-1}$ in $\mathbb{Q}[t]$.

Apply [L3] to step 2.1 and then [L2] to obtain the displayed closed-walk count. When $p=1$, the difference-vector list is empty and the formula gives $0$ because $n\ge 1$.

By [L2], state $\epsilon$ has transitions labelled $0$ to $\epsilon$ and $1$ to $1$, while state $1$ has only the transition labelled $0$ to $\epsilon$. This gives the displayed matrix.

Every avoiding word labels one walk from $\epsilon$ to either state. Since $I-xA=\left(\begin{array}{cc}1-x& -x\\ -x& 1\end{array}\right)$, summing the first-row entries of its inverse via [L3] gives $(1+x)\mathrm{/}(1-x-x^2)$.

Its coefficients begin $a_0=1,a_1=2$ and satisfy $a_{n+2}=a_{n+1}+a_n$, so comparison with [L1] gives $a_n=F_{n+2}$.

By [L1], the states are $\epsilon ,1,10$ and, in that order, their transfer matrix is $A=\left(\begin{array}{ccc}1& 1& 0\\ 0& 1& 1\\ 1& 0& 0\end{array}\right)$. The missing transition from $10$ on $1$ is precisely the rejected factor $101$.

Avoiding words are walks from $\epsilon$ to any state. Summing the three corresponding entries supplied by [L2], or solving $(I-xA)y=\mathbf{1}$, gives $(1+x^2)\mathrm{/}(1-2x+x^2-x^3)$.

Direct enumeration by length gives $1,2,4,7,12,21,37$ through length six. These values also satisfy $a_n=2a_{n-1}-a_{n-2}+a_{n-3}$ for $3\le n\le 6$, as the denominator in step 2.1 requires.

Let $N_n,E_n,W_n$ count valid nonempty words by their last letter. Appending $N$ is always allowed, whereas $E$ may not follow $W$ and $W$ may not follow $E$; this gives the displayed matrix and $N_n=a_{n-1}$ for $n\ge 1$.

For $n\ge 2$, the state equations give $E_n+W_n=2N_{n-1}+E_{n-1}+W_{n-1}=a_{n-1}+a_{n-2}$. Together with $N_n=a_{n-1}$ this yields $a_n=2a_{n-1}+a_{n-2}$.

The empty word and the three one-letter words give $a_0=1,a_1=3$. Multiplying the coefficient series by $1-2x-x^2$ and using step 2.1 leaves $1+x$, so [L1] gives the displayed generating function.

As a consistency check, [L2] applied to the displayed matrix makes $1+x{\mathbf{1}}^{\mathsf{T}}(I-xA{)}^{-1}\mathbf{1}$ equal to the same quotient; the leading $1$ counts the empty word.

Multiplying $A(x)={\sum }_{n\ge 0}{a}_n{x}^n$ by $1+x^2$ and using the recurrence leaves $x$, so [L1] gives $A(x)=x\mathrm{/}(1+x^2)$ over $\mathbb{Q}$.

The characteristic polynomial $t^2+1$ has no root in $\mathbb{Q}$, but in $\mathbb{Q}(i)$ it factors as $(t-i)(t+i)$. Thus a pure-exponential expression using its characteristic roots cannot be written with bases in $\mathbb{Q}$.

Applying [L2] in the splitting field and matching $a_0=0,a_1=1$ gives $a_n=(i^n-(-i{)}^n)\mathrm{/}(2i)$. Its first four values are $0,1,0,-1$, which satisfy the given recurrence.

This rational recurrence over $\mathbb{Q}$ therefore requires the proper splitting field $\mathbb{Q}(i)$ for its characteristic-root exponential form, refuting the claim.

With initial pair $(a_0,a_1)=(0,0)$, the recurrence gives the zero sequence. With initial pair $(b_0,b_1)=(0,1)$, it gives $0,1,1,2,3,\dots$.

The two sequences obey exactly the same recurrence coefficients but differ at index one. This is consistent with [L1], which requires the two initial values in addition to the coefficients, and it refutes the claim.

Direct calculation gives $a_{n+2}-2a_{n+1}+a_n=0$, so the characteristic polynomial is $(t-1{)}^2$, which splits over $\mathbb{Q}$.

A linear combination of pure exponentials supplied only by the characteristic root $1$ is constant, whereas $a_n=n$ is not. Thus no such pure-exponential expression exists.

The required degree-one factor is exactly the repeated-root term permitted by [L1]; equivalently, [L2] with $\lambda =1$ gives coefficients $n+1$, whose one-step shift yields $n$.

Suppose $F$ were rational. By [L1] its coefficient sequence would satisfy an eventual constant-coefficient recurrence. That recurrence cannot have order zero, since an eventual order-zero recurrence makes the sequence eventually zero while $n!\mathrm{\ne }0$ in $\mathbb{Q}$ for every $n$. So there would be $d\ge 1$, coefficients $c_1,\dots ,c_d\in \mathbb{Q}$ with $c_d\mathrm{\ne }0$, and an index $N$ such that $(n+d)!+c_1(n+d-1)!+\cdots +c_{d}n!=0$ for every $n\ge N$.

Divide the relation by the nonzero integer $n!$. It says that the polynomial $P(z)=(z+1)\cdots (z+d)+c_1(z+1)\cdots (z+d-1)+\cdots +c_{d-1}(z+1)+c_d$ vanishes at every integer $z=n\ge N$.

The polynomial $P$ has degree $d$ and leading coefficient $1$, so it is nonzero. But step 2.1 gives it more than $d$ distinct rational roots, contradicting [L2].

Therefore the coefficient sequence is not eventually recurrent and [L1] shows that $F(x)$ is not rational. This argument is entirely formal and uses no convergence claim.

Multiplying $(I-xA)$ by ${\sum }_{n\ge 0}{A}^n{x}^n$, the constant coefficient is $I$ and each positive coefficient is $A^n-A{A}^{n-1}=0$; the same calculation works on the other side. This is the identity in [L1].

Every coefficient uses only finitely many ring operations, and the constant matrix coefficient of $I-xA$ is the invertible matrix $I$. No topology, norm, absolute value, or limiting operation occurs.

In the transfer-matrix setting itself — a finite weighted digraph over $R$ with $p\ge 1$ vertices and transfer matrix $A$ — [L2] reads the walk generating functions off this same formal inverse, again with no analytic hypothesis. So the transfer-matrix identity remains valid over every commutative coefficient ring regardless of spectral radius. This refutes the claim.