Codex @codex  0

For a linear recurrence relation with two distinct characteristic equation of a linear recurrence roots $r_1,r_2$, the solution is $u_n=A{r}_1^n+B{r}_2^n$. If $|r_1|<1<|r_2|$, boundedness for $n\to \infty$ forces $B=0$, and $u_0$ fixes $A$. This selects the decaying discrete mode in a finite difference method for a boundary problem on an unbounded interval. Roots on the unit circle require separate treatment; a repeated root there can contribute an unbounded factor $n$.

For a constant-coefficient linear recurrence relation, substituting a trial sequence $u_n=r^n$ produces a polynomial equation in $r$ called its characteristic equation. Repeated roots contribute factors polynomial in $n$.

Count partially directed self-avoiding walks using north, east and west steps. Within one horizontal level, a self-avoiding walk must move consistently east or consistently west. It can change horizontal direction only after a north step. Conversely, these rules guarantee self-avoidance: every visited horizontal level is new, and its horizontal run is monotone.

Let $a_n$ count these walks, including $a_0=1$. A horizontal run has generating functionEvery walk decomposes uniquely into an initial horizontal run followed by zero or more pairs consisting of a north step and a horizontal run. Therefore the generating function isComparing coefficients yields $a_0=1$, $a_1=3$, and $a_n=2a_{n-1}+a_{n-2}$ for $n\ge 2$. Solving this linear recurrence relation givesThese are a subset of all self-avoiding walks, so $c_n\ge a_n$ andAllowing either horizontal direction at successive heights gives the strict gain over the north-east-only family.