# Fibonacci-Motzkin paths and J-type continued fractions

Recall that a Motzkin path is a piece-wise linear planar path connecting points in the integer lattice quadrant $$\Bbb{Z}_{\geq 0} \times \Bbb{Z}_{\geq 0}$$ beginning at the origin $$(0,0)$$ and ending at $$(n,0)$$ for some $$n \in \Bbb{Z}_{>0}$$ whose steps are either

$$$$\begin{array}{ll} \nearrow & = (1,1) \\ \searrow & = (1,-1) \\ \rightarrow & = (1,0) \end{array}$$$$

Alternatively we may view a Motzkin path as an $$n$$-tuple $$\underline{\pi} = \big(\pi_1, \dots, \pi_n \big)$$ where $$\pi_i \in \{ \nearrow \, , \searrow \, , \rightarrow \}$$ for each $$1 \leq i \leq n$$ and where $$\pi_1 + \cdots + \pi_n = (n,0)$$. The set of Motzkin paths $$\underline{\pi}$$ terminating at $$(n,0)$$ will be denoted $$\mathcal{M}_n$$. Among the Motzkin paths $$\mathcal{M}_n$$ is the subset of what I'll call Fibonacci-Motzkin paths: These are paths that weakly increase until a threshold is reached, after which they strictly decrease. More specifically $$\underline{\pi} = (\pi_1, \dots, \pi_n) \in \mathcal{M}_n$$ is a Fibonacci-Motzkin path if there exists a threshold $$0 \leq k \leq \lfloor {1 \over 2} n \rfloor$$ such that $$\pi_i \in \{ \nearrow, \, \rightarrow \}$$ for all $$1 \leq i \leq n - k$$ and $$\pi_i = \searrow$$ for all $$n-k < i \leq n$$. The threshold $$k$$ equals the number of $$\nearrow$$ steps taken in the initial ascent of the path. A moment's reflection should convince the reader that the cardinality of the set $$\mathcal{F}_n$$ of all Fibonacci-Motzkin paths is indeed the $$n$$-th Fibonacci number, thus justifying the choice of terminology.

Received wisdom tells us to introduce two infinite families of generic parameters $$\beta_1, \beta_2, \beta_3, \dots$$ and $$\gamma_0, \gamma_1, \gamma_2, \dots$$ and then assign a weight

$$$$\mathrm{w}(\underline{\pi}) \, := \ \beta_1 \cdots \beta_k \cdot \gamma_0^{m_0} \cdots \gamma_k^{m_k}$$$$

to a Motzkin path $$\underline{\pi} \in \mathcal{M}_n$$ where

$$$$\begin{array}{ll} k &\text{= number of \nearrow steps taken by \underline{\pi}} \\ m_\ell &\text{= number of \rightarrow steps taken by \underline{\pi} at height \ell} \end{array}$$$$

The corresponding generating function of all Motzkin paths, given by

$$$$M(z) := \ 1 \ + \ \sum_{n \, \geq \, 1} z^n \sum_{\underline{\pi} \, \in \, \mathcal{M}_n} \, \mathrm{w}(\underline{\pi})$$$$

is then seen to coincide with the formal expansion of the $$J$$-type continued fraction

$$$$\ {1 \over {1 - z \gamma_0 \ - \ {\displaystyle z^2 \beta_1 \over {\displaystyle 1 - z \gamma_1 \ - \ {z^2 \beta_2 \over {\displaystyle 1 - z \gamma_2 \ - \ {z^2 \beta_3 \over {\ddots}}}}}}}}$$$$

Let us introduce a Fibonacci analogue of the generating function $$M(z)$$ namely

$$$$F(z) := \ 1 \ + \ \sum_{n \, \geq \, 1} z^n \sum_{\underline{\pi} \, \in \, \mathcal{F}_n} \, \mathrm{w}(\underline{\pi})$$$$

Question: Is there some kind of continued fraction whose expansion is $$F(z)$$?

thanks, ines.

Grouping the terms of $$F(z)$$ by the height reached, we get $$F(z) = \frac{1}{(1 - z\gamma_0)} + \frac{z^2 \beta_1}{(1 - z\gamma_0) (1 - z\gamma_1)} + \frac{z^4 \beta_1 \beta_2}{(1 - z\gamma_0) (1 - z\gamma_1) (1 - z\gamma_2)} + \cdots \\$$ This has the form of Euler's continued fraction $$a_0 + a_0a_1 + a_0a_1a_2 + \cdots = \cfrac{a_0}{1 - \cfrac{a_1}{1 + a_1 - \cfrac{a_2}{1 + a_2 - \ddots}}}$$ with $$a_0 = \frac{1}{1 - z\gamma_0} \\ a_1 = \frac{z^2 \beta_1}{1 - z \gamma_1} \\ a_2 = \frac{z^2 \beta_2}{1 - z \gamma_2} \\ \vdots$$ It is perhaps more natural to drop the denominators to the next level: i.e. instead of $$\cfrac{\frac{1}{1 - z\gamma_0}}{1 - \cfrac{\frac{z^2 \beta_1}{(1 - z \gamma_1)}}{1 + \frac{z^2 \beta_1}{(1 - z \gamma_1)} - \cfrac{\frac{z^2 \beta_2}{(1 - z \gamma_2)}}{1 + \frac{z^2 \beta_2}{(1 - z \gamma_2)} - \ddots}}}$$ we could write $$\cfrac{1}{(1 - z\gamma_0) - \cfrac{(1 - z\gamma_0) z^2 \beta_1}{(1 - z \gamma_1) + z^2 \beta_1 - \cfrac{(1 - z \gamma_1) z^2 \beta_2}{(1 - z \gamma_2) + z^2 \beta_2 - \ddots}}}$$
• Why do you have a square $(1 -z\gamma_0)^2$ in the denominator for the $\beta_1$-terms? It seems to me that the height one terms contribute $z^2 \beta_1 \sum_{n \geq 0} {\gamma_0^{n+1} -\gamma_1^{n+1} \over {\gamma_0 - \gamma_1}} z^n = {z^2\beta_1 \over {(1-z\gamma_0)(1-z\gamma_1) } }$. May 4 at 23:23
• In fact, shouldn't all the denominators be multiplicity free --- i.e. the height $k$-terms contributing $z^{2k}\beta_1 \cdots \beta_k (1 - z\gamma_0)^{-1} \cdots (1 - z\gamma_k)^{-1}$ ? May 4 at 23:29
• Otherwise we don't recover the Fibonacci generating function $(1 - z -z^2)^{-1}$ upon specializing all the $\gamma$'s and $\beta$'s to 1. May 5 at 0:42
• To put it differently, shouldn't $a_k = z^2\beta_k (1 -z\gamma_k )^{-1}$ for $k \geq 1$ ? May 5 at 2:12