\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\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}

\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}}}


\usepackage{enumerate}
\usepackage{booktabs}
\usepackage{tikz}
	\usetikzlibrary{tikzmark, calc}
	\usetikzlibrary{automata,positioning}
	\tikzset{every state/.style={inner sep=0pt,minimum size=28pt}}
\usepackage{vmargin}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}

\newcommand{\val}{\mathrm{val}}

\begin{document}

\begin{center}
\includegraphics[width=4in]{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}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
Redundance in the Signed $m$-Bonacci \\
\vskip .1in
Numeration System
}
\vskip 1cm
\large
Zuzana Mas\'akov\'a and \'Elise Vandomme\\
Department of Mathematics FNSPE\\
Czech Technical University in Prague\\
Trojanova 13 \\
120 00 Praha 2\\
Czech Republic\\
\href{mailto:zuzana.masakova@fjfi.cvut.cz}{\tt zuzana.masakova@fjfi.cvut.cz} \\
\end{center}

\vskip .2 in

\begin{abstract}
We study redundance in the signed $m$-bonacci numeration system. We
determine the number of representations of 0 in this system and describe
the automaton accepting the language of such representations. We reveal
a surprising connection between Fibonacci and Tribonacci numbers.
\end{abstract}

\section{Introduction}

Integers are usually represented as sums of powers of a base $q\in\N$ for
$q\geq 2$. In particular, every $x\in\N$ can be written as $x=\sum_{j=1}^{n}a_jq^{j-1}$.
If $a_j\in\{0,1,\dots,q-1\}$ and $a_n\neq 0$, then such a representation of $x$ is unique. One can replace the sequence $(q^{j-1})_{j\geq 1}$ of powers of the base by any linear recurrence sequence $(G_j)_{j\geq 1}$. For details about such representations for a general linear recurrence sequence $(G_j)$ and conditions on uniqueness, see~\cite{PeTi89}
or~\cite[Chapter 7]{lothaire2}.

Perhaps the first example of a possibility of representing integers in these so-called linear numeration systems is the well-known Zeckendorf numeration system~\cite{Lekkerkerker}, where for $(G_j)$ we take the sequence of Fibonacci numbers $G_j=F_j$, where $F_1=1$, $F_2=2$, $F_{j+2}=F_{j+1}+F_j$ for $j\geq 1$.
The representation of an integer $x$ in the form $x=\sum_{j=1}^{n}a_jF^{j}$ is unique if $a_j\in\{0,1\}$ where $a_j\cdot a_{j-1}=0$, i.e., the sequence of coefficients does not contain consecutive 1's. This representation can be obtained by the greedy algorithm. Relaxing the condition on consecutive 1's, the system becomes redundant even with the alphabet of digits $\{0,1\}$.  The function $R(n)$ expressing the number of representations of $n\in\N$ has been studied by several authors. Berstel~\cite{Berstel01} provided a formula for calculating $R(n)$ based on the greedy representation of $n$. A different way of computation was given by Edson and Zamboni~\cite{EdZa04}. Koc\'abov\'a et al.~\cite{KoMaPe05} and Stockmeyer~\cite{Stock} studied the function $R(n)$ in more detail.

A similar study was performed for different linear recurrence sequences~\cite{GrKiTi}. The $m$-bonacci sequence as a natural generalization of the Fibonacci case $m=2$ was considered by Koc\'abov\'a et al.~\cite{KoMaPe07} and Edson and Zamboni~\cite{EdZa06}. Second-order linear recurrences were studied by Edson~\cite{Edson}. In all these cases, the alphabet of digits was chosen to be the minimal one allowing representation of every integer. In the case of the $m$-bonacci system, this means the alphabet $\{0,1\}$.


One can extend the study even more, to considering redundance when the alphabet contains more than the necessary number of digits.
Considering such representations may have practical consequences, e.g.,\ for the possibility to define algorithms for parallel addition or algorithms for fast multiplication using non-adjacent form or representations of minimal weight. Parallel addition for a numeration system with integer base $q\geq 3$ was given by Avizienis~\cite{Avizienis}. For a signed binary system (with the alphabet $\{-1,0,1\}$), the algorithm was described by 
Chow and Robertson~\cite{ChowRob}. An algorithm for parallel addition in the Fibonacci system with alphabet $\{-1,0,1\}$ was given by Frougny et al.~\cite{FrPeSv}. Minimal weight expansions were studied, for example, by Heuberger~\cite{Heuberger} and Grabner~\cite{GrHe06}.
Similar questions are examined by Frougny and Steiner~\cite{FroSt} in systems with real algebraic base $\beta$ which are directly connected to linear numeration systems~\cite{Frougny92fr}.

In this paper we study the linear numeration system based on the $m$-bonacci sequence over the alphabet of digits $\{-1,0,1\}$.
We show that the number $r(k)$ of representations of $0$ in the $m$-bonacci system over $\{-1,0,1\}$ of length at most $k$ is also a linear recurrence sequence and we determine the corresponding recurrence of order $m+1$. The proof of this result uses the $m$-bonacci numeration system with the alphabet $\{0,1,2\}$.
We also present the automaton accepting precisely the representations of $0$ over $\{-1,0,1\}$.



\section{Representations}

\begin{definition}
	Let $m\in\N$ with $m\ge 2$.
	Let $(T_k)_{k\ge 1}$ denote the $m$-bonacci sequence defined by
	$$
    T_k= 2^{k-1} \text{ for } k\in\{1,\ldots,m\}\ \text{ and }\ T_{k}= \sum_{j=1}^{m} T_{k-j}\text{ for }k> m.
    $$
\end{definition}

\begin{definition}\label{d:rep}
	Let $A\subset{\mathbb N}$ be an alphabet.
	A positive integer $n$ is \emph{represented} by $(a_\ell a_{\ell-1}\cdots a_1)$ if $n=\sum_{j=1}^\ell a_j T_j$ with $a_j\in A$ and $a_\ell\ne 0$.
	In that case, $\ell$ is the \emph{length} of the representation.
	The number $n$ represented by $(a_\ell a_{\ell-1}\cdots a_1)$ is called the \emph{value} of $(a_\ell a_{\ell-1}\cdots a_1)$ and is denoted by $\val(a_\ell a_{\ell-1}\cdots a_1)$.
	Let $p_A(n)$ denote the number of representations of $n$ over the alphabet $A$ and by $p_A(n,i)$ the number of representations of $n$ of length exactly $i$ over the alphabet $A$. If the alphabet is clear from the context, we simply write $p(n)$ and $p(n,i)$.
\end{definition}

Our aim is to enumerate the representations of 0 in the $m$-bonacci system with the alphabet $B=\{-1,0,1\}$. Conveniently, we transfer the question to determine
the number of representations in the system with the alphabet $A=\{0,1,2\}$ of the number $N_k$, where $(N_k)_{k\ge 1}$ is the running sum of the sequence $(T_k)_{k\ge 1}$, i.e.,
$$
N_{k}= \sum_{j=1}^{k} T_j\ \text{ for } k\ge 1.
$$
We set $N_0:=0$. In fact, adding 1 to every digit in a representation of 0 over $B=\{-1,0,1\}$ of length $k$, we obtain a representation of $N_k$ over the alphabet $A=\{0,1,2\}$. The exact relation of the two systems with alphabets $A$ and $B$ is explained in Section~\ref{sec:signed}.

First, let us present some computer calculations of $p(N_k)$ for the $m$-bonacci system with $m=2,3,4$, and $5$.
We count the number of representations of $N_k$ in the $m$-bonacci numeration system using the alphabet $A=\{0,1,2\}$.
\begin{table}[H]
\begin{tabular}{rr}
& $m=2$\\ \hline
	$N_i$ & $p(N_i)$ \\ \hline
	$1$ & $1$ \\
	$3$ & $2$ \\
	$6$ & $4$ \\
	$11$ & $7$ \\
	$19$ & $13$ \\
	$32$ & $24$ \\
	$53$ & $44$ \\
	$87$ & $81$ \\
	$142$ & $149$ \\
	$231$ & $274$ \\
	$375$ & $504$ \\
	$608$ & $927$ \\
	$985$ & $1705$ \\
	$1595$ & $3136$ \\
	$2582$ & $5768$ \\
	$4179$ & $10609$ \\
	$6763$ & $19513$ \\
	$10944$ & $35890$ \\
	$17709$ & $66012$ \\
	$28655$ & $121415$ \\
\end{tabular}
$\quad$
\begin{tabular}{rr}
& $m=3$\\ \hline
	$N_i$ & $p(N_i)$ \\ \hline
	$1$ & $1$ \\
	$3$ & $1$ \\
	$7$ & $2$ \\
	$14$ & $4$ \\
	$27$ & $6$ \\
	$51$ & $9$ \\
	$95$ & $15$ \\
	$176$ & $25$ \\
	$325$ & $40$ \\
	$599$ & $64$ \\
	$1103$ & $104$ \\
	$2030$ & $169$ \\
	$3735$ & $273$ \\
	$6871$ & $441$ \\
	$12639$ & $714$ \\
	$23248$ & $1156$ \\
	$42761$ & $1870$ \\
	$78651$ & $3025$ \\
	$144663$ & $4895$ \\
	$266078$ & $7921$ \\
\end{tabular}
$\quad$
\begin{tabular}{rr}
&    $m=4$\\ \hline
	$N_i$ & $p(N_i)$ \\ \hline
	$1$ & $1$ \\
	$3$ & $1$ \\
	$7$ & $1$ \\
	$15$ & $2$ \\
	$30$ & $4$ \\
	$59$ & $6$ \\
	$115$ & $8$ \\
	$223$ & $11$ \\
	$431$ & $17$ \\
	$832$ & $27$ \\
	$1605$ & $41$ \\
	$3095$ & $60$ \\
	$5967$ & $88$ \\
	$11503$ & $132$ \\
	$22174$ & $200$ \\
	$42743$ & $301$ \\
	$82391$ & $449$ \\
	$158815$ & $669$ \\
	$306127$ & $1001$ \\
	$590080$ & $1502$ \\
\end{tabular}
$\quad$
\begin{tabular}{rr}
&    $m=5$\\ \hline
	$N_i$ & $p(N_i)$ \\ \hline
	$1$ & $1$ \\
	$3$ & $1$ \\
	$7$ & $1$ \\
	$15$ & $1$ \\
	$31$ & $2$ \\
	$62$ & $4$ \\
	$123$ & $6$ \\
	$243$ & $8$ \\
	$479$ & $10$ \\
	$943$ & $13$ \\
	$1855$ & $19$ \\
	$3648$ & $29$ \\
	$7173$ & $43$ \\
	$14103$ & $61$ \\
	$27727$ & $84$ \\
	$54511$ & $116$ \\
	$107167$ & $164$ \\
	$210686$ & $236$ \\
	$414199$ & $340$ \\
	$814295$ & $485$ \\
\end{tabular}
\end{table}

\begin{remark}
  Note the surprising fact in the column of results for the case $m=2$: The number of representations of $N_k=\sum_{j=1}^kF_j=F_{k+2}-2$ is equal to the $k$-th Tribonacci number $T_k$.
  This observation was first made by Vla\v sic~\cite{Vlasic}. This statement is included in Proposition~\ref{prop:recurrence} as the case $m=2$.
\end{remark}




\section{Representations in the $m$-bonacci system over $\{0,1,2\}$}\label{sec:012}


\begin{proposition}\label{prop:recurrence}
	Let $A= \{0,1,2\}$, $k,m\in\N$ with $m\ge 2$ and $k\ge 1$. The number $p(N_k)$ of representations of $N_k$ in the $m$-bonacci numeration system over the alphabet $A$  satisfies the recurrence relation
	\begin{equation}\label{eq:recurrence}
		p_A(N_k)= p_A(N_{k-1})+p_A(N_{k-m})+p_A(N_{k-m-1}) \text{ for } k> m+1
	\end{equation}
	with $p_A(N_k)= 1$ for $k\in\{0,\ldots, m-1\}$, $p_A(N_m)=2$ and $p_A(N_{m+1})=4$.
\end{proposition}

The proof of this result relies on the following lemma.
\begin{lemma}
	Let $k\in \N$. The following inequalities hold:
\begin{equation}\label{eq:N_less_T}
N_k < T_k + T_{k+1}\le  T_{k+2} \text{ for }k\ge 1,
\end{equation}
\begin{equation}\label{eq:2N_less_N}
2N_{k-2} < N_k \text{ for } k \ge 3,
\end{equation}
\begin{equation}\label{eq:N_less_2T}
N_k < 2T_{k+1} \text{ for }k\ge 1.
\end{equation}




\end{lemma}

\begin{proof}
For the first inequality, we proceed by induction. It is easy to check that $N_1< T_1+T_2 \le  T_3$. Let $k\ge 2$ and assume the results hold for $k-1$. We have by definition and induction hypothesis that
$N_{k}= T_k+N_{k-1} < T_k+ T_{k+1} \le  T_{k+2}$.

All the other inequalities follow from the first one.
For the second inequality with $k\ge 3$, we have
$$
N_k = T_k + T_{k-1} + N_{k-2} > N_{k-2} + T_{k-1}+ N_{k-2}> 2N_{k-2}.
$$
For the last inequality, we just note that $T_k<T_{k+1}$ for all $k\ge 1$.
\end{proof}


\begin{proof}[Proof of Proposition~\ref{prop:recurrence}]
First note that \eqref{eq:N_less_T} and~\eqref{eq:2N_less_N} imply that every representation of $N_k$ has length in $\{k-1,k,k+1\}$. So
\begin{equation}\label{eq:lengths}
p(N_k)=p(N_k,k+1)+p(N_k,k)+p(N_k,k-1) \text{ for } k\geq 1.
\end{equation}
Obviously, by definition of $N_k$, $(1^k)$ is one of the representations of $N_k$.
	
We first take care of the initial conditions. For $k\in\{1,\ldots, m-1\}$, the number $N_k=2^k-1$ has a unique representation that is $(1^k)$. For $k=m$, we have $N_m=2^m-1 = T_{m+1}$. Therefore, $N_m$ can be represented only by $(1^m)$ or $(10^m)$. Finally, for $k=m+1$, we can use the $m$-bonacci recurrence to write
$$
N_{m+1} =\sum_{j=1}^{m+1}T_j =  T_{m+2}+ T_1 =2 T_{m+1} = 2\sum_{j=1}^{m}T_j .
$$
Thus the representations of $N_{k+1}$ are four, namely $(1^{m+1})$,  $(10^{m}1)$, $(20^m)$, and $(2^m)$. It is easy to check that these are the only ones.
We can summarize it in Table~\ref{t}.

\begin{table}[!ht]
\begin{center}
   \begin{tabular}{ccccc}
  $k$ & $p(N_k)$ & $p(N_k,k+1)$ & $p(N_k,k)$ & $p(N_k,k-1)$ \\ \midrule
  1 & 1 & 0 & 1 & 0 \\\midrule
  \vdots & \vdots & \vdots & \vdots & \vdots \\\midrule
  $m-1$ & 1 & 0 & 1 & 0 \\\midrule
  $m$ & 2 & 1 & 1 & 0 \\\midrule
  $m+1$ & 4 & 1 & 2 & 1 \\\midrule
\end{tabular}
\end{center}
  \caption{Initial conditions for the sequences $p(N_k)$, $p(N_k,k+1)$, $p(N_k,k)$, and $p(N_k,k-1)$.}\label{t}
\end{table}

For $k\geq m+2$, we will distinguish three cases according to the possible lengths of the representations.

\noindent \textbf{Case 1:} consider the representations $(a_{k+1}\cdots a_1)$ of $N_k$ of length $k+1$ and assume $k\ge m$. In that case, $a_{k+1}\ne 2$ because otherwise $N_k=\val(2a_k\cdots a_1)\ge 2T_{k+1}$, which is in contradiction with~\eqref{eq:N_less_2T}.
So $a_{k+1}=1$ and $\val(a_k\cdots a_1)=N_k-T_{k+1}=N_k-\sum_{j=0}^{m-1}T_{k-j}=N_{k-m}$. This means that $p(N_k,k+1)$ is equal to the number of representations of $N_{k-m}$ of length at most $k$. Since $k-m+1<k$, this number is equal to  $p(N_{k-m})$.
Thus
\begin{equation}\label{eq:rec_k+1}
	p(N_k,k+1)=p(N_{k-m}) \text{ for }k\ge m.
\end{equation}

\noindent\textbf{Case 2:} consider the representations $(a_k\cdots a_1)$ of $N_k$ of length $k$
and assume $k\ge m+1$.
If $a_k=2$, then
$\val(a_{k-1}\cdots a_1)=N_k-2T_k = N_{k-m-1}$. The number of such representations is equal to the number of representations of $N_{k-m-1}$, and since $k-m<k-1$, this is equal to $p(N_{k-m-1})$.
If $a_k=1$, then
$\val(a_{k-1}\cdots a_1)=N_k-T_k = N_{k-1}.$ So the number of such representations is equal to $p(N_{k-1},k-1)+p(N_{k-1},k-2)$.
In conclusion, we get
\begin{align*}
	p(N_k,k) & = p(N_{k-m-1})+p(N_{k-1},k-1)+p(N_{k-1},k-2)\\
	& = p(N_{k-m-1})+p(N_{k-1})-p(N_{k-1},k).
\end{align*}
Since $k\geq m+1$, we can use~\eqref{eq:rec_k+1} to obtain $p(N_{k-1},k) = p(N_{k-m-1})$ and thus
\begin{equation}\label{eq:rec_k}
	p(N_k,k) = p(N_{k-1})\text{ for }k\ge m+1.
\end{equation}


\noindent \textbf{Case 3:} consider the representations $(a_{k-1}\cdots a_1)$ of $N_k$ of length $k-1$
and assume $k\ge m+2$.
We have $a_{k-1}=a_{k-2}=\cdots =a_{k-m+1}= 2$.
Indeed, let $\ell \in\{1,\ldots,m-1\}$. If the prefix of length $\ell-1$ of the representation is a concatenation of $2$'s (i.e., $a_{k-1}=\cdots = a_{k+1-\ell}= 2$), then $a_{k-\ell}=2$.
Otherwise, $a_{k-\ell}$ is equal to $1$ or $0$ and
\begin{align*}
	2 N_{k-\ell-1}&\ge \val(a_{k-\ell-1}\cdots a_1) =  N_k - 2 \sum_{j=1}^{\ell-1} T_{k-j} - a_{k-\ell}T_{k-\ell} \ge\\
	& \ge N_k - 2 \sum_{j=1}^{\ell-1} T_{k-j} - T_{k-\ell} = N_{k-\ell-1} + T_k - \sum_{j=1}^{\ell-1} T_{k-j} = \\
	& = N_{k-\ell-1}  +  \sum_{j=k-m}^{k-\ell} T_{j} > 2N_{k-\ell-1}   %\tag{by Eq.~\eqref{eq:N_less_T}}	
\end{align*}
which is a contradiction. Note that for the last inequality we have used \eqref{eq:N_less_T} which is justified since $k-\ell-1 \geq k-m \geq 2$.

So the representation of $N_k$ is of the form $(a_{k-1}\cdots a_{1})= (2^{m-1}a_{k-m}\cdots a_{1})$ and
$$
\val(a_{k-m}\cdots a_{1})= N_k-2\sum_{j=k-m+1}^{k-1}T_j = N_{k-m}+T_{k} - \sum_{j=1}^{m-1}T_{k-j} = N_{k-m} + T_{k-m}.
$$
If $a_{k-m}=2$, then $\val(a_{k-m-1}\cdots a_1)=N_{k-m-1}$. The number of representations of $N_k$ of this form is $p(N_{k-m-1},k-m-1)+p(N_{k-m-1},k-m-2)$.
If $a_{k-m}=1$, then $\val(a_{k-m-1}\cdots a_1)=N_{k-m}$, and the number of corresponding representations is $p(N_{k-m},k-m-1)$.
Finally, $a_{k-m}=0$ is not possible because it would imply
$$
2 N_{k-m-1}\ge \val(a_{k-m-1}\cdots a_1)=N_{k-m}+T_{k-m}= N_{k-m-1}+2T_{k-m}
$$
which is in contradiction with \eqref{eq:N_less_2T}. Here we use that $k-m-1\geq 1$ from the assumption.
Putting everything together, we obtain
\begin{equation}\label{eq:aux_k-1}
\begin{aligned}
	p(N_k,k\!-\!1)= &\ p(N_{k-m-1},k\!-\!m\!-\!1)+p(N_{k-m-1},k\!-\!m\!-\!2)+p(N_{k-m},k\!-\!m\!-\!1)\\
	=&\ p(N_{k-m-1}) - p(N_{k-m-1},k\!-\!m)+ p(N_{k-m},k\!-\!m\!-\!1).
\end{aligned}
\end{equation}


Now suppose that $k\in\{m+2,\ldots, 2m\}$. Then $1\leq k-m-1\leq m-1$  and from the initial conditions in Table~\ref{t} we have
$p(N_{k-m-1},k-m)=0$ and $p(N_{k-m},k-m-1)=0$. It follows from~\eqref{eq:aux_k-1} that $p(N_k,k-1)=p(N_{k-m-1})$.
With \eqref{eq:rec_k+1} and \eqref{eq:rec_k}, it implies that
\begin{equation}\label{eq:rec_basis}
p(N_k)=p(N_{k-1})+p(N_{k-m})+p(N_{k-m-1})\text{ for } k\in\{m+2,\ldots, 2m\}.
\end{equation}

Now assume that $k> 2m$. Using \eqref{eq:rec_k+1} and \eqref{eq:rec_k} we deduce from~\eqref{eq:aux_k-1} that
\begin{align*}
p(N_k,k-1)= &\ p(N_{k-m-1}) - p(N_{k-m-1},k-m)+\\
&\ + p(N_{k-m})- p(N_{k-m},k-m+1)-p(N_{k-m},k-m)=\\
= &\ p(N_{k-m-1}) - p(N_{k-2m-1})
+ p(N_{k-m})- p(N_{k-2m}) - p(N_{k-m-1})\\
= &\  p(N_{k-m})- p(N_{k-2m}) - p(N_{k-2m-1}).
\end{align*}
Therefore, for $k>2m$, we have
$$
p(N_k)=p(N_{k-1})+p(N_{k-m})+ p(N_{k-m})- p(N_{k-2m}) - p(N_{k-2m-1}).
$$

To conclude the argument, an easy induction on $k$ shows the claim
$$
p(N_k)=p(N_{k-1})+p(N_{k-m})+p(N_{k-m-1})\text{ for }  k> m+1,
$$
since the base cases are treated in \eqref{eq:rec_basis}.
\end{proof}


\section{Representations of zero in the signed $m$-bonacci system}\label{sec:signed}



We are interested in the representations of $0$ over the balanced alphabet $B=\{-1,0,1\}$. We let ${\mathcal Z}$ denote the set of such representations. For a fixed $k\geq 1$, we further let ${\mathcal Z}_k$ denote the set of representations of 0 of length at most $k$. Let us describe the number of such representations, i.e.,
$r(k)=\#{\mathcal Z}_k$.
In order to determine $r(k)$ for $k\geq 2m+1$, let us present the correspondence between the $m$-bonacci numeration systems with the alphabet of digits $A=\{0,1,2\}$ and $B=\{-1,0,1\}$ and then derive the recurrence for the sequence $(r(k))_{k\geq 1}$.


\begin{proposition}
	Let $A=\{0,1,2\}$ and $B=\{-1,0,1\}$, $k,m\in\N$ with $m\ge 2$ and $k\ge 1$.
	The number $r(k)$ of representations of $0$ of length at most $k$ in the $m$-bonacci numeration system over the alphabet $B$ is given by
	$$
    r(k)=\sum_{j=0}^k p_B(0,j) = p_A(N_{k})- p_A(N_{k-m}) = p_A(N_{k-1})+ p_A(N_{k-m-1})\text{ for }k\ge m+1
    $$
	and $r(k)=p_A(N_k)=1$ for $k\in\{0,\ldots, m\}$.
\end{proposition}

\begin{proof}
Any representation $(b_k\cdots b_1)$ of $0$ over $B=\{-1,0,1\}$ (with possible leading zeros) is in one-to-one correspondence with
a representation $(a_k\cdots a_1)$ of $N_{k}$ of length at most $k$ over the alphabet $A=\{0,1,2\}$, setting $a_j=b_j+1$ for $j=1,\dots,k$.
By~\eqref{eq:lengths}, we have $r(k)= p_A(N_k,k)+p_A(N_k,k-1)=p_A(N_k)-p_A(N_k,k+1)$.
Using~\eqref{eq:rec_k+1}, we have $r(k)=p_A(N_k)-p_A(N_{k-m})$. The last equality in the statement of the proposition follows from the recurrence on $p_A(N_k)$.
\end{proof}


\begin{corollary}\label{coro:r}
  The number $r(k)$ of representations of $0$ of length at most $k$ in the $m$-bonacci numeration system over the alphabet $B=\{-1,0,1\}$ satisfies
  \begin{equation}\label{eq:rek-rk}
  r(k)=r(k-1)+r(k-m)+r(k-m-1) \text{ for }k\ge m+1
  \end{equation}
    and $r(k)=1$ for $k\in\{0,\ldots, m\}$.
\end{corollary}


\begin{remark}\label{rem:r}
 For further use, let us determine a set of initial values of the sequence $(r(k))_{k\geq 0}$. Obviously, the only representation of zero of length $k\leq m$ is $(0^k)$, which is in accordance with the initial conditions of the recurrence~\eqref{eq:rek-rk}.
 If $k=m+1$, we have, besides the representation $(0^{m+1})$ also $(1\bar{1}^m)$ and $(\bar{1}1^m)$, where we use $\bar{1}$ for $-1$ for lucidity of notation.
 We have $r(m+1)=3=r(m)+r(1)+r(0)$. For $m+2\leq k\leq 2m$ we have from~\eqref{eq:rek-rk} that
 $r(k)=r(k-1)+2$, i.e.,\ $r(m+j)=2j+1$ for $j=1,\dots,m$.
\end{remark}


\begin{figure}
\centering
	\begin{tikzpicture}[auto, initial text=, >=latex]
	\node[state, accepting, initial,initial where=below] (v0) at (0, 0) {$i$};
	\node[state] (v1) at (2, 0) {$v_1$};
	\node[state] (v2) at (-2,0) {$u_1$};
	\node[state] (v3) at (4, 0) {$v_2$};
	\node[state] (v5) at (-4, 0) {$u_2$};
	\path[->] (v0) edge[loop above] node {$0$} ();
	\path[->] (v0) edge node[above] {$1$} (v1);
	\path[->] (v0) edge node[above] {$-1$} (v2);
	\path[->] (v1) edge node[above] {$-1$} (v3);
	\path[->] (v2) edge node[above] {$1$} (v5);
	\path[->] (v3) edge[bend right=30]  node[above] {$-1$} (v0);
	\path[->] (v3) edge[bend left=30] node[below] {$0$} (v1);
	\path[->] (v5) edge[bend left=30]  node[above] {$1$} (v0);
	\path[->] (v5) edge[bend right=30] node[below] {$0$} (v2);
	\end{tikzpicture}
	\caption{Automaton accepting representations of $0$ over the alphabet $\{-1,0,1\}$ in the Fibonacci numeration system.}
	\label{fig:automata-Fibonacci}
\end{figure}

An automaton accepting the representations of zero in the signed Fibonacci numeration system ($m=2$, digits $-1,0,1$) was described by Frougny~\cite[Chap.~7]{lothaire2}; see Figure~\ref{fig:automata-Fibonacci}.
The number of representations of $0$ of length at most $k$ is exactly the number of representations with $k$ symbols where we allow leading zeros.
Hence it corresponds to the number of length-$k$ accepting paths in the automaton.
	

Here, we present an automaton recognizing representations of zero in the signed $m$-bonacci numeration system for $m\geq 2$.

\begin{proposition}\label{prop:automat}
  Let $\mathcal A=(Q,B,\delta,I,T)$ be a deterministic finite automaton with the set of states $Q=\{i,u_1,\dots,u_m,v_1,\dots,v_m\}$,
  alphabet $B=\{-1,0,1\}$, the set of initial and terminal states $I=T=\{i\}$. Define the transition function $\delta: Q\times\{-1,0,1\}\to Q$,
$$
\begin{aligned}
(i,0) &\mapsto i,\quad (i,-1)\mapsto u_1,\quad (i,1)\mapsto v_1\\
(u_j,1)&\mapsto u_{j+1},\quad (u_m,0)\mapsto u_1,\quad (u_m,1) \mapsto i\\
(v_j,-1)&\mapsto v_{j+1},\quad (v_m,0)\mapsto v_1,\quad (v_m,-1) \mapsto i,
\end{aligned}
$$
see Figure~\ref{fig:automata-mbonacci}. Then $\mathcal A$ recognizes precisely the representations of 0
in the $m$-bonacci numeration system over the alphabet $B$.
\end{proposition}


\begin{figure}
\centering
\resizebox{\textwidth}{!}{%
	\begin{tikzpicture}[auto, initial text=, >=latex]
	\node[state, accepting, initial,initial where=below] (v0) at (0, 0) {$i$};
	\node[state] (v1) at (2, 0) {$v_1$};
	\node[state] (v3) at (4, 0) {$v_2$};
	\node[state] (m) at (5.5, 0) {$v_{m-1}$};
	\node[state] (v4) at (7.5, 0) {$v_m$};
	\node[state] (v2) at (-2,0) {$u_1$};
	\node[state] (v5) at (-4, 0) {$u_2$};
	\node[state] (n) at (-5.5, 0) {$u_{m-1}$};
	\node[state] (v6) at (-7.5, 0) {$u_m$};
	\path[->] (v0) edge[loop above] node {$0$} ();
	\path[->] (v0) edge node[above] {$1$} (v1);
	\path[->] (v0) edge node[above] {$-1$} (v2);
	\path[->] (v1) edge node[above] {$-1$} (v3);
	\path[->] (m) edge node[above] {$-1$} (v4);
	\path[->] (v2) edge node[above] {$1$} (v5);
	\path[->] (n) edge node[above] {$1$} (v6);
	\path[->] (v4) edge[bend right=30]  node[above] {$-1$} (v0);
	\path[->] (v4) edge[bend left=30] node[below] {$0$} (v1);
	\path[->] (v6) edge[bend left=30]  node[above] {$1$} (v0);
	\path[->] (v6) edge[bend right=30] node[below] {$0$} (v2);
	\path[dashed] (v3) edge (m);		
	\path[dashed] (v5) edge (n);
	\end{tikzpicture}
}
\caption{Automata accepting representations of $0$ over the alphabet $\{-1,0,1\}$ in the $m$-bonacci numeration system with $m\ge 2$.}
\label{fig:automata-mbonacci}
\end{figure}

In order to justify that the accepting paths correspond precisely to the representations of 0, we study the adjacency matrix $\mathbb A$ of the automaton ${\mathcal A}$. In an adjacency matrix of the automaton, the element ${\mathbb A}_{j,k}$ is defined as 1 if there is an edge from the state $j$ to the state $k$, and 0 otherwise. Fixing the ordering of states of ${\mathcal A}$ from $1$ to $2m+1$ as $\{i,u_1,\dots,u_m,v_1,\dots,v_m\}$, we have
$$
{\mathbb A}=
 \begin{pmatrix}
   1 & v^T & v^T \\
   u & C & O \\
   u & O & C
 \end{pmatrix},
$$
where $v^T=(1 0 \dots 0)\in \Z^m$, $u^T=(0 \dots 0 1)\in\Z^m$, $O\in\Z^{m\times m}$ is the zero matrix and
$$
C = \begin{pmatrix}
      0 & 1 & 0  & \cdots  & 0 \\
      0 & 0 & 1 &          & \vdots \\
      \vdots &  & \ddots &  & 0 \\
      0 &  &  & 0 & 1 \\
      1 & 0 & \cdots & 0 & 0
    \end{pmatrix}\in\Z^{m\times m}
$$
is the companion matrix of the polynomial $x^m-1$.

\begin{lemma}\label{l:charpolA}
The characteristic polynomial of ${\mathbb A}$ is equal to
$$
f(x)=(x^m-1)(x^{m+1}-x^m-x-1)=x^{2m+1}-x^{2m}-2x^{m+1}+x+1.
$$
\end{lemma}

\begin{proof}
  For the computation of the characteristic polynomial $f(x)=-\det({\mathbb A}-xI)$, we use the following statement about determinants of block matrices~\cite{Silvester}.

  {\it
  Let $E,F,G,H$ be complex matrices of dimensions $p\times p$, $p\times q$, $q\times p$, $q\times q$, with $H$ invertible.
  Then for the determinant of
  $\begin{pmatrix}
   E & F \\
   G & H
   \end{pmatrix}$
  we have
  \begin{equation}\label{eq:odeterminantech}
    \det\begin{pmatrix}
   E & F \\
   G & H
 \end{pmatrix} =
 \det(E-FH^{-1}G)\det(H)\,.
  \end{equation}
  }

\noindent
We use the statement~\eqref{eq:odeterminantech} in two steps. First set
  $$
  E=\begin{pmatrix}
      1-x & v^T \\
      u & H
    \end{pmatrix},\
  F=\begin{pmatrix}
      v^T \\
      O
    \end{pmatrix},\
  G=\begin{pmatrix}
      u & O
    \end{pmatrix},
  $$
  $$
  H=C-xI=\begin{pmatrix}
      -x & 1 & 0  & \cdots  & 0 \\
      0 & -x & 1 &          & \vdots \\
      \vdots &  & \ddots &  & 0 \\
      0 &  &  & -x & 1 \\
      1 & 0 & \cdots & 0 & -x
    \end{pmatrix}.
  $$
Note that $\det(H)=(-1)^m(x^m-1)$. Also note that
the product $FH^{-1}G=(h_{j,k})\in \Z^{(m+1)\times(m+1)}$ is a matrix that is null everywhere except
for $c_{1,1}=h_{1,m}$ with $(h_{j,k})=H^{-1}=\det(H)^{-1}{\rm adj}(H)$ where ${\rm adj}(H)$ is the adjugate matrix.
Since the adjugate matrix is computed as the transpose of the cofactor matrix, we have
$$
c_{1,1}=h_{1,m}=\frac{1}{(-1)^m(x^m-1)} (-1)^{m+1}\det\begin{pmatrix}
                                                 1 & 0 & \dots & 0 \\
                                                 -x & 1 & \ddots & \vdots \\
                                                 \vdots & \ddots & \ddots & 0 \\
                                                 0 & \dots & -x & 1
                                               \end{pmatrix} = \frac{-1}{x^m-1}\,.
$$
At this stage, we have
$$
\det({\mathbb A}-xI) = \det(E-FH^{-1}G)\det(H) =
\det(H)\det\begin{pmatrix}
        1-x - c_{1,1} & v^T \\
        u & H
   \end{pmatrix}.
$$
We use~\eqref{eq:odeterminantech} again, with redefined blocks $E,F,G$, $E=(1-x-c_{1,1})$, namely $F= v^T$, $G= u$.
Realizing that $FH^{-1}G=(c_{1,1})$, we derive
$$
\begin{aligned}
-f(x) &=\det({\mathbb A}-xI) =
\det(H)^2 (1-x-2c_{1,1}) =\\
&= (x^m-1)^2\big(1-x-\frac{-2}{x^m-1}\big)=-(x^m-1)(x^{m+1}-x^m-x-1),
\end{aligned}
$$
which proves the lemma.
\end{proof}

Let us now demonstrate that the automaton presented in Figure~\ref{fig:automata-mbonacci} recognizes precisely the representations of 0 in the $m$-bonacci system over the alphabet $B=\{-1,0,1\}$.

\begin{proof}[Proof of Proposition~\ref{prop:automat}]
  The language accepted by the automaton ${\mathcal A}$ depicted in Figure~\ref{fig:automata-mbonacci} can be described by the regular expression
  $$
  0^*\big(1(\bar{1}^{m-1}0)^*\bar{1}^m+\bar{1}(1^{m-1}0)^*1^m\big)^*0^*
  $$
It can be directly checked with the use of the $m$-bonacci recurrence that every word of the above form corresponds to
a representation of $0$ in the sense of Definition~\ref{d:rep}. For every fixed $k$ we thus have
${\mathcal L}_k(\mathcal A) \subseteq {\mathcal Z}_k$.
In order to check the opposite inclusion, it suffices to show that
$$
\#{\mathcal L}_k(\mathcal A) = \#{\mathcal Z}_k = r(k).
$$

Consider the adjacency matrix  ${\mathbb A}$ of the automaton ${\mathcal A}$.
An accepting path in the automaton is a path both starting and ending in the initial state $i$. The number of such paths of length $k$, say $s(k)$, is equal to $({\mathbb A}^k)_{11}$. We thus have $s(k):=\#{\mathcal L}_k(\mathcal A)=({\mathbb A}^k)_{11}$. We will show that $s(k)=r(k)$ by verifying that both sequences satisfy the same linear recurrence of order $2m+1$ with the same initial conditions $s(j)=r(j)$ for $j=0,\dots,2m$.

The characteristic polynomial $f$ of the matrix ${\mathbb A}$ is computed in Lemma~\ref{l:charpolA}. By the Cayley-Hamilton theorem, we have
$$
f(\mathbb A)={\mathbb A}^{2m+1}-{\mathbb A}^{2m}-2{\mathbb A}^{m+1}+{\mathbb A}+I = O,
$$
where $I,O\in\Z^{(2m+1)\times(2m+1)}$ are the identity and zero matrix, respectively. Multiplying the above by ${\mathbb A}^k$ for $k\geq 0$,
and considering the sequence $s(k)=({\mathbb A}^k)_{11}$, we have
$$
s(k+2m+1)-s(k+2m)-2s(k+m+1)+s(k+1)+s(k)=0 \quad\text{ for } k\geq 0.
$$
Let us verify that the sequence $r(k)$ satisfies the same recurrence. From Corollary~\ref{coro:r} we have for $k\geq 0$ that
$$
\begin{aligned}
r(k+m+1)-r(k+m)-r(k+1)-r(k)&=0,\\
r(k+2m+1)-r(k+2m)-r(k+m+1)-r(k+m)&=0.
\end{aligned}
$$
Subtracting the two, we obtain
$$
r(k+2m+1)-r(k+2m)-2r(k+m+1)+r(k+1)+r(k)=0 \quad\text{ for } k\geq 0,
$$
as desired.
The initial values $r(0),\dots,r(2m)$ are determined in Remark~\ref{rem:r} as
$r(j)=1$ for $0\leq j\leq m$ and $r(j+m)=2j+1$ for $0\leq j\leq m$.
It remains to determine $s(0),\dots, s(2m)$. For that, we check directly the automaton ${\mathcal A}$. We see that $s(k)=r(k)$ for $0\leq k\leq 2m$ which implies that $s(k)=r(k)$ for every $k\geq 0$.
\end{proof}







\section{Characteristic polynomial}\label{sec:polynom}

When studying growth of the sequences $p_A(N_k)$, $r(k)$ counting representations
in the $m$-bonacci system, one is interested in the zeros of the characteristic polynomial of the corresponding recurrence relation. From Proposition~\ref{prop:recurrence} and Corollary~\ref{coro:r} we see that both $p_A(N_k)$ and $r(k)$ satisfy the same recurrence with characteristic polynomial
$f(x)=x^{m+1}-x^m-x-1$.
Quadrinomials whose coefficients take values only in $\{\pm1\}$ have been considered by several authors, e.g., Ljunggren~\cite{Ljunggren}, Finch and Jones~\cite{FiJo}, or  Mills~\cite{Mills}. It is not difficult to derive the following result.

\begin{proposition}
  Let $m\geq 2$. Then $\chi(x)=x^{m+1}-x^m-x-1$ is irreducible over $\Q$ if and only if $m\not\equiv 3\pmod 4$. If $m=4k+3$ for $k\geq 1$, then we have
  $\chi(x)=(x^2+1)\psi(x)$ where for $k=1$ we have $\psi(x)=(x^3-x^2+1)(x^3-x-1)$, and for $k\geq 2$, $\psi\in\Z[x]$ is irreducible over $\Q$.
  \end{proposition}

\begin{proof}
  It follows from Theorem~2 in the paper by Finch and Jones~\cite{FiJo} that the quadrinomial $\chi(x)=x^{m+1}-x^m-x-1$ is irreducible over $\Q$ if and only if $m\not\equiv 3\pmod 4$.
  The factorization of the polynomial $\chi$ in the reducible case can be deduced from the results of Ljunggren~\cite{Ljunggren} and Mills~\cite{Mills}.
\end{proof}

\begin{figure}
  \centering
  \includegraphics[width=0.32\textwidth]{Polynom4.png}\
  \includegraphics[width=0.32\textwidth]{Polynom8.png}\
  \includegraphics[width=0.32\textwidth]{Polynom33.png}
  \caption{Zeros of the polynomial $\chi(x)=x^{m+1}-x^m-x-1$ for $m=3$, $m=7$ and $m=32$. The zeros $\lambda$ with $\Re\lambda>0$ are of modulus greater than $1$, the zeros with negative real part lie inside the unit disk.}\label{f:roots}
\end{figure}



\section{Acknowledgments}

This work was supported by the project CZ.02.1.01/0.0/0.0/16\_019/0000778
from European Regional Development Fund.

\begin{thebibliography}{10}

\bibitem{Avizienis}
A.~Avi\v{z}ienis, Signed-digit number representations for fast parallel
  arithmetic, {\em IRE Trans.} {\bf EC-10} (1961), 389--400.

\bibitem{Berstel01}
J.~Berstel, An exercise on {F}ibonacci representations, {\em Theor. Inform.
  Appl.} {\bf 35} (2001), 491--498.

\bibitem{ChowRob}
C.~Y. Chow and J.~E. Robertson, Logical design of a redundant binary adder, In
  {\em 1978 IEEE 4th Symposium on Computer Arithmetic (ARITH)}, pp.~109--115.
  Institute of Electrical and Electronics Engineers, 1978.

\bibitem{Edson}
M.~Edson, Calculating the numbers of representations and the {G}arsia entropy
  in linear numeration systems, {\em Monatsh. Math.} {\bf 169} (2013),
  161--185.

\bibitem{EdZa04}
M.~Edson and L.~Q. Zamboni, On representations of positive integers in the
  {F}ibonacci base, {\em Theoret. Comput. Sci.} {\bf 326} (2004), 241--260.

\bibitem{EdZa06}
M.~Edson and L.~Q. Zamboni, On the number of partitions of an integer in the
  {$m$}-bonacci base, {\em Ann. Inst. Fourier (Grenoble)} {\bf 56} (2006),
  2271--2283.

\bibitem{FiJo}
C.~Finch and L.~Jones, On the irreducibility of {$\{-1,0,1\}$}-quadrinomials,
  {\em Integers} {\bf 6} (2006), Paper \#A16.

\bibitem{Frougny92fr}
C.~Frougny, Syst\`emes de num\'{e}ration lin\'{e}aires et
  {$\theta$}-repr\'{e}sentations, {\em Theoret. Comput. Sci.} {\bf 94} (1992),
  223--236.

\bibitem{FrPeSv}
C.~Frougny, E.~Pelantov\'{a}, and M.~Svobodov\'{a}, Parallel addition in
  non-standard numeration systems, {\em Theoret. Comput. Sci.} {\bf 412}
  (2011), 5714--5727.

\bibitem{FroSt}
C.~Frougny and W.~Steiner, Minimal weight expansions in {P}isot bases, {\em J.
  Math. Cryptol.} {\bf 2} (2008), 365--392.

\bibitem{GrHe06}
P.~J. Grabner and C.~Heuberger, On the number of optimal base 2 representations
  of integers, {\em Des. Codes Cryptogr.} {\bf 40} (2006), 25--39.

\bibitem{GrKiTi}
P.~J. Grabner, P.~Kirschenhofer, and R.~F. Tichy, Combinatorial and
  arithmetical properties of linear numeration systems, {\em Combinatorica}
  {\bf 22} (2002), 245--267.

\bibitem{Heuberger}
C.~Heuberger, Minimal expansions in redundant number systems and shortest paths
  in graphs, {\em Computing} {\bf 63} (1999), 341--349.

\bibitem{KoMaPe05}
P.~Koc\'{a}bov\'{a}, Z.~Mas\'{a}kov\'{a}, and E.~Pelantov\'{a}, Integers with a
  maximal number of {F}ibonacci representations, {\em Theor. Inform. Appl.}
  {\bf 39} (2005), 343--359.

\bibitem{KoMaPe07}
P.~Koc\'{a}bov\'{a}, Z.~Mas\'{a}kov\'{a}, and E.~Pelantov\'{a}, Ambiguity in
  the {$m$}-bonacci numeration system, {\em Discrete Math. Theor. Comput. Sci.}
  {\bf 9} (2007), 109--123.

\bibitem{Lekkerkerker}
C.~G. Lekkerkerker, Representation of natural numbers as a sum of {F}ibonacci
  numbers, {\em Simon Stevin} {\bf 29} (1952), 190--195.

\bibitem{Ljunggren}
W.~Ljunggren, On the irreducibility of certain trinomials and quadrinomials,
  {\em Math. Scand.} {\bf 8} (1960), 65--70.

\bibitem{lothaire2}
M.~Lothaire, {\em Algebraic Combinatorics on Words}, Vol.~90 of {\em
  Encyclopedia of Mathematics and its Applications}, Cambridge University
  Press, 2002.

\bibitem{Mills}
W.~H. Mills, The factorization of certain quadrinomials, {\em Math. Scand.}
  {\bf 57} (1985), 44--50.

\bibitem{PeTi89}
A.~Peth\H{o} and R.~F. Tichy, On digit expansions with respect to linear
  recurrences, {\em J. Number Theory} {\bf 33} (1989), 243--256.

\bibitem{Silvester}
J.~Silvester, Determinants of block matrices, {\em Math. Gaz.} {\bf 84} (2000),
  460--467.

\bibitem{Stock}
P.~K. Stockmeyer, A smooth tight upper bound for the {F}ibonacci representation
  function {$R(N)$}, {\em Fibonacci Quart.} {\bf 46/47} (2008/09), 103--106.

\bibitem{Vlasic}
O.~Vla{\v s}ic, {\em Redundance in numeration systems}, Bachelor's
  project, Czech Technical University in Prague, 2016.  In Czech.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 11A67; Secondary 11B39.

\noindent \emph{Keywords: } linear numeration system, $m$-bonacci number.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 6 2021;
revised version received  June 2 2021; June 4 2021.
Published in {\it Journal of Integer Sequences},
June 4 2021.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in

\end{document}
