\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{amscd} \usepackage{graphicx} \usepackage{psfig} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics} \usepackage{latexsym} \usepackage{epsf} \usepackage{breakurl} \usepackage{diagbox} \usepackage{array} \usepackage[margin=1in]{geometry} \usepackage{tikz} \usetikzlibrary {arrows.meta} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{observation}[theorem]{Observation} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm {\LARGE\bf Walks in Tiled Rectangles and \\ \vskip .01in Self-Convolutions of Higher-Order\\ \vskip .1in Fibonacci Numbers } \vskip 1cm \large Jan Sedl\'ak and Anton\'\i n Slav\'\i k\\ Faculty of Mathematics and Physics\\ Charles University\\ Sokolovsk\'a 83\\ 186 75 Prague\\ Czech Republic\\ \href{mailto:deg.sedlak@gmail.com}{\tt deg.sedlak@gmail.com}\\ \href{mailto:slavik@karlin.mff.cuni.cz}{\tt slavik@karlin.mff.cuni.cz} \end{center} \vskip .2in \begin{abstract} We derive new formulas for self-convolutions of Fibonacci numbers of arbitrary order using a combinatorial approach based on counting walks in tiled rectangles. This approach leads to a difference equation whose solution can be expressed in terms of weighted sums involving higher-order Fibonacci numbers, and we evaluate these sums via summation by parts. In addition, we provide combinatorial proofs of further convolution identities for Fibonacci numbers. \end{abstract} %\allowdisplaybreaks \section{Introduction} Self-convolutions of the Fibonacci numbers appear in various combinatorial problems, some of which are listed in the {\it On-Line Encyclopedia of Integer Sequences} (OEIS) \cite{OEIS} (see \seqnum{A001629} there), for instance: \begin{itemize} \item Consider sequences of $n$ tosses of a fair coin. It is well known that the number of sequences with no pair of successive heads is $F_{n+2}$, where $(F_n)_{n\in\mathbb Z}$ is the Fibonacci sequence satisfying $F_{n}=F_{n-1}+F_{n-2}$ for all $n\in\mathbb Z$, $F_0=0$, and $F_1=1$. What about sequences of tosses with exactly one pair of successive heads? Suppose the unique pair HH is located at positions $i$, $i+1$. It must be preceded by a sequence of length $i-2$ with no two successive heads, followed by a tail; the number of such prefixes is $F_{i}$. Also, the pair HH must be followed by a tail and a sequence of length $n-i-2$ with no two successive heads; the number of such suffixes is $F_{n-i}$. Hence, the total number of sequences with a unique pair of heads is $\sum_{i=0}^n F_iF_{n-i}$. \item Consider all subsets of $\{1,\dots,n-1\}$ with no two consecutive integers. Clearly, the number of such subsets is $F_{n+1}$, since each subset $S$ can be represented by a sequence of heads and tails, where T's corresponds to elements of $S$, and H's correspond to elements of $\{1,\dots,n-1\}\setminus S$. But what is the total number of elements in such subsets? Let us fix an integer $i\in\{1,\dots,n-1\}$, and calculate how many subsets $S$ contain $i$. Note that $S$ must avoid both $i-1$ and $i+1$. Hence, $S=S_1\cup\{i\}\cup S_2$, where \mbox{$S_1\subset\{1,\dots,i-2\}$}, \mbox{$S_2\subset\{i+2,\dots,n-1\}$}, and $S_1,S_2$ never contain consecutive integers. Since $S_1$ can be chosen in $F_i$ ways and $S_2$ can be chosen in $F_{n-i}$ ways, the total number of subsets containing $i$ is $F_iF_{n-i}$. Hence, the total number of elements in all subsets of \mbox{$\{1,\dots,n-1\}$} with no two successive integers is $\sum_{i=0}^n F_iF_{n-i}$. \item Consider tilings of a $1\times n$ rectangle with monominoes and dominoes, where exactly one of the dominoes is colored. The number of such tilings is again $\sum_{i=0}^n F_iF_{n-i}$. Indeed, if the colored domino is located at positions $i$ and $i+1$, there are $F_i$ ways of tiling the left $1\times(i-1)$ rectangle, and $F_{n-i}$ ways of tiling the right $1\times(n-i-1)$ rectangle. \end{itemize} One of the earliest papers \cite{HM1977} dealing with Fibonacci self-convolutions contains the explicit formula \begin{equation}\label{ordinary-fibonacci-convolution} \sum_{i=0}^n F_iF_{n-i}=\frac{1}{5}((n-1)F_{n+1}+(n+1)F_{n-1}). \end{equation} More general results were obtained by Moree \cite{Moree2004}, who derived explicit formulas for higher-order convolutions Fibonacci numbers expressed in terms of the Fibonacci and Lucas numbers, as well as by Czabarka et al.\ \cite{CFJ2015}, who dealt with generalized Fibonacci (also known as Gibonacci) numbers~$G_n$ with arbitrary initial values $G_1=a$, $G_2=b$, and studies convolutions of the form $\sum_i G_{(k+1)i+1}G_{m-l(k+1)i}$ for arbitrary parameters $k$, $l$, $m$. Another possibility is to replace Fibonacci numbers by their higher-order analogues $(F_{n}^{(m)})_{n\in\mathbb Z}$, which satisfy \[ F^{(m)}_n = F^{(m)}_{n-1}+F^{(m)}_{n-2}+\cdots+F^{(m)}_{n-m},\quad n\in\mathbb Z, \] and \[ F^{(m)}_0=F^{(m)}_1=\cdots=F^{(m)}_{m-2}=0,\qquad F^{(m)}_{m-1}=1. \] These include the Fibonacci numbers ($m=2$), Tribonacci numbers ($m=3$), Tetranacci numbers ($m=4$), Pentanacci numbers ($m=5$), etc. Generalizing the above-mentioned counting problems leads to convolutions of higher-order Fibonacci numbers. For example, it is not difficult to observe that the number of sequences of $n$~coin tosses with no $m$ consecutive heads is $F_{n+m}^{(m)}$. Consequently, the convolution \[ \sum_{i=0}^n F_i^{(m)}F_{n-i}^{(m)} \] counts the number of sequences of length $n-m+2$ with exactly one occurrence of $m$~successive heads: If the $m$ heads occur on positions $i-m+2,\dots,i+1$, there are $F_{i}^{(m)}$ ways to choose a prefix consisting of a sequence of length $i-m$ followed by a tail, and $F_{n-i}^{(m)}$ ways to choose a suffix beginning with a~tail~followed by a sequence of length $n-i-m$. As far as we are aware, there are no explicit formulas for the self-convolutions of Fibonacci numbers of order $m\ge 4$, and the goal of the present paper is to fill this gap. For our purposes, it will be more convenient to replace $n$ by $n+2m-2$. Thus, recalling that $F^{(m)}_0=F^{(m)}_1=\cdots=F^{(m)}_{m-2}=0$, we will focus on sums of the form \[ w^{(m)}_{n}=\sum_{i=0}^{n+2m-2} F_i^{(m)}F_{n+2m-2-i}^{(m)}=\sum_{i=m-1}^{n+m-1} F_i^{(m)}F_{n+2m-2-i}^{(m)}=\sum_{j=0}^{n} F_{j+m-1}^{(m)}F_{n-j+m-1}^{(m)}. \] A neat combinatorial interpretation of these numbers, which correspond to shifted self-convolutions of higher-order Fibonacci numbers, was provided by Khadir et al.\ \cite{KNS2024}: $w^{(m)}_{n}$ is the number of tilings of a $1\times n$ board with linear polyominoes of length at most $m$ having two different colors, where the first tile must have color 1. (Note that their result is more general, dealing with $k$-fold convolutions and $k$ colors.) Our goal is to find an explicit formula for $w^{(m)}_{n}$, and this will also lead to an explicit formula for $\sum_{i=0}^n F_i^{(m)}F_{n-i}^{(m)}$. \begin{figure}[h] \centering \begin{tikzpicture}[x=0.8cm,y=0.8cm] \fill[gray!20] (3,0) rectangle (5,1); \fill[gray!20] (5,0) rectangle (7,1); \draw[thin] (-2,0) rectangle (-1,1); \draw[thin] (1,0) rectangle (2,1); \draw[thin] (-2,0) rectangle (5,1); \draw[thin] (4,0) rectangle (5,1); \draw[thin] (5,0) rectangle (7,1); \draw[thin] (1,0) -- (1,1); \draw[thin] (3,0) -- (3,1); \draw[thin] (4,0) -- (4,1); \draw[line width=2.2pt, blue!70!black, line cap=round, line join=round] (-2,0) -- (0,0) -- (3,0) -- (3,1) -- (5,1) -- (7,1); \end{tikzpicture} \caption{A tiling of a $1 \times 9$ board and an admissible walk.} \label{fibowalk} \end{figure} We begin with an alternative combinatorial interpretation of $w^{(m)}_{n}$, which generalizes a tiling problem studied by N\'emeth \cite{nemeth2024walks}. It is well known (and easy to verify by the standard last-tile argument) that the number of tilings of a $1\times n$ board by linear polyominoes of lengths $1,2,\dots,m$ equals $F^{(m)}_{n+m-1}$. We claim that $w^{(m)}_{n}$ is the number of shortest walks along the edges of such tilings starting in the lower left corner and terminating in the upper right corner. Hence, each walk consists of $n$ unit steps to the right, exactly one unit step upwards, and the upward step must occur at a vertical grid line that is a boundary between tiles (cf.~Figure \ref{fibowalk}). If the upward step occurs after $j$ right-steps, then the tiles to the left of that step form a tiling of length $j$, and the tiles to the right form a tiling of length $n-j$. Hence there are $F^{(m)}_{j+m-1}\,F^{(m)}_{n-j+m-1}$ such walks, and summing over $j$ yields \begin{equation}\label{eq:m-convolution} w^{(m)}_{n}=\sum_{j=0}^{n} F^{(m)}_{j+m-1}\,F^{(m)}_{n-j+m-1}. \end{equation} N\'emeth \cite{nemeth2024walks} deals with the case $m=2$ (i.e., tilings with monominoes and dominoes) and does not mention the convolution formula. Instead, the author derives and solves a~recurrence relation for $w^{(2)}_{n}$. The final formula agrees with the right-hand side of \eqref{ordinary-fibonacci-convolution} in which $n$ is replaced by $n+2m-2=n+2$, i.e., \begin{equation}\label{alternative-vn-formula} w^{(2)}_{n}=\frac{1}{5}((n+1)F_{n+2}+(2n+4)F_{n+1})=\frac{1}{5}((n+1)F_{n+3}+(n+3)F_{n+1}). \end{equation} Our plan is as follows: In Section \ref{subsec:m-fibonacci}, we extend N\'emeth's method \cite{nemeth2024walks} and derive a first-order linear nonhomogeneous recurrence relation for $w^{(m)}_{n}$ (with $m$ being fixed). In order to solve this recurrence, we will need to evaluate weighted Fibonacci sums of the form $\sum_{k=0}^n q^k F^{(m)}_{k+l}$ and $\sum_{k=0}^n k q^k F^{(m)}_{k+l}$; we will achieve this goal using summation by parts in Section~\ref{sec-weighted-sums}. In Section~\ref{solving-recurrence-relation}, we solve the earlier recurrence and obtain an explicit formula for $w^{(m)}_{n}$. In Section~\ref{convolution-identities}, we return to convolutions of the form $\sum_{i=0}^n F_i^{(m)}F_{n-i}^{(m)}$, write down the explicit formulas for small values on $m$, and identify the corresponding sequences in the OEIS. In Section \ref{more-bijections}, we return to counting walks in tiled boards. By distinguishing whether the upward step occurs at an even or odd position, we obtain new combinatorial proofs of additional convolution identities. Several open problems are discussed in the final Section \ref{conclusion}. There is an extensive literature dealing with other convolution-type identities involving the Fibonacci, Lucas, Tribonacci, Jacobsthal, Pell and similar numbers \cite{DT2022,DW2021,DW2024,FG2024,Griffiths2011,Nacin2023}. \section{A recurrence relation for the number of walks}\label{subsec:m-fibonacci} Let $m\in\mathbb N$ be fixed. In the present section, we derive a recurrence relation for $w^{(m)}_{n}$, the number of walks in the $1\times n$ rectangle tiled with linear polyominoes whose length does not exceed $m$. As in Figure~\ref{fibowalk}, each walk partitions the board into two regions, a white region and a gray region. The walk is determined by the unique step upward. We now express \(w^{(m)}_n\) in two different ways. For clarity, we begin with the case $m=2$, and later extend the argument to a general $m$. To simplify notation, denote $v_n=w^{(2)}_{n}$. One approach of counting the walks, described by N\'emeth \cite{nemeth2024walks}, is to condition on the last tile. If the last tile is a monomino, then there are \(v_{n-1}\) walks that reach the red point in the upper-right diagram in Figure~\ref{fig:fibowalk-recurrence}, and a further \(F_n\) walks that reach the blue point and then continue with one step to the right and one step up. The case where the last tile is a domino can be analyzed in a similar manner, and we get the recurrence formula \begin{equation} v_{n} \;=\; v_{n-2}+F_{n-1}+v_{n-1}+F_n \;=\; v_{n-1}+v_{n-2}+F_{n+1}. \label{rekurence wn1} \end{equation} \begin{figure}[t] \centering \begin{tikzpicture}[x=1cm,y=1cm, line cap=round, line join=round] \def\H{0.55} \def\L{4.6} \def\C{0.85} \def\gap{1.05} \tikzset{ board/.style={draw=black, line width=0.4pt}, tile/.style={fill=gray!40, draw=black, line width=0.4pt}, walk/.style={draw=blue!70!black, line width=2.0pt}, redpt/.style={draw=red, fill=white, line width=0.9pt}, cyanpt/.style={draw=cyan!70!black, fill=white, line width=0.9pt}, lab/.style={blue!70!black, font=\normalsize\itshape} } \begin{scope}[shift={(0,1.35)}] \fill[tile] (\L,0) rectangle (\L+2*\C,\H); \draw[board] (0,0) rectangle (\L+2*\C,\H); \draw[board] (\L,0) -- (\L,\H); \node[lab] at (0.5*\L,0.5*\H) {$v_{n-2}$}; \draw[walk] (\L,\H) -- (\L+2*\C,\H); \draw[redpt] (\L,\H) circle (0.08); \end{scope} \begin{scope}[shift={(\L+2*\C+\gap,1.35)}] \fill[tile] (\L,0) rectangle (\L+\C,\H); \draw[board] (0,0) rectangle (\L+\C,\H); \draw[board] (\L,0) -- (\L,\H); \node[lab] at (0.5*\L,0.5*\H) {$v_{n-1}$}; \draw[walk] (\L,\H) -- (\L+\C,\H); \draw[redpt] (\L,\H) circle (0.08); \end{scope} \begin{scope}[shift={(0,0)}] \fill[tile] (\L,0) rectangle (\L+2*\C,\H); \draw[board] (0,0) rectangle (\L+2*\C,\H); \draw[board] (\L,0) -- (\L,\H); \node[lab] at (0.5*\L,0.5*\H) {$F_{n-1}$}; \draw[walk] (0,0) -- (\L+2*\C,0) -- (\L+2*\C,\H); \draw[cyanpt] (\L,0) circle (0.08); \end{scope} \begin{scope}[shift={(\L+2*\C+\gap,0)}] \fill[tile] (\L,0) rectangle (\L+\C,\H); \draw[board] (0,0) rectangle (\L+\C,\H); \draw[board] (\L,0) -- (\L,\H); \node[lab] at (0.5*\L,0.5*\H) {$F_{n}$}; \draw[walk] (0,0) -- (\L+\C,0) -- (\L+\C,\H); \draw[cyanpt] (\L,0) circle (0.08); \end{scope} \end{tikzpicture} \caption{Tiling and walks on a \((1\times n)\)-board (reproduced from N\'emeth \cite{nemeth2024walks}).} \label{fig:fibowalk-recurrence} \end{figure} Here is a second way of calculating \(v_{n}\). There are \(F_{n+1}\) possible tilings of the \(1\times n\) rectangle. Given such a tiling, we may choose any of the \(n+1\) vertical grid lines as the position of the upward step of the walk. If the chosen position lies on a boundary between tiles, the upward step is feasible and we obtain a valid walk on the \(1\times n\) board, contributing to \(v_{n}\). Otherwise, the chosen position cuts through the interior of a domino, so the upward step is not allowed. In that case we remove this domino and place the upward step at its right endpoint; this produces a walk on a \(1\times (n-2)\) rectangle, and all such walks arise in this way. This reasoning yields the recurrence \begin{equation} v_n+v_{n-2}=(n+1)F_{n+1} \label{rekurence wn2} \end{equation} By adding \eqref{rekurence wn1} and \eqref{rekurence wn2}, we get a first-order linear nonhomogeneous recurrence for $v_{n}$: \begin{equation} 2v_n-v_{n-1}=(n+2)F_{n+1}. \label{R1} \end{equation} Extending the preceding argument for a general $m\in\mathbb N$ leads to the following recurrence relation. \begin{theorem} If $w_n^{(m)}$ is the number of shortest walks in a $1\times n$ rectangle tiled with linear polyominoes whose size does not exceed $m$, then \begin{equation}\label{eq:m-final-rec} (m+1)w^{(m)}_{n+1}-2m\,w^{(m)}_n=(n+m+2)F^{(m)}_{n+m}-(n+m)F^{(m)}_{n+m-1},\quad n\in\mathbb N_0. \end{equation} \end{theorem} \begin{proof} Again, we express $w^{(m)}_{n}$ in two different ways. First, distinguish the walk according to the length of the last tile. If the last tile has length $k\in\{1,2,\dots,m\}$, then either the upward step occurs somewhere in the first $n-k$ positions (giving a walk counted by $w^{(m)}_{n-k}$), or the walk is the unique ``lower-boundary'' walk determined by a tiling of length $n-k$ (giving $F^{(m)}_{n-k+m-1}$ possibilities). Summing over $k$ gives \begin{equation}\label{eq:m-rec1} w^{(m)}_{n} =\sum_{k=1}^{m}\bigl(w^{(m)}_{n-k}+F^{(m)}_{n-k+m-1}\bigr) =\sum_{k=1}^{m} w^{(m)}_{n-k}+F^{(m)}_{n+m-1}. \end{equation} Second, fix a tiling of the $1\times n$ board, and choose one of the $n+1$ vertical grid lines as the position of the upward step. If the chosen line lies on a boundary between tiles, the upward step is feasible and we obtain a walk counted by $w^{(m)}_{n}$. Otherwise, if the line lies inside a tile of length $l$, then there are $l-1$ interior vertical lines, and removing that tile and moving the step to its right endpoint produces a walk on a $1\times(n-l)$ board, counted by $w^{(m)}_{n-l}$. Therefore \begin{equation}\label{eq:m-rec2} w^{(m)}_{n}+\sum_{l=2}^{m}(l-1)\,w^{(m)}_{n-l}=(n+1)\,F^{(m)}_{n+m-1}. \end{equation} The final task is to manipulate \eqref{eq:m-rec1} and \eqref{eq:m-rec2} to get a first-order recurrence relation for~$w^{(m)}_{n}$. Subtracting \eqref{eq:m-rec1} from its shifted version (with $n$ replaced by $n+1$), we get \begin{equation}\label{eq:m-diff1} w^{(m)}_{n+1}-w^{(m)}_{n} = w^{(m)}_{n}-w^{(m)}_{n-m} + F^{(m)}_{n+m}-F^{(m)}_{n+m-1}. \end{equation} Similarly, subtracting \eqref{eq:m-rec2} from its shifted version (with $n$ replaced by $n+1$), we obtain \begin{equation}\label{eq:m-diff2} (n+2)F^{(m)}_{n+m}-(n+1)F^{(m)}_{n+m-1} =w^{(m)}_{n+1}-w^{(m)}_{n}+\sum_{j=1}^{m-1} w^{(m)}_{n-j}-(m-1)w^{(m)}_{n-m}. \end{equation} Using \eqref{eq:m-rec1} to rewrite \[ \sum_{j=1}^{m-1}w^{(m)}_{n-j} =\sum_{k=1}^{m}w^{(m)}_{n-k}-w^{(m)}_{n-m} =w^{(m)}_{n}-F^{(m)}_{n+m-1}-w^{(m)}_{n-m} \] and substituting into \eqref{eq:m-diff2}, we obtain \begin{equation}\label{eq:m-diff-substituted} \begin{aligned} (n+2)F^{(m)}_{n+m}-(n+1)F^{(m)}_{n+m-1} &=w^{(m)}_{n+1}-w^{(m)}_{n}+w^{(m)}_{n}-F^{(m)}_{n+m-1}-m\,w^{(m)}_{n-m}\\ &=w^{(m)}_{n+1}-F^{(m)}_{n+m-1}-m\,w^{(m)}_{n-m}. \end{aligned} \end{equation} Equivalently, \begin{equation}\label{eq:m-w-rec} w^{(m)}_{n+1}=(n+2)F^{(m)}_{n+m}-n\,F^{(m)}_{n+m-1}+m\,w^{(m)}_{n-m}. \end{equation} Multiplying \eqref{eq:m-diff1} by $m$ and adding \eqref{eq:m-w-rec} yields the recurrence \eqref{eq:m-final-rec}. \end{proof} \section{Weighted sums with higher-order Fibonacci\\ numbers}\label{sec-weighted-sums} In order to solve the recurrence \eqref{eq:m-final-rec} and obtain an explicit formula for $w^{(m)}_n$, we will need to evaluate sums of the form \[ S(m,n,l,q) := \sum_{k=0}^{n} q^k F^{(m)}_{k+l}, \] where $m\in\mathbb N$, $n\in\mathbb N_0$, $l\in\mathbb Z$, $q\in\mathbb R$. As shown by Slav\'\i k \cite{Slavik-2025}, weighted Fibonacci sums can be evaluated using summation by parts. The following result might be of independent interest. The calculations in the present section do not depend on the choice of the initial values $F^{(m)}_0,\ldots,F^{(m)}_{m-1}$; we only assume that the sequence $(F_n^{(m)})_{n\in\mathbb Z}$ satisfies \[ F^{(m)}_n=F^{(m)}_{n-1}+\cdots+F^{(m)}_{n-m},\quad n\in\mathbb Z. \] \begin{theorem} If $q^{m+1}-2q+1\neq 0$, then \begin{align*} S(m,n,l,q) =\frac{(q-1)\left(\!q^{n+1}F^{(m)}_{n+l+1}-F^{(m)}_l +\sum\limits_{i=1}^{m-1}\left(\sum\limits_{j=1}^{i}q^{i+1-j}\left(q^{n+1}F^{(m)}_{n+l-j+1}- F^{(m)}_{l-j}\right)\right)\right)}{q^{m+1}-2q+1}. \end{align*} \end{theorem} \begin{proof} Recalling that the antidifference to $q^k$ is $q^k/(q-1)$, summation by parts gives \begin{align*} S(m,n,l,q)&=\sum_{k=0}^n q^k F^{(m)}_{k+l} =\left[\frac{q^k}{q-1}F^{(m)}_{k+l}\right]_{k=0}^{n+1}- \sum_{k=0}^n \frac{q^{k+1}}{q-1} \left(F^{(m)}_{k+l+1}-F^{(m)}_{k+l}\right)\\ &=\frac{1}{q-1}\left(q^{n+1}F^{(m)}_{n+l+1}-F^{(m)}_l -\sum_{k=0}^n q^{k+1}\sum_{i=1}^{m-1}F^{(m)}_{k+l-i} \right)\\ &=\frac{1}{q-1}\left(q^{n+1}F^{(m)}_{n+l+1}-F^{(m)}_l -\sum_{i=1}^{m-1}q^{i+1}\sum_{k=0}^n q^{k-i}F^{(m)}_{k+l-i} \right)\\ &=\frac{1}{q-1}\left(q^{n+1}F^{(m)}_{n+l+1}-F^{(m)}_l -\sum_{i=1}^{m-1}q^{i+1}\sum_{k=-i}^{n-i} q^{k}F^{(m)}_{k+l} \right)\\ \noalign{\begin{align*}&=\frac{q^{n+1}F^{(m)}_{n+l+1}-F^{(m)}_l -\sum_{i=1}^{m-1}q^{i+1}\left(S(m,n,l,q)-\sum_{j=0}^{i-1}q^{n-j}F^{(m)}_{n+l-j}+\sum_{j=1}^i q^{-j}F^{(m)}_{l-j}\right) }{q-1} \\ &=\frac{q^{n+1}F^{(m)}_{n+l+1}-F^{(m)}_l -S(m,n,l,q)\sum\limits_{i=1}^{m-1}q^{i+1}+\sum\limits_{i=1}^{m-1}\left(\sum\limits_{j=1}^{i}q^{i+1-j}\left(q^{n+1}F^{(m)}_{n+l-j+1}-F^{(m)}_{l-j}\right)\right) }{q-1}. \end{align*} } \end{align*} Solving this for $S(m,n,l,q)$ yields \begin{align*} S(m,n,l,q)&=\frac{q^{n+1}F^{(m)}_{n+l+1}-F^{(m)}_l +\sum\limits_{i=1}^{m-1}\left(\sum\limits_{j=1}^{i}q^{i+1-j}\left(q^{n+1}F^{(m)}_{n+l-j+1}- F^{(m)}_{l-j}\right)\right) }{(q-1)\left(1+\frac{\sum\limits_{i=1}^{m-1}q^{i+1}}{q-1}\right)}, \end{align*} and the proof is finished by a simple algebraic manipulation. \end{proof} We will also need to evaluate sums of the form \[ S_2(m,n,l,q)=\sum_{k=0}^n k q^k F^{(m)}_{k+l}, \] where $m\in\mathbb N$, $n\in\mathbb N_0$, $q\in\mathbb R$, $l\in\mathbb Z$. This is easily achieved by differentiating $S(m,n,l,q)$ with respect to $q$; since \[ \frac{\partial}{\partial q}S(m,n,l,q)=\sum_{k=1}^n k q^{k-1} F^{(m)}_{k+l}=\sum_{k=0}^n k q^{k-1} F^{(m)}_{k+l}, \] we have \[ S_2(m,n,l,q)=q\frac{\partial}{\partial q}S(m,n,l,q). \] Although it is not difficult to calculate the derivative on the right-hand side, the result is not particularly enlightening, so we prefer to keep the formula in the present simple form. \section{Explicit formula for the number of walks}\label{solving-recurrence-relation} After a brief digression, we return to the recurrence \eqref{eq:m-final-rec} for the number of paths in tiled boards, i.e., \begin{equation}\label{wn-recurrence} (m+1)w^{(m)}_{n+1}-2m w^{(m)}_n=(n+m+2)F^{(m)}_{n+m}-(n+m)F^{(m)}_{n+m-1},\quad n\in\mathbb N_0,\quad w^{(m)}_0=1. \end{equation} We will express the solution in terms of the sums $S$ and $S_2$ introduced in the previous section. \begin{theorem} For each $m\in\mathbb N$, the solution of the recurrence \eqref{wn-recurrence} is given by \begin{align*} w^{(m)}_n&=\left(\frac{2m}{m+1}\right)^n+\frac{(2m)^{n-1}}{(m+1)^n}\Biggl((m+2)S\left(m,n-1,m,\frac{m+1}{2m}\right)\\&+S_2\left(m,n-1,m,\frac{m+1}{2m}\right) -mS\left(m,n-1,m-1,\frac{m+1}{2m}\right)\\&-S_2\left(m,n-1,m-1,\frac{m+1}{2m}\right) \Biggr),\quad n\in\mathbb N_0. \end{align*} \end{theorem} \begin{proof} The solution of the general first-order recurrence relation \begin{equation}\label{general-recurrence} a_{n+1}-\alpha a_n=\beta_n,\quad n\in\mathbb N_0,\quad a_0=1, \end{equation} is given by \[ a_n=\alpha^n+\sum_{k=0}^{n-1}\alpha^{n-k-1}\beta_k \] \cite[formula (1.2.6)]{Elaydi}. Our recurrence \eqref{wn-recurrence} is a special case of \eqref{general-recurrence} with \[ \alpha=\frac{2m}{m+1},\quad \beta_n=\frac{n+m+2}{m+1}F^{(m)}_{n+m}-\frac{n+m}{m+1}F^{(m)}_{n+m-1}. \] Hence, the solution is \begin{align*} w^{(m)}_n&=\left(\frac{2m}{m+1}\right)^n+\sum_{k=0}^{n-1}\left(\frac{2m}{m+1}\right)^{n-k-1}\left(\frac{k+m+2}{m+1}F^{(m)}_{k+m}-\frac{k+m}{m+1}F^{(m)}_{k+m-1}\right)\\ &= \left(\frac{2m}{m+1}\right)^n+\frac{(2m)^{n-1}}{(m+1)^n}\sum_{k=0}^{n-1}\left(\frac{2m}{m+1}\right)^{-k}\left((k+m+2)F^{(m)}_{k+m}-(k+m)F^{(m)}_{k+m-1}\right)\\ &= \left(\frac{2m}{m+1}\right)^n+\frac{(2m)^{n-1}}{(m+1)^n}\Biggl((m+2)\sum_{k=0}^{n-1}\left(\frac{2m}{m+1}\right)^{-k}F^{(m)}_{k+m}+\sum_{k=0}^{n-1}\left(\frac{2m}{m+1}\right)^{-k}kF^{(m)}_{k+m}\\ &-m\sum_{k=0}^{n-1}\left(\frac{2m}{m+1}\right)^{-k}F^{(m)}_{k+m-1}-\sum_{k=0}^{n-1}\left(\frac{2m}{m+1}\right)^{-k}kF^{(m)}_{k+m-1}\Biggr), \end{align*} and the proof is finished by recalling the definitions of $S$ and $S_2$. \end{proof} \section{Self-convolution identities}\label{convolution-identities} In the present section, we return to the standard $m$-the order Fibonacci sequence having the initial terms \[ F^{(m)}_0=\cdots=F^{(m)}_{m-2}=0,\quad F^{(m)}_{m-1}=1, \] and study its self-convolutions. According to \eqref{eq:m-convolution}, we have \[ \sum_{i=0}^n F^{(m)}_{i+m-1}F^{(m)}_{n-i+m-1}=w^{(m)}_n, \] where $(w^{(m)}_n)_{n=0}^\infty$ satisfies the recurrence \eqref{wn-recurrence}. Using the formula for $w^{(m)}_n$ from the previous section, we get \begin{align*} \sum_{i=0}^n F^{(m)}_{i+m-1}F^{(m)}_{n-i+m-1}&=\left(\frac{2m}{m+1}\right)^n+\frac{(2m)^{n-1}}{(m+1)^n}\Biggl((m+2)S\left(m,n-1,m,\frac{m+1}{2m}\right)\\&+S_2\left(m,n-1,m,\frac{m+1}{2m}\right) -mS\left(m,n-1,m-1,\frac{m+1}{2m}\right)\\ &-S_2\left(m,n-1,m-1,\frac{m+1}{2m}\right) \Biggr). \end{align*} It is perhaps more natural to replace $n$ by $n-2m+2$, which yields the $n$-the term of the self-convolution of $(F_{n}^{(m)})_{n=0}^\infty$, namely \begin{align*} \sum_{i=0}^{n-2m+2} F^{(m)}_{i+m-1}F^{(m)}_{n-i-m+1}&=F_{m-1}^{(m)}F_{n-m+1}^{(m)}+\cdots+F_{n-m+1}^{(m)}F_{m-1}^{(m)}\\ &=F_{0}^{(m)}F_{n}^{(m)}+\cdots+F_{n}^{(m)}F_{0}^{(m)}=\sum_{i=0}^nF_{i}^{(m)}F_{n-i}^{(m)}, \end{align*} where we used the fact that $F^{(m)}_0=\cdots=F^{(m)}_{m-2}=0$. This leads to the following main result. \begin{theorem} For all $m\in\mathbb N$ and $n\in\mathbb N_0$, we have \begin{align*} \sum_{i=0}^nF_{i}^{(m)}F_{n-i}^{(m)}&=w^{(m)}_{n-2m+2} \\&=\left(\frac{2m}{m+1}\right)^{n-2m+2}+\frac{(2m)^{n-2m+1}}{(m+1)^{n-2m+2}}\Biggl((m+2)S\left(m,n-2m+1,m,\frac{m+1}{2m}\right)\\ &+S_2\left(m,n-2m+1,m,\frac{m+1}{2m}\right) -mS\left(m,n-2m+1,m-1,\frac{m+1}{2m}\right)\\&-S_2\left(m,n-2m+1,m-1,\frac{m+1}{2m}\right) \Biggr). \end{align*} \end{theorem} Using the formulas for $S$ and $S_2$, we can write down special cases of the previous identity for an arbitrary choice of $m$. We use \textit{Wolfram Mathematica} to evaluate $S$ and $S_2$, and to transform the resulting expression using the recurrence $F^{(m)}_j=F^{(m)}_{j-1}+\cdots+F^{(m)}_{j-m}$ so that it contains only those terms $F^{(m)}_j$ with $j\in\{n-m+1,\dots, n\}$. For $m=2$, we get the Fibonacci identity \[ F_0^{(2)}F_{n}^{(2)}+\cdots+F_{n}^{(2)}F_{0}^{(2)} = \frac{1}{5}(2nF_{n-1}^{(2)}+(n-1)F_{n}^{(2)}), \] which is in agreement with \eqref{ordinary-fibonacci-convolution}, and whose sides correspond to the sequence \seqnum{A001629}. For $m=3$, we get the Tribonacci identity \begin{align*} F_0^{(3)}F_{n}^{(3)}+\cdots+F_{n}^{(3)}F_{0}^{(3)} &= \frac{1}{22}((5n-5)F_{n-2}^{(3)}+(n-5)F_{n-1}^{(3)}+(2n-4)F_{n}^{(3)}), \end{align*} whose sides correspond to the sequence \seqnum{A073778}; the explicit formula (written in a slightly different form) was derived by Gryszka \cite{Gryszka} using generating functions. For $m=4$, we get the Tetranacci identity \begin{align*} F_0^{(4)}F_{n}^{(4)}+\cdots+F_{n}^{(4)}F_{0}^{(4)} &=\frac{1}{563}((86n-172)F_{n-3}^{(4)}+(-n-85)F_{n-2}^{(4)}+(15n-85)F_{n-1}^{(4)}\\&+(25n-75)F_{n}^{(4)}), \end{align*} whose sides correspond to a shifted version of the sequence \seqnum{A118898}. The interpretation in terms of convolution and the explicit formula are new. For $m=5$, we get the new Pentanacci identity \begin{align*} F_0^{(5)}F_{n}^{(5)}+\cdots+F_{n}^{(5)}F_{0}^{(5)} &= \frac{1}{1198}((136n-408)F_{n-4}^{(5)}+(-22n-92)F_{n-3}^{(5)}\\&+(3n-117)F_{n-2}^{(5)}+(18n-117)F_{n-1}^{(5)}+(27n-108)F_{n}^{(5)}). \end{align*} \section{More bijections}\label{more-bijections} As in Section \ref{subsec:m-fibonacci}, let $v_n$ denote the number of shortest walks on a tiled $1\times n$ board with a single upward step allowed at an arbitrary position (along a vertical tile boundary). Then \begin{equation} \label{e_n+o_n} v_n=e_n+o_n, \end{equation} where $e_n$ is the number of walks with the upward step at an even position, and $o_n$ is the number of walks with the upward step at an odd position. In the next lemma, we use bijections to establish relations between $e_n$ and $o_n$. \begin{lemma}\label{lem:diff-even-odd} For every $k\in\mathbb N$, we have \begin{align} e_{2k-1}&=o_{2k-1},\label{eq:diff-odd}\\ e_{2k}&=o_{2k}+F_{2k+2}.\label{eq:diff-even} \end{align} \end{lemma} \begin{proof} For $1\times (2k-1)$ rectangles, the horizontal flip is a bijection between tilings with an upward step at an even position and those with an upward step at an odd position. Hence, \eqref{eq:diff-odd} holds. To prove \eqref{eq:diff-even}, we rewrite it as \begin{equation} e_{2k}=o_{2k}+F_{2k}+F_{2k+1}. \end{equation} We make the following observations concerning the terms on the right-hand side: \begin{itemize} \item $F_{2k+1}$ counts all tilings of a $1\times 2k$ rectangle. This coincides with the number of walks in a~tiled $1\times 2k$ rectangle whose upward step occurs at position $2k$. \item \(F_{2k}\) counts all tilings of a \(1\times (2k-1)\) rectangle. For each tiling, let the last monomino (there is at least one) determine a walk by placing the upward step along its left border and replacing the monomino with a domino. This yields a walk in a \(1\times 2k\) rectangle with an upward step at an even position less than \(2k\), followed only by dominoes. This defines a bijection, with the following inverse map: given a walk with the upward step at an even position less than \(2k\) followed only by dominoes, replace the domino immediately after the upward step with a monomino and remove the walk. \item By definition, \(o_{2k}\) counts walks in a \(1\times 2k\) rectangle whose upward step occurs at an odd position. For each walk, swap the upward step with the first monomino preceding it (there is at least one). This produces a walk with the upward step at an even position, followed by at least one monomino (cf.\ Figures~\ref{before} and~\ref{after}). Again, this is a bijection, with the following inverse: for a walk with an upward step at an even position followed by at least one monomino, swap the upward step with the first monomino after it. \end{itemize} Hence, $o_{2k}+F_{2k}+F_{2k+1}$ counts all walks in a $1\times 2k$ rectangle whose upward step occurs at an even position. \end{proof} \begin{figure}[h] \centering \begin{tikzpicture}[x=0.8cm,y=0.8cm] \fill[gray!20] (5,0) rectangle (6,1); \fill[gray!20] (6,0) rectangle (8,1); \fill[red] (2,0) rectangle (3,1); \draw[thin] (-2,0) rectangle (-1,1); \draw[thin] (-1,0) rectangle (0,1); \draw[thin] (0,0) rectangle (2,1); \draw[thin] (2,0) rectangle (3,1); \draw[thin] (3,0) rectangle (5,1); \draw[thin] (5,0) rectangle (6,1); \draw[thin] (6,0) rectangle (8,1); \draw[line width=2.2pt, blue!70!black, line cap=round, line join=round] (-2,0) -- (0,0) -- (5,0) -- (5,1) -- (7,1) -- (8,1); \end{tikzpicture} \caption{Upward step at odd position $j$ and first preceding monomino between positions $i$ and $i+1$, where $i$ is even.} \label{before} \end{figure} \begin{figure}[h] \centering \begin{tikzpicture}[x=0.8cm,y=0.8cm] \fill[gray!20] (2,0) rectangle (4,1); \fill[gray!20] (5,0) rectangle (6,1); \fill[gray!20] (6,0) rectangle (8,1); \fill[red] (4,0) rectangle (5,1); \draw[thin] (-2,0) rectangle (-1,1); \draw[thin] (-1,0) rectangle (0,1); \draw[thin] (0,0) rectangle (2,1); \draw[thin] (2,0) rectangle (4,1); \draw[thin] (4,0) rectangle (5,1); \draw[thin] (5,0) rectangle (6,1); \draw[thin] (6,0) rectangle (8,1); \draw[line width=2.2pt, blue!70!black, line cap=round, line join=round] (-2,0) -- (0,0) -- (2,0) -- (2,1) -- (7,1) -- (8,1); \end{tikzpicture} \caption{After swap, the upward step is at even position $i$, and the monomino is between positions $j-1$ and $j$.} \label{after} \end{figure} We can now derive explicit formulas for $e_n$ and $o_n$, keeping in mind that we have already established an explicit formula for $v_n$. \begin{theorem}\label{thm:explicit-eo-from-w} For every $k\in\mathbb N$, we have \begin{align} e_{2k-1} &= o_{2k-1}= \frac{v_{2k-1}}{2}, \label{eq:explicit-odd-from-w}\\ e_{2k} &= \frac{v_{2k}+F_{2k+2}}{2}, \quad o_{2k} = \frac{v_{2k}-F_{2k+2}}{2}, \label{eq:explicit-even-from-w}. \end{align} \end{theorem} \begin{proof} The relations \eqref{eq:explicit-odd-from-w} follow from $e_{2k-1}=o_{2k-1}$ and $e_{2k-1}+o_{2k-1}=v_{2k-1}$. Similarly, the relations \eqref{eq:explicit-even-from-w} follow from $e_{2k}-o_{2k}=F_{2k+2}$ and $e_{2k}+o_{2k}=v_{2k}$. \end{proof} Note that $e_n$ and $o_n$ can also be counted in another way: once the position of the upward step in a walk is fixed, the left and right parts of the rectangle can be tiled arbitrarily. This gives the formulas \begin{align*} e_{2k}&=\sum_{i=0}^k F_{2i+1}F_{2k-2i+1}=F_1F_{2k+1}+F_3F_{2k-1}+\cdots+F_{2k+1}F_1,\label{odd-convolution} \end{align*} \begin{align*} o_{2k}&=\sum_{i=0}^{k-1}F_{2i+2}F_{2k-2i}=F_2F_{2k}+F_4F_{2k-2}+\cdots+F_{2k}F_2,\\ e_{2k-1}&=\sum_{i=0}^{k-1}F_{2i+1}F_{2k-2i}=F_1F_{2k}+F_3F_{2k-2}+\cdots+F_{2k}F_1. \end{align*} Using the explicit formulas for $e_n$ and $o_n$ from Theorem \ref{thm:explicit-eo-from-w}, we can evaluate the convolutions on the right-hand sides. For example, recalling that $v_n=w_n^{(2)}$ and using formula \eqref{alternative-vn-formula}, we get \begin{align*} e_{2k}=\frac{v_{2k}+F_{2k+2}}{2} &=\frac{\frac{1}{5}\left((2k+1)F_{2k+2}+(4k+4)F_{2k+1}\right)+F_{2k+2}}{2}\\ &=\frac{(2k+2)F_{2k+1}+(k+3)F_{2k+2}}{5}. \end{align*} This result was obtained in our recent paper as a special case of an identity involving Chebyshev polynomials \cite[Lemma A.2 and Corollary A.3]{Sedlak-Slavik-2025}. We posed it as an open problem to prove this identity combinatorially, and here we accomplish this task. All convolutions in the present section are special cases of the sums \[ \sum_i G_{(k+1)i+1}G_{m-l(k+1)i},\] which were evaluated by Czabarka et al.\ \cite{CFJ2015} using extensive computations with generating functions. Therefore, we believe that our combinatorial proofs, based on the bijections developed in Lemma~\ref{lem:diff-even-odd}, may be of independent interest. \section{Conclusion}\label{conclusion} Finally, we offer a list of possible projects for the interested reader: \begin{itemize} \item Find explicit formulas for $k$-fold convolutions of Fibonacci numbers of order~$m$. Note that these convolutions have a natural combinatorial interpretation; see, for instance, the colored tiling model described by Khadir et al.\ \cite{KNS2024}. \item Investigate whether the methods of the present article extend to bracelet (annular) tilings. Do they yield explicit formulas for convolutions of higher-order Lucas numbers? \item Following Section~\ref{more-bijections}, count the number of walks whose upward step occurs in an even or odd position, respectively. Assume that the rectangle is tiled not only by monominoes and dominoes, but also by trominoes or possibly longer polyominoes. This may lead to new identities involving Tribonacci or higher-order Fibonacci numbers. For instance, a numerical analysis of walks in the monomino-domino-tromino case appears to yield an analogue of Lemma~\ref{lem:diff-even-odd}, in which the difference between the numbers of even and odd walks is given by the sum of even-indexed Tribonacci numbers. \item It appears that the self-convolution formulas in Section~\ref{convolution-identities} are related to the sequence whose initial terms are $1, 5, 44, 563, 9584, 205937,\dots$. Up to sign, this is sequence \seqnum{A106273} from the OEIS, which gives the discriminants of the polynomials $x^m - x^{m-1} - \cdots - x - 1$, that is, the characteristic polynomials of the recurrence defining Fibonacci numbers of order~$m$. If the right-hand sides of the self-convolution identities are multiplied by these numbers, one obtains linear combinations of Fibonacci numbers of order $m$ with integer coefficients. What explains this phenomenon? \end{itemize} \begin{thebibliography}{99} \bibitem{BG2016} A. Bramham and M. Griffiths, {Combinatorial interpretations of some convolution identities}, \textit{Fibonacci Quart.} \textbf{54} (2016), 335--339. \bibitem{CFJ2015} \'E. Czabarka, R. Fl\'orez, and L. Junes, {A discrete convolution on the generalized Hosoya triangle}, \textit{J. Integer Sequences} \textbf{18} (2015), \href{https://cs.uwaterloo.ca/journals/JIS/VOL18/Florez/florez12.html}{Article 15.1.6}. \bibitem{DT2022} G. Dresden and M. Tulskikh, {Convolutions of sequences with similar linear recurrence formulas}, \textit{J. Integer Sequences} \textbf{25} (2022), \href{https://cs.uwaterloo.ca/journals/JIS/VOL25/Dresden/dresden12.html}{Article~22.3.3}. \bibitem{DW2021} G. Dresden and Y. Wang, {Sums and convolutions of $k$-bonacci and $k$-Lucas numbers}, \textit{Integers} \textbf{21} (2021), Article A56. \bibitem{DW2024} G. Dresden and Y. Wang, {A general convolution identity}, \textit{Math. Mag.} \textbf{97} (2024), 98--109. \bibitem{Elaydi} S. Elaydi, \textit{An Introduction to Difference Equations. Third Edition}, Springer, 2005. \bibitem{FG2024} R. Frontczak and K. Gryszka, {General convolution sums involving Fibonacci $m$-step numbers}, \textit{J. Integer Sequences} \textbf{27} (2024), \href{https://cs.uwaterloo.ca/journals/JIS/VOL27/Gryszka/gryszka12.html}{Article 24.8.8}. \bibitem{Griffiths2011} M. Griffiths, {Fibonacci diagonals}, \textit{Fibonacci Quart.} \textbf{49} (2011), 51--56. \bibitem{Gryszka} K. Gryszka, A note on the self-convolution of the Tribonacci sequence, \textit{Notes Number Theory Discrete Math.} \textbf{32} (2026), 133--136. \bibitem{HM1977} V.~E.~Hoggatt and M.~Bicknell-Johnson, {Fibonacci convolution sequences}, \textit{Fibonacci Quart.} \textbf{15} (1977), 117--122. \bibitem{KNS2024} O. Khadir, L. N\'emeth, and L. Szalay, {Tiling of dominoes with ranked colors}, \textit{Results Math.} \textbf{79} (2024), Article 253. \bibitem{Moree2004} P. Moree, {Convoluted convolved Fibonacci numbers}, \textit{J. Integer Sequences} \textbf{7} (2004), \href{https://cs.uwaterloo.ca/journals/JIS/VOL7/Moree/moree12.html}{Article 04.2.2}. \bibitem{Nacin2023} D. Nacin, {Fibonacci convolutions}, \textit{Math. Mag.} \textbf{96} (2023), 356--358. \bibitem{nemeth2024walks} L. N\'emeth, {Walks on tiled boards}, \textit{Math. Slovaca} \textbf{74} (2024), 1369--1382. \bibitem{OEIS} OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2026. Available at \url{https://oeis.org}. \bibitem{Sedlak-Slavik-2025} J. Sedl\'ak and A. Slav\'ik, {Resistance distances and Kirchhoff indices in graph joins}, \textit{J.~Phys. A }\textbf{58} (2025), Article 505203. \bibitem{Slavik-2025} A. Slav\'\i k, {Discrete calculus and weighted Fibonacci and Tribonacci sums}, \textit{Amer. Math. Monthly }\textbf{132} (2025), 622--633. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2020 {\it Mathematics Subject Classification}: Primary 11B39; Secondary 05A19, 11B37, 05B45, 52C20. \noindent \emph{Keywords: } Fibonacci number, Tribonacci number, convolution, tiling. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A001629}, \seqnum{A073778}, \seqnum{A106273}, \seqnum{A118898}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received April 15 2026; revised versions received April 16 2026; May 29 2026; May 30 2026. Published in {\it Journal of Integer Sequences}, June 1 2026. \bigskip \hrule \bigskip \noindent Return to \href{https://cs.uwaterloo.ca/journals/JIS/}{Journal of Integer Sequences home page}. \vskip .1in \end{document}