Puyuan Peng1, Shang-Wen Li2, Okko Räsänen3, Abdelrahman Mohamed4, David
Harwath1

# Syllable Discovery and Cross-Lingual Generalization in
a Visually Grounded, Self-Supervised Speech Model

###### Abstract

In this paper, we show that representations capturing syllabic units emerge
when training a self-supervised speech model with a visually-grounded training
objective. We demonstrate that a nearly identical model architecture (HuBERT)
trained with a masked language modeling loss does not exhibit this same
ability, suggesting that the visual grounding objective is responsible for the
emergence of this phenomenon. We propose the use of a minimum cut algorithm to
automatically predict syllable boundaries in speech, followed by a 2-stage
clustering method to group identical syllables together. We show that our
model not only outperforms a state-of-the-art syllabic segmentation method on
the language it was trained on (English), but also generalizes in a zero-shot
fashion to Estonian. Finally, we show that the same model is capable of zero-
shot generalization for a word segmentation task on 4 other languages from the
Zerospeech Challenge, in some cases beating the previous state-of-the-
art.111Code & Model: https://github.com/jasonppy/syllable-discovery.

Index Terms: visually-grounded speech, speech segmentation, self-supervised
speech processing

##  1 Introduction

Traditionally, automatic speech recognition, speech synthesis, and spoken
language understanding tasks have relied on supervised learning and the
assumption that ground-truth text transcriptions of the training speech are
available. Such transcriptions are costly to collect and represent a major
hurdle in developing speech recognition and related technologies that can
serve the thousands of languages around the world.

Recently the speech community has made tremendous progress developing self-
supervised models that can learn powerful representations of the speech signal
by being pre-trained on untranscribed speech data. After pre-training the
models can be fine-tuned on a small amount of transcribed data to achieve
impressive performance on a variety of tasks [1, 2, 3, 4, 5]. Furthermore, the
representations learned by these models can be clustered into discrete speech
units that have been shown to be strongly correlated with words and phones [6,
7]. These units can be used to tokenize speech into a pseudo-text sequence,
which can be used as a drop-in replacement for a text transcription in a wide
variety of downstream tasks, giving rise to a new genre of ``textless'' speech
processing research [8, 9, 10, 11].

Because of the emergent nature of these units, it is not yet understood how to
control what type of linguistic structure (e.g. phones, syllables, words) they
will capture. It has been shown that the representations of self-supervised
speech models tend to correlate with lower-level structure such as phones at
lower model layers, and higher-level structure such as words at higher model
layers [6, 12]. However, it has also been demonstrated that the model's
training objective strongly influences the nature of these representations.
Training the model to perform cross-modal grounding of speech to contextually-
relevant visual images has been shown to dramatically increase the model's
word learning capability over a masked language modeling objective, even when
the model architecture is held nearly constant [7].

In this paper, we build on [7] and demonstrate that multimodal self-
supervision simultaneously results in the emergence of word-like and syllable-
like representations within the same model. While [7] showed that word-like
units are encoded by the Transformer's attention heads, we show that syllabic
structure emerges within the embeddings of the token sequence itself. We
propose the use of a minimum cut segmentation algorithm to derive syllable
boundaries from these features, outperforming a state-of-the-art method for
unsupervised syllabic segmentation. We then show that these segments can be
clustered across a speech corpus to perform syllable discovery, enabling
tokenization of the speech signal at the level of syllable-like units.
Finally, we also show surprising results where our model trained only on
English speech is able to perform zero-shot segmentation of syllables on
another language (Estonian) and words in multiple non-English languages, in
several cases outperforming the state-of-the-art models on the Zerospeech
challenge [13].

##  2 Related Work

Besides the aforementioned work on self-supervised and textless speech
processing, our work is also related to spoken term discovery and visually
grounded speech processing.

Spoken term discovery - inferring the temporal boundary and identity of words
and short phrases from untranscribed speech audio data - has been an important
research direction in Zero-resource speech processing [13]. The earliest work
that tackles spoken term discovery date back to at least the segmental dynamic
programming algorithm proposed by Park and Glass [14]. Since then, numerous
other approaches have been proposed. [15, 16] developed Bayesian models for
hierarchical phoneme and word discovery. Based on the fact that syllables are
organized around particularly sonorous speech sounds, [17] developed sonority
fluctuation-based method for syllabic segmentation. Other works model word
directly either via an iterative segmentating-clustering approach [18], or
reinforcement learning [19]. Self-supervised learning has also been considered
for end-to-end phoneme and word segmentation [20, 21]. Mostly recently,
Algayres et al. [22] identified the key issues in applying text-based models
for speech segmentation, and proposed the DP-Parse algorithm which uses
instance lexicon to mitigate clustering error. Herman [23] applied vector
quantization for phoneme-like unit discovery, and then ran a dynamic
programming algorithm on the discovered units for word segmentation.

Visually grounded speech (VGS) processing [24] generalizes the idea of self-
supervised learning to multimodal (visual) data and learns speech
representations by associating speech audio with contextually-relevant visual
input. VGS usually leverages image-speech [25, 26] or video-speech [27, 28]
paired data. In practice, besides speech-image retrieval and alignment [29,
30, 31, 32, 33, 34], VGS models has also be shown to achieves competitive
performance keyword spotting [35], query-by-example research [36], and varies
tasks in the SUPERB benchmark [37, 38]. The study of linguistic information
learned in VGS models has been attracting increasing attention. In particular,
researchers has measured the phonetic, syllabic, and lexical information in
VGS models [39, 40, 6, 41, 42, 7, 43]. In addition to [7] which we build our
work on, [43] is the most relevant to ours where they studied the emergence of
phonetic, syllabic, and lexical information in different layers of CNN-based
VGS models. Our work is different from their in that none of the modules of
our model receives textual supervision, while their image encoder is pre-
trained on Imagenet classification [44]. In addition, we show the emergence of
hierarchical linguistic information in the non-hierarchical Transformer model,
while they use hierarchical CNN models.

##  3 Technical Approach

VG-HuBERT [7] is a self-supervised dual-encoder model trained using a
contrastive loss to match speech waveforms with the images they describe.
Although VG-HuBERT is not trained with any textual supervision, the model has
been shown to exhibit strong word discovery capabilities [7]. Specifically,
its CLS token places concentrated chunks of attention weight on word segments
in input utterances (see lower left subfigure of figure 1 for an example). Our
motivating hypothesis is that VG-HuBERT's word discovery ability is predicated
on its ability to also discover sub-word units at earlier layers. To probe
this we first extract a sequence of frame embeddings from some layer of the
model given an input waveform, $\mathbf{C}\in\mathbb{R}^{T\times D}$, ($T$ is
number of speech frames, $D$ is the feature dimension). Next, we then
calculate the feature self-similarity matrix as
$\text{featSSM}\mathrel{\mathop{\mathchar
58\relax}}=\mathbf{C}\mathbf{C}^{\intercal}$. We normalize featSSM by
subtracting smallest element of the matrix from all elements to insure that
all frame-pair similarity scores are non-negative. Figure 1 shows an example
of featSSM, where green color denotes high similarity and blue denotes low
similarity. We see a clear block diagonal structure in VG-HuBERT's featSSM,
where each block corresponds to a syllable. In HuBERT's featSSM, however, the
block structure hardly exists. Based on the different patterns we see between
the feature self-similarity matrix and the CLS attention, we hypothesize that
visually grounded training leads to the emergence of syllable identity being
encoded in VG-HuBERT's features, and the CLS token attending to these features
to infer the presence of words. To quantitatively study the syllable discovery
phenomenon, we adopt the normalized minimum cut algorithm [45, 46, 47] to
automatically segment the blocks in featSSM, and use the block boundaries to
predict syllable boundaries.

A min-cut segmentation algorithm for featSSM. We define a fully-connected,
undirected graph $G(V,E)$ for every speech utterance. Set $V$ consists of all
speech frames as nodes; Set $E$ consists of edges, where the edge weight
$w(u,v)$ is defined as the similarity score corresponding to nodes $u$ and
$v$. Segmenting the blocks in featSSM means partitioning the corresponding
graph $G(V,E)$ into disjoint sets $A_{1},A_{2},\cdots,A_{k}$ such that
similarity among nodes (i.e. frames) within each set are maximized, and while
minimizing the similarities of nodes between sets. To achieve this, [45]
proposed the following objective:

$\text{Ncut}_{k}(V)=\frac{cut(A_{1},V-A_{1})}{vol(A_{1})}+\cdots+\frac{cut(A_{k},V-A_{k})}{vol(A_{k})}\vspace{-1mm}$

where $cut(A,B)\mathrel{\mathop{\mathchar 58\relax}}=\sum_{u\in A,v\in
B}w(u,v)$, and $vol(A)\mathrel{\mathop{\mathchar 58\relax}}=\sum_{u\in A,v\in
V}w(u,v)$. For sequential data, the above minimization problem can be solved
using a dynamic programming algorithm [46] in $O(KN^{2})$ time. Here $K$ is
the number of partitions (estimated number of syllables in the utterance in
our case), and $N$ is the number of nodes (speech frames). $K$ needs to be set
up-front for every utterance, and we use a hyperparameter second-per-syllable
(secPerSyllable) to decide $K$ based on the duration of the utterance. In
practice, we use the variant introduced in [47], where we first oversegment
featSSM, and then iteratively merge temporally adjacent partitions if the
cosine similarity of the averaged features belonging to the two partitions
falls below some threshold (denoted as mergeThres). We found that this variant
always outperformed the original algorithm proposed in [46].

Clustering. With hypothesized syllabic segment boundaries produced by the min-
cut algorithm, we further use a 2-step clustering approach to categorize the
segments. Average features within each segment are used as the embedding of
the segment. We initially cluster the segment embeddings using KMeans to
produce a large number of clusters, and then run agglomerate clustering to
merge similar clusters. We found our 2-step clustering approach to work better
compared to just using Kmeans, given the same number of final clusters. Since
our work and [7] are both based on VG-HuBERT, we denote [7]'s segmentation
approach as $\text{VG-HuBERT}_{\text{cls}}$, where the CLS attention is used
to segment speech, and denote our approach as $\text{VG-
HuBERT}_{\text{featSSM}}$, where the min-cut algorithm is used on featSSM for
segmentation. Both approaches used the 2-step clustering method for segment
categorization.

Figure 1: Visualization of feature self-similarity matrix (upper) and the
attention (lower) in VG-HuBERT and HuBERT. The vertical white dotted lines are
generated by minCutMerge, and vertical blue dotted lines are generated by
taking the midpoint of boundaries of adjacent attention segments

##  4 Experiments

###  4.1 Datasets

Following [7], the training dataset is SpokenCOCO [48], an image-English
spoken caption dataset built on top of the MSCOCO image-text caption dataset
[49]. For evaluation on English, we use the test set of SpokenCOCO. Since
SpokenCOCO does not have syllable alignment, we first use the Montreal Forced
Aligner222https://montreal-forced-aligner.readthedocs.io/en/latest/ to
generate phonetic and word alignment, and then derive the corresponding
syllable alignment utilizing a rule-based syllabification
script333https://github.com/kylebgorman/syllabify. For cross-lingual
generalization experiments, we follow [17] and evaluate our approaches on
Estonian syllabic segmentation using the Phonetic Corpus of Estonian
Spontaneous Speech [50], which contains conversational speech between two test
subjects recorded with near-field microphones. The corpus comes with manually
verified syllable transcription and alignment. We also evaluate our approach
on the Zerospeech word segmentation task, which contains five languages:
Mandarin, English, French, German, and Wolof.

###  4.2 Implementation details

Model training. We use the official open-sourced codebase and training recipe
released by Peng and Harwath [7] and train a VG-HuBERT on SpokenCOCO. Model
snapshots are saved during training for syllable and word discovery analysis.

Evaluation. To evaluate segmentation performance, we use precision, recall, F1
and R-value [51, 23]. For the calculation of above metrics, we use a tolerance
window of $50$ms for SpokenCOCO and Estonian following [17], and $30$ms for
the Zerospeech Challenge [13]. To evaluate the quality of our syllable
clustering, we first match hypothesized syllable segments with the ground
truth segments for each utterance. To do so, we use a Hungarian matching
algorithm where each segment is a node and edge weights are defined by
temporal intersection-over-union between each hypothesized segment and ground
truth segment (unmatched segments are assigned to a dummy segment). Then, we
follow [7] and use cluster purity and number of detected syllables (DS). A
syllable is defined as being detected if it achieves an F1 score greater than
$0.5$ for some cluster [7]. To avoid conflating word detection and syllable
detection, we only evaluate on multisyllabic words.

Hyperparameter tuning. For SpokenCOCO, we tune the mergeThres to maximize the
segmentation R-value on the SpokenCOCO validation set. The number of clusters
in Kmeans and agglomerative clustering are fixed at $16384$ and $4096$. For
syllabic segmentation on Estonian, we tune the hyperparameters on a validation
set created following the procedure introduced in [17], using a subset of the
original Estonain corpus [50]. For cross-lingual word segmentation on the
Zerospeech challenge, we use the hyperparameters selected from the SpokenCOCO
validation set.

###  4.3 When do syllables and words emerge during training?

Figure 2: The performance of speech-image retrieval, and syllable and word
segmentation of VG-HuBERT as training progress.

We first investigate when syllable and word information emerges during the
training of VG-HuBERT. In Figure 2, we show the syllable and word segmentation
performance of VG-HuBERT as a function of training iteration, along with
speech-image retrieval accuracy on the SpokenCOCO validation set. Since the
contrastive training loss is a direct approximation of the retrieval metric,
speech-image retrieval accuracy keeps improving throughout the course of
training as expected. For syllabic segmentation, VG-HuBERT reaches the first
peak at 20*2k steps, and the performance keeps improving shortly afterwards,
with a trend similar to retrieval performance. Interestingly, VG-HuBERT peaks
at 20*2k steps for word segmentation, and the performance slightly decreases
before levelling off. Anecdotally, by manually examining some examples we
found that VG-HuBERT's CLS token tends to ignore more words in the later
stages of training. This might be because the model is starting to ignore non-
salient words in order to produce semantic representations that are more
discriminative in terms of retrieval performance. Notably, as we can see in
Figure 1, syllabic information for the entire utterance tends to persist in
the model's representations even when some segments are ignored by the CLS
token's attention.

###  4.4 Where in the model do syllables and words emerge?

We next perform a layer-wise study to show how visual grounding helps the
emergence of syllables and words, and the interplay between the discovery of
different linguistic units. Figure 3 compares VG-HuBERT to HuBERT for syllabic
segmentation, and also shows VG-HuBERT's word segmentation on the SpokenCOCO
validation set. HuBERT performs quite evenly across all layers, while syllabic
segmentation is best in VG-HuBERT's mid to late layers, and VG-HuBERT's word
segmentation ability is concentrated in the final few layers. We also fine-
tuned HuBERT on the SpokenCOCO utterances using its original self-supervised
loss to mitigate the potential domain gap, but did not see any improvement in
syllabic segmentation (see first two rows in Table 1). We see a `division of
labor' between different layers in VG-HuBERT with middle layers performing
best in syllabic segmentation, while the last three layers specialize in word
segmentation. In addition, we note that the best syllabic segmentation layer
(layer $9$) is right before the best word segmentation layer (layer $10$),
indicating that the attention heads may be learning to string syllables
together into words. We leave a more in-depth investigation of this phenomenon
for future work.

Figure 3: Layer-wise performance of VG-HuBERT on syllable and word
segmentation, and HuBERT on syllabic segmentation on SpokenCOCO val set.
HuBERT word segmentation gives very poor results [7] and therefore is not
shown.

###  4.5 Syllable discovery on English

Table 1 compares VG-HuBERT with other models for syllable discovery on the
SpokenCOCO test set. We see that HuBERT performs the worst on this dataset, no
matter whether it is fine-tuned on SpokenCOCO or not. $\text{VG-
HuBERT}_{\text{cls}}$ denotes the CLS token's attention-based segmentation, a
method that has been shown to achieve SotA on word segmentation [7], gives
high precision and low recall on this syllabic segmentation task as expected.
In terms of syllable detection, we see that $\text{VG-HuBERT}_{\text{cls}}$
can detect more than $700$ syllables with a high cluster purity. Considering
the high cluster purity and low boundary recall of $\text{VG-
HuBERT}_{\text{cls}}$, we conclude that this approach is able to discover a
smaller number of syllables, but is highly confident of the ones that it does
discover. Oscillator [17] is a signal processing-based syllabic segmentation
algorithm that achieves SotA for unsupervised syllabic segmentation on
multiple languages, including English. Oscillator performs reasonably well on
this dataset, only lagging behind our approach on segmentation. Our $\text{VG-
HuBERT}_{\text{featSSM}}$ model achieves the best performance in both syllabic
segmentation (best F1 and R-val) and clustering (best DS).

Table 1: Syllabic segmentation performance of different models on SpokenCOCO
test set. DS denotes detected syllables.

Model | Prec. | Rec. | F1 | R-val. | Purity | DS
---|---|---|---|---|---|---
HuBERT ft. [2] | 43.8 | 49.4 | 46.4 | 51.5 | 29.0 | 519
HuBERT [2] | 43.8 | 46.5 | 45.1 | 52.0 | 30.1 | 522
$\text{VG-HuBERT}_{\text{cls}}$ [7] | 58.7 | 37.1 | 45.5 | 54.3 | 66.1 | 751
Oscillator [17] | 52.0 | 64.6 | 57.6 | 57.4 | - | -
$\text{VG-HuBERT}_{\text{featSSM}}$ | 57.4 | 63.6 | 60.3 | 64.3 | 45.8 | 902

###  4.6 Zero-shot syllabic segmentation on Estonian

Syllables are strongly correlated with speech intensity and voicing, and are
organized around sonorant speech sounds [17]. This suggests that a syllable
detection model trained on one language may able to generalize to other
languages. We thus evaluate our English-trained models on a non-English
language, namely Estonian. We use the same five-hour subset and evaluation
pipeline as [17]. Table 2 lists the results. We see that compared to other
methods including the Oscillator, our VG-HuBERT performs the best in both F1
and R-val metrics, indicating that its syllabic segmentation ability is at
least somewhat language-agnostic.

Table 2: Syllabic segmentation on the Estonian corpus.

Approach | Prec. | Rec. | F1 | R-val.
---|---|---|---|---
$\text{VG-HuBERT}_{\text{cls}}$ [7] | 56 | 77 | 65 | 57
HuBERT [2] | 64 | 75 | 69 | 70
WN [17] | 77 | 62 | 69 | 72
EnvMin [52] | 67 | 71 | 69 | 73
Vseg [53] | 82 | 63 | 71 | 73
Oscillator [17] | 71 | 78 | 74 | 77
Oscillator (our reprod.) | 72 | 78 | 75 | 78
$\text{VG-HuBERT}_{\text{featSSM}}$ | 77 | 80 | 79 | 82

###  4.7 Zero-shot word segmentation on unseen languages

Lastly, we ask the question: if VG-HuBERT's CLS token detects words in
English, what does it do for a language it has not seen during training? To
investigate CLS token's behavior on languages unseen during training, we first
visualize the CLS attention for Estonian and Mandarin utterances in figure 4.
We see that anecdotally, the CLS attention appears to be performing syllabic
segmentation, but it sometimes also connect adjacent syllables together. In
some cases, the connections give invalid words - in figure 4, for Estonian
(the upper figure), `h_ve' and `i' are connected, but the result is not a
valid word; for Mandarin, `必须分' is connected (in the middle figure), and the
result is also not a valid word. However, in some other cases, the connections
happen to give valid words - in the two Mandarin examples in figure 4, `历史'
and `不知' got connected, and they are valid words.

Based on the observation that the CLS token produces a mixture of
monosyllablic and multisyllabic segmentation, we test $\text{VG-
HuBERT}_{\text{cls}}$ for word segmentation on the Zerospeech challenge. In
table 3, we see that VG-HuBERT achieves SotA performance on three out of five
languages, despite only being trained on English. Interestingly, VG-HuBERT
performs very differently on Mandarin and Wolof. While this could be due to
hyperparameter settings (we use the same hyperparameters for all languages),
we are not able to verify because the Wolof transcripts are not publicly
available.

Figure 4: Visualizations of VG-HuBERT's CLS attention on unseen languages -
Estonian and Mandarin. Thin dashed lines denote syllable boundaries, thick
vertical line denotes word boundaries. Word boundaries are also syllable
boundaries. Table 3: Word segmentation performance on the Zerospeech
Challenge. Token F1 is a stricter metric than boundary F1 where a word is
considered a hit only when both it's start and end boundaries are successfully
predicted.

Approach | Mand. | French | Engl. | German | Wolof
---|---|---|---|---|---
PDTW [54] | 4.4 | 5.1 | 4.1 | 2.9 | 4.2
ES-KMeans [18] | 8.1 | 6.3 | 19.2 | 14.5 | 10.9
SEA [55] | 12.1 | 6.3 | 6.6 | 6.3 | 12.6
DP-Parse [22] | 16.0 | 15.3 | 21.9 | 13.4 | 17.5
DPDP [23] | 26.3 | 12.2 | 19.2 | 9.0 | 15.0
$\text{VG-HuBERT}_{\text{cls}}$ | 19.5 | 15.5 | 26.6 | 15.8 | 7.1

##  5 Concluding Discussion

In this paper, we demonstrated that the VG-HuBERT visually-grounded speech
model exhibits emergent syllable recognition behavior. We proposed the use of
a minimum cut algorithm to automatically extract syllable boundaries from the
model's learned representations, and showed that this segmentation ability
could transfer to Estonian speech even though the model was only trained on
English. Furthermore, we demonstrated that the emergent word discovery ability
that is also present in the model could be applied in a zero-shot transfer
fashion to segment words in non-English languages, achieving state-of-the-art
segmentation performance for several languages in the Zerospeech Challenge
benchmark. In our future work, we plan to apply our syllable discovery method
to tokenize speech waveforms and use these tokenizations in various textless
speech processing tasks such as spoken language modeling and speech-to-speech
translation, as well as unsupervised speech recognition.

## References

  * [1] A. Baevski, Y. Zhou, A. Mohamed, and M. Auli, ``wav2vec 2.0: A framework for self-supervised learning of speech representations,'' in _NeurIPS_ , 2020\.
  * [2] W.-N. Hsu _et al._ , ``Hubert: Self-supervised speech representation learning by masked prediction of hidden units,'' _TASLP_ , 2021.
  * [3] Y.-A. Chung _et al._ , ``w2v-bert: Combining contrastive learning and masked language modeling for self-supervised speech pre-training,'' _ASRU_ , 2021.
  * [4] S. Chen _et al._ , ``Wavlm: Large-scale self-supervised pre-training for full stack speech processing,'' _JSTSP_ , 2021.
  * [5] A. Mohamed _et al._ , ``Self-supervised speech representation learning: A review,'' _JSTSP_ , 2022.
  * [6] D. Harwath, W. Hsu, and J. R. Glass, ``Learning hierarchical discrete linguistic units from visually-grounded speech,'' in _ICLR_ , 2020.
  * [7] P. Peng and D. F. Harwath, ``Word discovery in visually grounded, self-supervised speech models,'' in _Interspeech_ , 2022.
  * [8] K. Lakhotia _et al._ , ``On generative spoken language modeling from raw audio,'' _TACL_ , 2021.
  * [9] X. Li, Y. Jia, and C.-C. Chiu, ``Textless direct speech-to-speech translation with discrete speech representation,'' _ArXiv preprint_ , 2022.
  * [10] T. Nguyen _et al._ , ``Generative spoken dialogue language modeling,'' _ArXiv_ , 2022.
  * [11] G.-T. Lin _et al._ , ``Dual: Textless spoken question answering with speech discrete unit adaptive learning,'' _ArXiv preprint_ , 2022.
  * [12] A. Pasad, B. Shi, and K. Livescu, ``Comparative layer-wise analysis of self-supervised speech models,'' _ArXiv preprint_ , 2022.
  * [13] E. Dunbar, N. Hamilakis, and E. Dupoux, ``Self-supervised language learning from raw audio: Lessons from the zero resource speech challenge,'' _JSTSP_ , 2022.
  * [14] A. S. Park and J. R. Glass, ``Unsupervised pattern discovery in speech,'' _TASLP_ , no. 1, 2008.
  * [15] C.-y. Lee, T. J. O'Donnell, and J. Glass, ``Unsupervised lexicon discovery from acoustic input,'' _TACL_ , 2015.
  * [16] T. Taniguchi, S. Nagasaka, and R. Nakashima, ``Nonparametric bayesian double articulation analyzer for direct language acquisition from continuous speech signals,'' _TCDS_ , 2015.
  * [17] O. Räsänen, G. Doyle, and M. C. Frank, ``Pre-linguistic segmentation of speech into syllable-like units,'' _Cognition_ , 2018.
  * [18] H. Kamper, K. Livescu, and S. Goldwater, ``An embedded segmental k-means model for unsupervised segmentation and clustering of speech,'' _ASRU_ , 2017.
  * [19] Y. Wang, H. Lee, and L. Lee, ``Segmental audio word2vec: Representing utterances as sequences of vectors with applications in spoken term detection,'' in _ICASSP_ , 2018.
  * [20] S. Bhati _et al._ , ``Segmental contrastive predictive coding for unsupervised word segmentation,'' in _Interspeech_ , 2021.
  * [21] S. Cuervo _et al._ , ``Contrastive prediction strategies for unsupervised segmentation and categorization of phonemes and words,'' _ICASSP_ , 2022.
  * [22] R. Algayres _et al._ , ``Dp-parse: Finding word boundaries from raw speech with an instance lexicon,'' _TACL_ , 2022.
  * [23] H. Kamper, ``Word segmentation on discovered phone units with dynamic programming and self-supervised scoring,'' _TASLP_ , 2022.
  * [24] G. Chrupała, ``Visually grounded models of spoken language: A survey of datasets, architectures and evaluation techniques,'' _J. Artif. Intell. Res._ , 2021.
  * [25] S. Gabriel, V. Maarten, and E. Dupoux, ``Learning words from images and speech,'' in _NeurIPS Workshop on Learning Semantics_ , 2014.
  * [26] D. F. Harwath, A. Torralba, and J. R. Glass, ``Unsupervised learning of spoken language with visual context,'' in _NeurIPS_ , 2016.
  * [27] A. Rouditchenko _et al._ , ``Avlnet: Learning audio-visual language representations from instructional videos,'' in _Interspeech_ , 2021.
  * [28] M. Nikolaus, A. Alishahi, and G. Chrupała, ``Learning english with peppa pig,'' _TACL_ , vol. 10, pp. 922–936, 2022.
  * [29] H. Kamper, G. Shakhnarovich, and K. Livescu, ``Semantic speech retrieval with a visually grounded model of untranscribed speech,'' _TASLP_ , vol. 27, pp. 89–98, 2017.
  * [30] R. Sanabria, A. Waters, and J. Baldridge, ``Talk, don't write: A study of direct speech-based image retrieval,'' in _Interspeech_ , 2021.
  * [31] P. Peng and D. Harwath, ``Fast-slow transformer for visually grounding speech,'' in _ICASSP_ , 2022.
  * [32] Y.-J. Shih _et al._ , ``Speechclip: Integrating speech with pre-trained vision and language model,'' _2022 IEEE Spoken Language Technology Workshop (SLT)_ , pp. 715–722, 2022.
  * [33] K. Khorrami and O. J. Räsänen, ``Evaluation of audio-visual alignments in visually grounded speech models,'' in _Interspeech_ , 2021.
  * [34] D. F. Harwath, A. Recasens, D. Surís, G. Chuang, A. Torralba, and J. R. Glass, ``Jointly discovering visual objects and spoken words from raw sensory input,'' _IJCV_ , vol. 128, pp. 620–641, 2018.
  * [35] K. Olaleye, ``Visually grounded keyword detection and localisation for low-resource languages,'' _ArXiv_ , vol. abs/2302.00765, 2023.
  * [36] H. Kamper, A. Anastassiou, and K. Livescu, ``Semantic query-by-example speech search using visual grounding,'' _ICASSP_ , pp. 7120–7124, 2019.
  * [37] S. Yang _et al._ , ``SUPERB: speech processing universal performance benchmark,'' in _Interspeech_ , 2021.
  * [38] P. Peng and D. Harwath, ``Self-supervised representation learning for speech using visual grounding and masked language modeling,'' in _SAS@AAAI_ , 2022\.
  * [39] A. Alishahi, M. Barking, and G. Chrupała, ``Encoding of phonology in a recurrent neural model of grounded speech,'' _ArXiv_ , vol. abs/1706.03815, 2017.
  * [40] O. J. Räsänen and K. Khorrami, ``A computational model of early language acquisition from audiovisual experiences of young infants,'' in _Interspeech_ , 2019.
  * [41] W. N. Havard, J.-P. Chevrot, and L. Besacier, ``Models of visually grounded speech signal pay attention to nouns: A bilingual experiment on english and japanese,'' _ICASSP_ , pp. 8618–8622, 2019.
  * [42] ——, ``Word recognition, competition, and activation in a model of visually grounded speech,'' in _Conference on Computational Natural Language Learning_ , 2019.
  * [43] K. Khorrami and O. J. Räsänen, ``Can phones, syllables, and words emerge as side-products of cross-situational audiovisual learning? - a computational investigation,'' _Language Dev. Research_ , 2021.
  * [44] O. Russakovsky _et al._ , ``Imagenet large scale visual recognition challenge,'' _IJCV_ , vol. 115, pp. 211–252, 2014.
  * [45] J. Shi and J. Malik, ``Normalized cuts and image segmentation,'' _CVPR_ , 1997\.
  * [46] I. Malioutov and R. Barzilay, ``Minimum cut model for spoken lecture segmentation,'' in _ACL_ , 2006.
  * [47] D. F. Harwath and T. J. Hazen, ``Topic identification based extrinsic evaluation of summarization techniques applied to conversational speech,'' _ICASSP_ , 2012.
  * [48] W.-N. Hsu _et al._ , ``Text-free image-to-speech synthesis using learned segmental units,'' in _ACL_ , 2021.
  * [49] T.-Y. Lin _et al._ , ``Microsoft coco: Common objects in context,'' in _ECCV_ , 2014.
  * [50] P. Lippus _et al._ , ``Phonetic corpus of estonian spontaneous speech,'' _Institute of Estonian and General Linguistics, University of Tartu. DOI: https://doi. org/10.15155/TY. D_ , 2013.
  * [51] O. Räsänen, U. K. Laine, and T. Altosaar, ``An improved speech segmentation quality measure: the r-value,'' in _Interspeech_ , 2009.
  * [52] D. Wang and S. S. Narayanan, ``Robust speech rate estimation for spontaneous speech,'' _TASLP_ , 2007.
  * [53] R. Villing, J. Timoney, and T. E. Ward, ``Automatic blind syllable segmentation for continuous speech,'' 2004.
  * [54] O. Räsänen and M. A. C. Blandón, ``Unsupervised discovery of recurring speech patterns using probabilistic adaptive metrics,'' in _Interspeech_ , 2020.
  * [55] S. Bhati _et al._ , ``Self-expressing autoencoders for unsupervised spoken term discovery,'' in _Interspeech_ , 2020.


#  On the linear space of the two-sided generalized Fibonacci sequences

Martin Bunder
School of Mathematics and Applied Statistics
University of Wollongong  Australia
<EMAIL_ADDRESS>Joseph Tonien
School of Computing and Information Technology
University of Wollongong  Australia
<EMAIL_ADDRESS>
###### Abstract

In this paper, we study the linear space of all two-sided generalized
Fibonacci sequences $\\{F_{n}\\}_{n\in\mathbb{Z}}$ that satisfy the recurrence
equation of order $k$: $F_{n}=F_{n-1}+F_{n-2}+\dots+F_{n-k}$. We give two
types of explicit formula, one is based on generalized binomial coefficients
and the other based on generalized multinomial coefficients.

AMS Classification Numbers: 11B37, 11B39, 47B37

Keywords: generalized Fibonacci sequence, generalized binomial, generalized
multinomial.

##  1 Introduction

The Fibonacci sequence, $F_{0}=0$, $F_{1}=1$, $F_{n}=F_{n-1}+F_{n-2}$, have
been generalized in many ways. One of the generalizations [12, 5, 17] is to
change the recurrence equation to $F_{n}=\alpha F_{n-1}+\beta F_{n-2}$, thus
keeping the characteristic equation remained in order 2. Another common
generalization is to extend the recurrence equation to a higher order. For a
fixed integer $k\geq 2$, a sequence is called a Fibonacci sequence of order
$k$ if it satisfies the following recurrence equation

$F_{n}=F_{n-1}+F_{n-2}+\dots+F_{n-k}.$ (1)

For some particular values of $k$, the sequence has a special name. It is
called a tribonacci sequence, a tetranacci sequence and a pentanacci sequence
for $k=3,4,5$, respectively.

A Fibonacci sequence of order $k$ is uniquely determined by a list of values
of $k$ consecutive terms. For instance, if the values of
$F_{0},F_{1},\dots,F_{k-1}$ are given then using the recurrence equation (1),
we can work out the values of all other terms $F_{n}$ for $n\geq k$, as well
as for negative indices $n<0$. Here is an example of a Fibonacci sequence of
order 5:

$\displaystyle\dots,F_{-4}=-2,F_{-3}=7,F_{-2}=-3,F_{-1}=-4,$ $\displaystyle
F_{0}={\bf 3},F_{1}={\bf 1},F_{2}={\bf 4},F_{3}={\bf 1},F_{4}={\bf
5},F_{5}=14,F_{6}=25,\dots\quad.$

Since we have $F_{0}=0$ and $F_{1}=1$ in the original Fibonacci sequence,
there are two common ways to set the initial conditions: (i)
$F_{0}=F_{1}=\dots=F_{k-2}=0$, $F_{k-1}=1$ as in [18, 9, 19, 13, 4, 6]; or
(ii) $F_{0}=0$, $F_{1}=\dots=F_{k-2}=F_{k-1}=1$ as in [14, 21, 3]. Another
initial condition $F_{0}=F_{1}=\dots=F_{k-1}=1$ appears in Ferguson [8] arisen
in the study of polyphase merge-sorting. Various formulas have been found for
Fibonacci sequences with these three initial conditions which can be grouped
into three types: Binet formula [7, 13], binomial coefficients [8, 1] and
multinomial coefficents [18, 13]. We note that these formulas of $F_{n}$ are
only restricted to the integer indices $n\geq 0$. The Binet type of formula is
algebraic in nature and remains valid when we extend to negative indices
$n<0$. However, formulas involved binomial coefficients and multinomial
coefficents are limited to non-negative indices and it is not trivial to
extend to negative indices.

While most authors only consider sequences $F_{n}$ with $n\geq 0$, in this
paper, we will study two-sided sequences. Those are sequences $\\{F_{n}\\}$
where the index $n\in\mathbb{Z}$, that is, we allow $n$ to be a negative
integer. Instead of looking for explicit formula for a Fibonacci sequence with
a particular initial condition, our aim is to find explicit formulas for a
general Fibonacci sequence that has an arbitrary initial condition
$(F_{0},F_{1},\dots,F_{k-1})$. To do that, we consider the set of all
Fibonacci sequences of order $k$. This forms a $k$-dimensional linear space.
We will study the standard basis of this linear space which is denoted by
$B^{(0)},B^{(1)},\dots,B^{(k-1)}$. For $0\leq j\leq k-1$, each $B^{(j)}$ is a
Fibonacci sequence whose initial values are all zero except $B^{(j)}_{j}=1$.
We will find explicit formula for the basis sequences
$B^{(0)},B^{(1)},\dots,B^{(k-1)}$, and thus, any Fibonacci sequence $F$ can be
determined by a linear combination
$F=F_{0}B^{(0)}+F_{1}B^{(1)}+\dots+F_{k-1}B^{(k-1)}$.

Our aim is to find explicit formulas for two-sided Fibonacci sequences that
are expressed in terms of binomial coefficients and multinomial coefficients,
respectively. Since the classical binomial coefficients and multinomial
coefficients are only associated with non-negative integers, to use these for
our two-sided sequences we need to extend the binomial notation and
multinomial notation to include negative integers. To this end, we extend the
binomial notation ${n\choose i}$ to negative values of $n$ and $i$, writing
this as $\left\langle{n\choose i}\right\rangle$. Subjected to the two
conditions $\left\langle{n\choose n}\right\rangle=1$ and
$\left\langle{{n-1}\choose{i}}\right\rangle+\left\langle{{n-1}\choose{i-1}}\right\rangle=\left\langle{{n}\choose{i}}\right\rangle$,
the latter is called the Pascal Recursion equation, the value of the
generalized binomial notation is uniquely determined. In Theorem 7, we will
show that

$\displaystyle B_{n}^{(j)}=$
$\displaystyle-\sum_{i\in\mathbb{Z}}{(-1)^{i}\left\langle{{n-ik}\choose{i-1}}\right\rangle
2^{n+1-i(k+1)}}$
$\displaystyle+\sum_{i\in\mathbb{Z}}{(-1)^{i}\left\langle{{n-j-1-ik}\choose{i-1}}\right\rangle
2^{n-j-i(k+1)}}\mbox{ for all }n\in\mathbb{Z}.$

We extend the multinomial notation ${n\choose{i_{1},i_{2},\dots,i_{t}}}$ to
negative values of $n$ and $i_{1},\dots,i_{t}$, writing this as
$\left\langle{n\choose{i_{1},i_{2},\dots,i_{t}}}\right\rangle$. The
generalization is done as follows.

Using the generalized binomial notation we extend the traditional multinomial
notation

${n\choose{i_{1},i_{2},\dots,i_{k}}}={n\choose{i_{2}+\dots+i_{t}}}{{i_{2}+\dots+i_{t}}\choose{i_{3}+\dots+i_{t}}}\dots{i_{t-2}+i_{t-1}+i_{t}}\choose{i_{t-1}+i_{t}}{{i_{t-1}+i_{t}}\choose{i_{t}}},$

to

$\displaystyle\left\langle{{n}\choose{i_{1},i_{2},\dots,i_{t}}}\right\rangle=\left\langle{{n}\choose{i_{2}+\dots+i_{t}}}\right\rangle\left\langle{{i_{2}+\dots+i_{t}}\choose{i_{3}+\dots+i_{t}}}\right\rangle\dots\left\langle{{i_{t-2}+i_{t-1}+i_{t}}\choose{i_{t-1}+i_{t}}}\right\rangle\left\langle{{i_{t-1}+i_{t}}\choose{i_{t}}}\right\rangle.$

Using this generalized multinomial notation, in Theorem 12, we will show that

$B_{n}^{(j)}=\sum_{n-k-j\leq a_{1}+2a_{2}+\dots+ka_{k}\leq
n-k}{\left\langle{{a_{1}+a_{2}+\dots+a_{k}}\choose{a_{1},a_{2},\dots,a_{k}}}\right\rangle},\mbox{
for all }n\in\mathbb{Z}.$

The rest of the paper is organised as follows. In section 2, we study the
linear space of Fibonacci sequences of order $k$ in general, especially
looking at the linear automorphisms of this space. Formulas based on the
generalized binomial notation are derived in section 3. Formulas based on the
generalized multinomial notation are derived in section 4. Finally, in section
5, we remark on how the generalized Fibonacci sequences are related to a
tiling problem.

##  2 The Fibonacci linear space of order $k$

######  Definition 1.

Let $k\geq 2$ be a fixed integer. A sequence $\\{F_{n}\\}_{n\in{\mathbb{Z}}}$
is called a Fibonacci sequence of order $k$ if it satisfies the following
recurrence equation

$F_{n}=F_{n-1}+F_{n-2}+\dots+F_{n-k},\mbox{ for all }n\in\mathbb{Z}.$ (2)

We can see that, given $k$ values $(F_{0},F_{1},\dots,F_{k-1})$, then using
the Fibonacci recurrence equation (2), all other values $F_{n}$ for
$n\in\mathbb{Z}$ are determined uniquely. We will refer to
$(F_{0},F_{1},\dots,F_{k-1})$ as the initial values of the sequence. The set
of all Fibonacci sequences of order $k$ forms a $k$-dimensional vector space
(either over the field $\mathbb{R}$ or $\mathbb{C}$). We will use
$\mathsf{Fibonacci}^{(k)}$ to denote this vector space of all Fibonacci
sequences of order $k$. We now define the standard basis for the Fibonacci
vector space $\mathsf{Fibonacci}^{(k)}$.

######  Definition 2.

Let $k\geq 2$ be a fixed integer. For each integer $0\leq j\leq k-1$, the
sequence $B^{(j)}\in\mathsf{Fibonacci}^{(k)}$ is defined by the initial values

$B^{(j)}_{n}=\begin{cases}0,&\mbox{ if }0\leq n\leq k-1\mbox{ and }n\neq j\\\
1,&\mbox{ if }n=j.\end{cases}$

The special sequences $B^{(0)},B^{(1)},\dots,B^{(k-1)}$ defined above form a
standard basis for the space $\mathsf{Fibonacci}^{(k)}$. Any member of this
Fibonacci vector space is a linear combination of the standard basis and we
have the following theorem.

######  Theorem 1.

Let $k\geq 2$ be a fixed integer. Let $\\{F_{n}\\}_{n\in{\mathbb{Z}}}$ be a
Fibonacci sequence of order $k$. Then

$F_{n}=\sum_{j=0}^{k-1}{B^{(j)}_{n}F_{j}}\mbox{ for all }n\in\mathbb{Z}.$

By Theorem 1, we can see that in order to determine an explicit formula for
any Fibonacci sequence $\\{F_{n}\\}_{n\in{\mathbb{Z}}}$, it suffices to derive
formula for the $k$ basis sequences $B^{(0)},B^{(1)},\dots,B^{(k-1)}$.

###  2.1 Linear operators on the Fibonacci space

Here we list some standard linear operators on two-sided sequences.

  * •

Identity operator $\mathtt{I}$.

  * •

Left shift operator $\mathtt{L}$: $\mathtt{L}(X)=Y$ iff $Y_{n}=X_{n+1}$ for
all $n\in{\mathbb{Z}}$.

  * •

Right shift operator $\mathtt{R}$: $\mathtt{R}(X)=Y$ iff $Y_{n}=X_{n-1}$ for
all $n\in{\mathbb{Z}}$. The left shift and the right shift are inverse of each
other: $\mathtt{L}\mathtt{R}=\mathtt{R}\mathtt{L}=\mathtt{I}$.

  * •

Forward difference operator $\Delta$: $\Delta(X)=Y$ iff $Y_{n}=X_{n+1}-X_{n}$
for all $n\in{\mathbb{Z}}$. Here $\Delta=\mathtt{L}-\mathtt{I}$.

  * •

Backward difference operator $\nabla$: $\nabla(X)=Y$ iff $Y_{n}=X_{n}-X_{n-1}$
for all $n\in{\mathbb{Z}}$. Here
$\nabla=\mathtt{I}-\mathtt{R}=\mathtt{I}-\mathtt{L}^{-1}$,
$\mathtt{L}\nabla=\Delta$ and $\mathtt{R}\Delta=\nabla$.

We have the following theorem concerning the above operators.

######  Theorem 2.

All operators $\mathtt{I}$, $\mathtt{L}$, $\mathtt{R}$, $\Delta$ and $\nabla$
when restricted to the space $\mathsf{Fibonacci}^{(k)}$ are linear
automorphisms $\mathsf{Fibonacci}^{(k)}\to\mathsf{Fibonacci}^{(k)}$ and
satisfy the following relations:

(i)
$\mathtt{L}^{k}=\mathtt{I}+\mathtt{L}+\mathtt{L}^{2}+\dots+\mathtt{L}^{k-1}.$

(ii)
$\mathtt{R}=\mathtt{L}^{-1}=-\mathtt{I}-\mathtt{L}-\mathtt{L}^{2}-\dots-\mathtt{L}^{k-2}+\mathtt{L}^{k-1}$

(iii)
$\mathtt{R}^{k}=\mathtt{I}-\mathtt{R}-\mathtt{R}^{2}-\dots-\mathtt{R}^{k-1}.$

(iv)
$\mathtt{L}=\mathtt{R}^{-1}=\mathtt{I}+\mathtt{R}+\mathtt{R}^{2}+\dots+\mathtt{R}^{k-1}.$

(v) $\mathtt{L}^{k+1}=2\mathtt{L}^{k}-\mathtt{I}.$

(vi) $\mathtt{R}^{k+1}=2\mathtt{R}-\mathtt{I}.$

(vii)
$\Delta(\mathtt{I}+(k-1)\mathtt{R}+(k-2)\mathtt{R}^{2}+(k-3)\mathtt{R}^{3}+\dots+2\mathtt{R}^{k-2}+\mathtt{R}^{k-1})=(k-1)\mathtt{I}.$

(viii)
$\nabla(k\mathtt{I}+(k-1)\mathtt{R}+(k-2)\mathtt{R}^{2}+\dots+2\mathtt{R}^{k-2}+\mathtt{R}^{k-1})=(k-1)\mathtt{I}.$

(ix) $\sum_{i=0}^{k}{{k+1}\choose{i+1}}\frac{k-1-2i}{k+1}\Delta^{i}=0.$

(x) $(k-1)\mathtt{I}+\sum_{i=1}^{k}{{k+1}\choose{i+1}}(-1)^{i}\nabla^{i}=0.$

Proof. It is easy to see that all these operators $\mathtt{I}$, $\mathtt{L}$,
$\mathtt{R}$, $\Delta$ and $\nabla$ are linear. Each maps a Fibonacci sequence
to another Fibonacci sequence. The bijectivity of $\mathtt{I}$, $\mathtt{L}$,
$\mathtt{R}$ is obvious, whereas, the bijectivity of $\Delta$ and $\nabla$
follows from (vii) and (viii), respectively.

(i) For any $X\in\mathsf{Fibonacci}^{(k)}$, let
$(\mathtt{I}+\mathtt{L}+\mathtt{L}^{2}+\dots+\mathtt{L}^{k-1})(X)=Y$ then
$Y_{n}=X_{n}+X_{n+1}+X_{n+2}+\dots+X_{n+k-1}=X_{n+k}$, therefore,
$Y=\mathtt{L}^{k}(X)$. This proves that, restricted to the linear space
$\mathsf{Fibonacci}^{(k)}$,
$\mathtt{I}+\mathtt{L}+\mathtt{L}^{2}+\dots+\mathtt{L}^{k-1}=\mathtt{L}^{k}$.

(ii) For any $X\in\mathsf{Fibonacci}^{(k)}$, let
$(-\mathtt{I}-\mathtt{L}-\mathtt{L}^{2}-\dots-\mathtt{L}^{k-2}+\mathtt{L}^{k-1})(X)=Y$
then $Y_{n}=-X_{n}-X_{n+1}-X_{n+2}-\dots-X_{n+k-2}+X_{n+k-1}=X_{n-1}$. Hence,
$Y=\mathtt{R}(X)$, and therefore,
$-\mathtt{I}-\mathtt{L}-\mathtt{L}^{2}-\dots-\mathtt{L}^{k-2}+\mathtt{L}^{k-1}=\mathtt{R}=\mathtt{L}^{-1}$.

(iii) For any $X\in\mathsf{Fibonacci}^{(k)}$, let
$(\mathtt{I}-\mathtt{R}-\mathtt{R}^{2}-\dots-\mathtt{R}^{k-1})(X)=Y$ then
$Y_{n}=X_{n}-X_{n-1}-X_{n-2}-\dots-X_{n-k+1}=X_{n-k}$. Hence,
$Y=\mathtt{R}^{k}(X)$, and therefore,
$\mathtt{I}-\mathtt{R}-\mathtt{R}^{2}-\dots-\mathtt{R}^{k-1}=\mathtt{R}^{k}.$

(iv) For any $X\in\mathsf{Fibonacci}^{(k)}$, let
$(\mathtt{I}+\mathtt{R}+\mathtt{R}^{2}+\dots+\mathtt{R}^{k-1})(X)=Y$ then
$Y_{n}=X_{n}+X_{n-1}+X_{n-2}+\dots+X_{n-k+1}=X_{n+1}$. Hence,
$Y=\mathtt{L}(X)$, and therefore,
$\mathtt{I}+\mathtt{R}+\mathtt{R}^{2}+\dots+\mathtt{R}^{k-1}=\mathtt{L}=\mathtt{R}^{-1}$.

(v) By (i),
$\mathtt{L}^{k+1}=\mathtt{L}\,\mathtt{L}^{k}=\mathtt{L}(\mathtt{I}+\mathtt{L}+\mathtt{L}^{2}+\dots+\mathtt{L}^{k-1})=\mathtt{L}+\mathtt{L}^{2}+\dots+\mathtt{L}^{k-1}+\mathtt{L}^{k}=(\mathtt{I}+\mathtt{L}+\mathtt{L}^{2}+\dots+\mathtt{L}^{k-1})+\mathtt{L}^{k}-\mathtt{I}=\mathtt{L}^{k}+\mathtt{L}^{k}-\mathtt{I}=2\mathtt{L}^{k}-\mathtt{I}$.

(vi) By (iii),
$\mathtt{R}^{k+1}=\mathtt{R}\mathtt{R}^{k}=\mathtt{R}(\mathtt{I}-\mathtt{R}-\mathtt{R}^{2}-\dots-\mathtt{R}^{k-1})=\mathtt{R}-\mathtt{R}^{2}-\mathtt{R}^{3}-\dots-\mathtt{R}^{k-1}-\mathtt{R}^{k}=\mathtt{R}-\mathtt{R}^{2}-\mathtt{R}^{3}-\dots-\mathtt{R}^{k-1}-(\mathtt{I}-\mathtt{R}-\mathtt{R}^{2}-\dots-\mathtt{R}^{k-1})=2\mathtt{R}-\mathtt{I}$.

(vii) We have

$\displaystyle\Delta(\mathtt{I}+(k-1)\mathtt{R}+(k-2)\mathtt{R}^{2}+(k-3)\mathtt{R}^{3}+\dots+2\mathtt{R}^{k-2}+\mathtt{R}^{k-1})$
$\displaystyle=(\mathtt{L}-\mathtt{I})(\mathtt{I}+(k-1)\mathtt{R}+(k-2)\mathtt{R}^{2}+(k-3)\mathtt{R}^{3}+\dots+2\mathtt{R}^{k-2}+\mathtt{R}^{k-1})$
$\displaystyle=\mathtt{L}+(k-2)\mathtt{I}-\mathtt{R}-\mathtt{R}^{2}-\dots-\mathtt{R}^{k-2}-\mathtt{R}^{k-1}$
$\displaystyle=(k-1)\mathtt{I}\quad\mbox{ by (iv).}$

(viii) We have

$\displaystyle\nabla(k\mathtt{I}+(k-1)\mathtt{R}+(k-2)\mathtt{R}^{2}+\dots+2\mathtt{R}^{k-2}+\mathtt{R}^{k-1})$
$\displaystyle=(\mathtt{I}-\mathtt{R})(k\mathtt{I}+(k-1)\mathtt{R}+(k-2)\mathtt{R}^{2}+\dots+2\mathtt{R}^{k-2}+\mathtt{R}^{k-1})$
$\displaystyle=k\mathtt{I}-\mathtt{R}-\mathtt{R}^{2}-\dots-\mathtt{R}^{k-1}-\mathtt{R}^{k}$
$\displaystyle=(k-1)\mathtt{I}\quad\mbox{ by (iii).}$

(ix) Substituting $\mathtt{L}=\mathtt{I}+\Delta$ into (i), we have

$\displaystyle(\mathtt{I}+\Delta)^{k}$
$\displaystyle=\mathtt{I}+(\mathtt{I}+\Delta)+(\mathtt{I}+\Delta)^{2}+\dots+(\mathtt{I}+\Delta)^{k-1}$
$\displaystyle\sum_{i=0}^{k}{k\choose i}\Delta^{i}$
$\displaystyle=\sum_{j=0}^{k-1}\sum_{i=0}^{j}{j\choose
i}\Delta^{i}=\sum_{i=0}^{k-1}\sum_{j=i}^{k-1}{j\choose
i}\Delta^{i}=\sum_{i=0}^{k-1}{k\choose{i+1}}\Delta^{i}.$

Therefore,

$\displaystyle\Delta^{k}$
$\displaystyle=\sum_{i=0}^{k-1}\left({k\choose{i+1}}-{k\choose
i}\right)\Delta^{i}=\sum_{i=0}^{k-1}{{k+1}\choose{i+1}}\frac{k-1-2i}{k+1}\Delta^{i}.$

(x) Substituting $\mathtt{R}=\mathtt{I}-\nabla$ into (iii), we have

$\displaystyle(\mathtt{I}-\nabla)^{k}$
$\displaystyle=\mathtt{I}-(\mathtt{I}-\nabla)-(\mathtt{I}-\nabla)^{2}-\dots-(\mathtt{I}-\nabla)^{k-1}.$

So

$\displaystyle\sum_{i=1}^{k}{k\choose i}(-\nabla)^{i}$
$\displaystyle=-\sum_{j=1}^{k-1}\sum_{i=0}^{j}{j\choose
i}(-\nabla)^{i}=-(k-1)\mathtt{I}-\sum_{i=1}^{k-1}\sum_{j=i}^{k-1}{j\choose
i}(-\nabla)^{i}$
$\displaystyle=-(k-1)\mathtt{I}-\sum_{i=1}^{k-1}{k\choose{i+1}}(-\nabla)^{i}.$

Therefore,

$\displaystyle(-\nabla)^{k}$
$\displaystyle=-(k-1)\mathtt{I}-\sum_{i=1}^{k-1}\left({k\choose{i+1}}+{k\choose
i}\right)(-\nabla)^{i}$
$\displaystyle=-(k-1)\mathtt{I}-\sum_{i=1}^{k-1}{{k+1}\choose{i+1}}(-\nabla)^{i}$

and

$\displaystyle\sum_{i=1}^{k}{{k+1}\choose{i+1}}(-\nabla)^{i}$
$\displaystyle=-(k-1)\mathtt{I}.\quad\blacksquare$

######  Theorem 3.

Denote $S=B^{(0)}+B^{(1)}+\dots+B^{(k-1)}\in\mathsf{Fibonacci}^{(k)}$. We have

(i) $B^{(j)}-B^{(j-1)}=\mathtt{R}^{j}(B^{(0)})$ for all $1\leq j\leq k-1$.

(ii) $B^{(j)}=\sum_{i=0}^{j}\mathtt{R}^{i}(B^{(0)})$ for all $0\leq j\leq
k-1$.

(iii) $B^{(0)}=\mathtt{R}(B^{(k-1)})$ and $B^{(k-1)}=\mathtt{L}(B^{(0)})$.

(iv) $B^{(j)}=\sum_{i=0}^{j}\mathtt{R}^{i+1}(B^{(k-1)})$ for all $0\leq j\leq
k-1$.

(v)
$S=(k\,\mathtt{I}+(k-1)\,\mathtt{R}+(k-2)\,\mathtt{R}^{2}+\dots+\mathtt{R}^{k-1})(B^{(0)})$.

(vi) $\nabla(S)=(k-1)B^{(0)}$.

(vii) $(\mathtt{I}-\mathtt{R}^{j+1})(S)=(k-1)B^{(j)}$ for all $0\leq j\leq
k-1$.

Proof. (i) Both $B^{(j)}-B^{(j-1)}$ and $\mathtt{R}^{j}(B^{(0)})$ are members
of $\mathsf{Fibonacci}^{(k)}$ and their initial values are equal, therefore,
$B^{(j)}-B^{(j-1)}=\mathtt{R}^{j}(B^{(0)})$.

(ii) It follows from (i).

(iii) By (ii), $B^{(k-1)}=\sum_{i=0}^{k-1}\mathtt{R}^{i}(B^{(0)})$ and since
$\mathtt{L}=\mathtt{R}^{-1}=\mathtt{I}+\mathtt{R}+\mathtt{R}^{2}+\dots+\mathtt{R}^{k-1}$
(Theorem 2(iv)), we have $B^{(k-1)}=\mathtt{L}(B^{(0)})$ and so
$B^{(0)}=\mathtt{R}(B^{(k-1)})$.

(iv) It follows from (ii) and (iii).

(v) It follows from (ii).

(vi) It follows from (v) and Theorem 2(viii).

(vii) We have

$\displaystyle(k-1)B^{(j)}$
$\displaystyle=(k-1)\sum_{i=0}^{j}\mathtt{R}^{i}(B^{(0)})\quad\mbox{ by (ii)}$
$\displaystyle=\sum_{i=0}^{j}\mathtt{R}^{i}(\nabla(S))\quad\mbox{ by (vi)}$
$\displaystyle=\sum_{i=0}^{j}(\mathtt{R}^{i}(1-\mathtt{R}))(S)=(1-\mathtt{R}^{j+1})(S).$

Another direct way to prove (vii) is by observing that both $(k-1)B^{(j)}$ and
$(1-\mathtt{R}^{j+1})(S)$ are members of $\mathsf{Fibonacci}^{(k)}$ and their
initial values are equal. $\blacksquare$

##  3 Explicit formulas based on binomials

In this section, we will derive explicit formula for the two-sided Fibonacci
basis sequences $B^{(0)},B^{(1)},\dots,B^{(k-1)}$ expressed in terms of
binomial coefficients. Since the traditional binomial notation is associated
with non-negative integers, to use these for our two-sided sequences we need
to extend the binomial notation to include negative integers. To this end, we
extend the binomial notation ${n\choose i}$ to negative values of $n$ and $i$.

The binomial notation ${n\choose i}$ can be generalized to
$\left\langle{{n}\choose{i}}\right\rangle$ for all integers $n$ and $i$ by
enforcing two conditions:

  * •

$\left\langle{{n}\choose{n}}\right\rangle=1$ for all $n\in\mathbb{Z}$; and

  * •

Pascal Recursion relation

$\left\langle{{n-1}\choose{i}}\right\rangle+\left\langle{{n-1}\choose{i-1}}\right\rangle=\left\langle{{n}\choose{i}}\right\rangle.$
(3)

With these two conditions, $\left\langle{{n}\choose{i}}\right\rangle$ is
uniquely determined as

$\displaystyle\left\langle{{n}\choose{i}}\right\rangle$
$\displaystyle=\begin{cases}\frac{n^{\underline{n-i}}}{(n-i)!}=\frac{n(n-1)(n-2)\dots(i+1)}{(n-i)!},&\text{if
}n\geq i\\\ 0,&\text{otherwise}\end{cases}$ (4)
$\displaystyle=\begin{cases}{n\choose i},&\text{if }n\geq i\geq 0\\\
(-1)^{i+n}{{-i-1}\choose{-n-1}},&\text{if }-1\geq n\geq i\\\
0,&\text{otherwise}\end{cases}.$ (5)

Refer to [15, 16] for detailed discussion on various generalizations of
binomial notation. The following table shows some values of
$\left\langle{{n}\choose{i}}\right\rangle$:

$\left\langle{{n}\choose{i}}\right\rangle$ | $i$
---|---
$-6$ | $-5$ | $-4$ | $-3$ | $-2$ | $-1$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$
$n$ | $6$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $1$ | $6$ | $15$ | $20$ | $15$ | $6$ | $1$
$5$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $1$ | $5$ | $10$ | $10$ | $5$ | $1$ | $0$
$4$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $1$ | $4$ | $6$ | $4$ | $1$ | $0$ | $0$
$3$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $1$ | $3$ | $3$ | $1$ | $0$ | $0$ | $0$
$2$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $1$ | $2$ | $1$ | $0$ | $0$ | $0$ | $0$
$1$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $1$ | $1$ | $0$ | $0$ | $0$ | $0$ | $0$
$0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $1$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$
$-1$ | $-1$ | $1$ | $-1$ | $1$ | $-1$ | $1$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$
$-2$ | $5$ | $-4$ | $3$ | $-2$ | $1$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$
| $-3$ | $-10$ | $6$ | $-3$ | $1$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$
| $-4$ | $10$ | $-4$ | $1$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$
| $-5$ | $-5$ | $1$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$
| $-6$ | $1$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$

In the following theorem, we define an auxiliary sequence
$\\{A_{n}\\}_{n\in\mathbb{Z}}$ which will be useful in the sequel. Note that
this sequence is not a member of the linear space $\mathsf{Fibonacci}^{(k)}$.
The proof of the theorem is a consequence of the Pascal Recursion relation
(3).

######  Theorem 4.

Let $k\geq 2$ and the sequence $\\{A_{n}\\}$ defined as

$A_{n}=\sum_{i\in\mathbb{Z}}{(-1)^{i}\left\langle{{n-ik}\choose{i-1}}\right\rangle
2^{n+1-i(k+1)}}\mbox{ for all }n\in\mathbb{Z}.$ (6)

Then $A_{0}=A_{1}=A_{2}=\dots=A_{k-1}=0$,
$A_{n}=A_{n-1}+A_{n-2}+\dots+A_{n-k}-1$ and $A_{n}=2A_{n-1}-A_{n-k-1}$.

Proof. Note that the above summation in the formula of $A_{n}$ only has a
finite number of non-zero terms. This is because
$\left\langle{{n-ik}\choose{i-1}}\right\rangle=0$ except for $1\leq
i\leq\frac{n+1}{k+1}$ when $n\geq 0$ and $\frac{n+1}{k}\leq
i\leq\frac{n+1}{k+1}$ for $n\leq-1$. It follows that
$A_{0}=A_{1}=A_{2}=\dots=A_{k-1}=0$ and $A_{k}=-1$.

We have

$\displaystyle 2A_{n-1}-A_{n-k-1}=$ $\displaystyle
2\sum{(-1)^{i}\left\langle{{n-1-ik}\choose{i-1}}\right\rangle 2^{n-i(k+1)}}$
$\displaystyle-\sum{(-1)^{i}\left\langle{{n-k-1-ik}\choose{i-1}}\right\rangle
2^{n-k-i(k+1)}}$ $\displaystyle=$
$\displaystyle\sum{(-1)^{i}\left\langle{{n-1-ik}\choose{i-1}}\right\rangle
2^{n+1-i(k+1)}}$
$\displaystyle+\sum{(-1)^{i+1}\left\langle{{n-1-(i+1)k}\choose{i-1}}\right\rangle
2^{n+1-(i+1)(k+1)}}.$

In the last summation, let $i:=i+1$, we have

$\displaystyle 2A_{n-1}-A_{n-k-1}=$
$\displaystyle\sum{(-1)^{i}\left\langle{{n-1-ik}\choose{i-1}}\right\rangle
2^{n+1-i(k+1)}}$
$\displaystyle+\sum{(-1)^{i}\left\langle{{n-1-ik}\choose{i-2}}\right\rangle
2^{n+1-i(k+1)}}$

and by the Pascal Recursion (3),

$\displaystyle 2A_{n-1}-A_{n-k-1}=$
$\displaystyle\sum{(-1)^{i}\left\langle{{n-ik}\choose{i-1}}\right\rangle
2^{n+1-i(k+1)}}$ $\displaystyle=$ $\displaystyle A_{n}.$

Therefore, $(\mathtt{R}^{k+1}-2\mathtt{R}+\mathtt{I})(A)=0$.

As
$\mathtt{R}^{k+1}-2\mathtt{R}+\mathtt{I}=(\mathtt{R}-\mathtt{I})(\mathtt{R}^{k}+\mathtt{R}^{k-1}+\dots+\mathtt{R}-\mathtt{I})$,
it follows that
$(\mathtt{R}^{k}+\mathtt{R}^{k-1}+\dots+\mathtt{R}-\mathtt{I})(A)$ is a
constant sequence, so
$A_{n-1}+A_{n-2}+\dots+A_{n-k}-A_{n}=A_{0}+A_{1}+\dots+A_{k-1}-A_{k}=1$.
$\blacksquare$

Recall that in Theorem 3 we define the sequence
$S=B^{(0)}+B^{(1)}+\dots+B^{(k-1)}\in\mathsf{Fibonacci}^{(k)}$. The following
theorem gives an explicit formula for the sequence $S$.

######  Theorem 5.

Let $k\geq 2$. The $k$-order Fibonacci sequence $S$ (determined by the first
$k$ terms $(1,1,\dots,1)$) satisfies the following formula

$S_{n}=1-(k-1)\sum_{i\in\mathbb{Z}}{(-1)^{i}\left\langle{{n-ik}\choose{i-1}}\right\rangle
2^{n+1-i(k+1)}}\mbox{ for all }n\in\mathbb{Z}.$ (7)

Proof. Let $S_{n}^{\prime}$ denote the sequence on the RHS of (7) then
$S_{n}^{\prime}=1-(k-1)A_{n}$ where $\\{A_{n}\\}$ is the auxiliary sequence
defined in Theorem 4. It follows from Theorem 4 that
$S_{0}^{\prime}=S_{1}^{\prime}=\dots=S_{k-1}^{\prime}=1$, $S_{k}^{\prime}=k$
and $S^{\prime}_{n}=2S^{\prime}_{n-1}-S^{\prime}_{n-k-1}$. By Theorem 2(vi),
the sequence $S$ also satisfies the same recursion equation
$S_{n}=2S_{n-1}-S_{n-k-1}$. Since $S_{i}=S^{\prime}_{i}$ for all $0\leq i\leq
k$, it follows that $S_{i}=S^{\prime}_{i}$ for all $i\in\mathbb{Z}$.
$\blacksquare$

######  Theorem 6.

Let $k\geq 2$. The $k$-order Fibonacci sequence $S$ (determined by the first
$k$ terms $(1,1,\dots,1)$) satisfies the following formula

$S_{n}=1-(k-1)\sum_{1\leq
i\leq\frac{n+1}{k+1}}{(-1)^{i}{{n-ik}\choose{i-1}}2^{n+1-i(k+1)}}\mbox{ for
all }n\geq 0,$ (8) $S_{n}=1-(k-1)\sum_{\frac{n+1}{k}\leq
i\leq\frac{n+1}{k+1}}{(-1)^{i}\left\langle{{n-ik}\choose{i-1}}\right\rangle
2^{n+1-i(k+1)}}\mbox{ for all }n\leq-1.$ (9)

Proof. Since $\left\langle{{n-ik}\choose{i-1}}\right\rangle=0$ except for
$1\leq i\leq\frac{n+1}{k+1}$ when $n\geq 0$ and $\frac{n+1}{k}\leq
i\leq\frac{n+1}{k+1}$ for $n\leq-1$, the theorem follows from Theorem 5.
$\blacksquare$

######  Theorem 7.

Let $k\geq 2$, $0\leq j\leq k-1$. The $k$-order Fibonacci sequence $B^{(j)}$
satisfies the following formula

$\displaystyle B_{n}^{(j)}=$
$\displaystyle-\sum_{i\in\mathbb{Z}}{(-1)^{i}\left\langle{{n-ik}\choose{i-1}}\right\rangle
2^{n+1-i(k+1)}}$
$\displaystyle+\sum_{i\in\mathbb{Z}}{(-1)^{i}\left\langle{{n-j-1-ik}\choose{i-1}}\right\rangle
2^{n-j-i(k+1)}}\mbox{ for all }n\in\mathbb{Z}.$

Proof. By Theorem 3(vii),
$B^{(j)}=\frac{1}{k-1}(\mathtt{I}-\mathtt{R}^{j+1})(S)$, thus, using the
formula (7) for $S_{n}$ in Theorem 5, we obtain the desired formula for
$B^{(j)}_{n}$. $\blacksquare$

The formula (8) for $S_{n}$ in Theorem 6 is equivalent to a formula in
Ferguson [8] (formula (3) for $V_{n,a(n+1)+b}$). Theorem 7 for the case
$j=k-1$ and positive indices is proved in Benjamin et al. [1].

##  4 Explicit formula based on multinomials

In this section, we will derive explicit formula for the two-sided Fibonacci
basis sequences $B^{(0)},B^{(1)},\dots,B^{(k-1)}$ expressed in terms of
multinomial coefficients. Since the traditional multinomial notation is
associated with non-negative integers, to use these for our two-sided
sequences we need to extend the multinomial notation to include negative
integers. To this end, we extend the multinomial notation
${n\choose{i_{1},i_{2},\dots,i_{t}}}$ to negative values of $n$ and
$i_{1},i_{2},\dots,i_{t}$.

A multinomial is defined as

$\displaystyle(i_{1},i_{2},\dots,i_{t})$
$\displaystyle={{i_{1}+i_{2}+\dots+i_{t}}\choose{i_{1},i_{2},\dots,i_{t}}}=\frac{(i_{1}+i_{2}+\dots+i_{t})!}{i_{1}!i_{2}!\dots
i_{t}!}.$

We observe that

$(i_{1},i_{2},\dots,i_{t})={{i_{1}+\dots+i_{t}}\choose{i_{2}+\dots+i_{t}}}{{i_{2}+\dots+i_{t}}\choose{i_{3}+\dots+i_{t}}}\dots{i_{t-2}+i_{t-1}+i_{t}}\choose{i_{t-1}+i_{t}}{{i_{t-1}+i_{t}}\choose{i_{t}}}.$

We will use this formula to extend multinomial notation for negative integers.

######  Definition 3.

Let $t\geq 2$ be an integer. For any integers $i_{1},i_{2},\dots,i_{t}$, the
generalized multinomial $\left\langle(i_{1},i_{2},\dots,i_{t})\right\rangle$
is defined as

$\displaystyle\left\langle(i_{1},i_{2},\dots,i_{t})\right\rangle=\left\langle{{i_{1}+i_{2}+\dots+i_{t}}\choose{i_{1},i_{2},\dots,i_{t}}}\right\rangle$
$\displaystyle=\left\langle{{i_{1}+\dots+i_{t}}\choose{i_{2}+\dots+i_{t}}}\right\rangle\left\langle{{i_{2}+\dots+i_{t}}\choose{i_{3}+\dots+i_{t}}}\right\rangle\dots\left\langle{{i_{t-2}+i_{t-1}+i_{t}}\choose{i_{t-1}+i_{t}}}\right\rangle\left\langle{{i_{t-1}+i_{t}}\choose{i_{t}}}\right\rangle.$

Using the following formula for the generalized binomial coefficient

$\displaystyle\left\langle{{n}\choose{i}}\right\rangle$
$\displaystyle=\begin{cases}\frac{n^{\underline{n-i}}}{(n-i)!}=\frac{n(n-1)(n-2)\dots(i+1)}{(n-i)!},&\text{if
}n\geq i\\\ 0,&\text{otherwise}\end{cases},$

we obtain the following formula for the generalized multinomial

$\displaystyle\left\langle(i_{1},i_{2},\dots,i_{t})\right\rangle=\left\langle{{i_{1}+i_{2}+\dots+i_{t}}\choose{i_{1},i_{2},\dots,i_{t}}}\right\rangle$
$\displaystyle=\begin{cases}\cfrac{(i_{1}+\dots+i_{t})^{\underline{i_{1}}}(i_{2}+\dots+i_{t})^{\underline{i_{2}}}\dots(i_{t-1}+i_{t})^{\underline{i_{t-1}}}}{i_{1}!i_{2}!\dots
i_{t-1}!},&\text{if }i_{1},i_{2},\dots,i_{t-1}\geq 0\\\
0,&\text{otherwise}\end{cases}.$

When $t=2$, the Pascal Recursion relation becomes

$\displaystyle\left\langle(i_{1},i_{2})\right\rangle=\left\langle(i_{1}-1,i_{2})\right\rangle+\left\langle(i_{1},i_{2}-1)\right\rangle.$

For a general $t\geq 2$, we have the following generalized Pascal Recursion
relation for multinomials:

$\displaystyle\left\langle(i_{1},i_{2},\dots,i_{t})\right\rangle$
$\displaystyle=\left\langle(i_{1}-1,i_{2},\dots,i_{t})\right\rangle+\left\langle(i_{1},i_{2}-1,\dots,i_{t})\right\rangle+\dots+\left\langle(i_{1},i_{2},\dots,i_{t}-1)\right\rangle.$
(10)

Since $\left\langle{n\choose i}\right\rangle$ is non-zero only for $n\geq
i\geq 0$ or $-1\geq n\geq i$, the generalized multinomial
$\left\langle(i_{1},i_{2},\dots,i_{t})\right\rangle$ is non-zero only for
$i_{1}+\dots+i_{t}\geq i_{2}+\dots+i_{t}\geq\dots\geq i_{t-1}+i_{t}\geq
i_{t}\geq 0$ or $-1\geq i_{1}+\dots+i_{t}\geq i_{2}+\dots+i_{t}\geq\dots\geq
i_{t-1}+i_{t}\geq i_{t}$. Using the formula (5) for $\left\langle{n\choose
i}\right\rangle$, we can derive the formula for the generalized multinomial in
these two separate cases.

Case 1. If $i_{1}+\dots+i_{t}\geq i_{2}+\dots+i_{t}\geq\dots\geq
i_{t-1}+i_{t}\geq i_{t}\geq 0$, i.e. $i_{1},i_{2},\dots,i_{t}\geq 0$, then

$\displaystyle\left\langle(i_{1},i_{2},\dots,i_{t})\right\rangle=\left\langle{{i_{1}+i_{2}+\dots+i_{t}}\choose{i_{1},i_{2},\dots,i_{t}}}\right\rangle={{i_{1}+i_{2}+\dots+i_{t}}\choose{i_{1},i_{2},\dots,i_{t}}}=(i_{1},i_{2},\dots,i_{t}).$

Case 2. If $-1\geq i_{1}+\dots+i_{t}\geq i_{2}+\dots+i_{t}\geq\dots\geq
i_{t-1}+i_{t}\geq i_{t}$ then

$\displaystyle\left\langle(i_{1},i_{2},\dots,i_{t})\right\rangle$
$\displaystyle=\left\langle{{i_{1}+i_{2}+\dots+i_{t}}\choose{i_{1},i_{2},\dots,i_{t}}}\right\rangle$
$\displaystyle=(-1)^{i_{1}+\dots+i_{t-1}}{{-i_{t}-1}\choose{i_{1},i_{2},\dots,i_{t-1},-i_{1}-\dots-
i_{t}-1}}$
$\displaystyle=(-1)^{i_{1}+\dots+i_{t-1}}(i_{1},i_{2},\dots,i_{t-1},-i_{1}-\dots-
i_{t}-1).$

Thus, we obtain the following theorem that connects the generalized
multinomial to the classical multinomial.

######  Theorem 8.

For any integer $t\geq 2$ and $i_{1},i_{2},\dots,i_{t}\in\mathbb{Z}$, we have

$\displaystyle\left\langle(i_{1},i_{2},\dots,i_{t})\right\rangle$
$\displaystyle=\begin{cases}(i_{1},i_{2},\dots,i_{t}),&\text{if
}i_{1},i_{2},\dots,i_{t}\geq 0\\\
(-1)^{i_{1}+\dots+i_{t-1}}(i_{1},i_{2},\dots,i_{t-1},-i_{1}-\dots-
i_{t}-1)&\text{if }i_{1},i_{2},\dots,i_{t-1}\geq 0\mbox{ and
}i_{1}+\dots+i_{t}\leq-1\\\ 0,&\text{otherwise.}\end{cases}$

In the following theorem, we define an auxiliary sequence
$\\{X_{n}\\}_{n\in\mathbb{Z}}$. Note that $X$ is a member of the linear space
$\mathsf{Fibonacci}^{(k)}$.

######  Theorem 9.

Let $k\geq 2$, $c\in\mathbb{Z}$ any constant, and

$\displaystyle X_{n}$
$\displaystyle=\sum_{a_{1}+2a_{2}+\dots+ka_{k}=n+c}{\left\langle(a_{1},a_{2},\dots,a_{k})\right\rangle}$
$\displaystyle=\sum_{s_{1}+s_{2}+\dots+s_{k}=n+c}{\left\langle{s_{1}\choose
s_{2}}\right\rangle\left\langle{s_{2}\choose
s_{3}}\right\rangle\dots\left\langle{s_{k-1}\choose s_{k}}\right\rangle}.$

Then $\\{X_{n}\\}_{n\in\mathbb{Z}}$ is a Fibonacci sequence of order $k$.

Proof. The two formulas on the RHS are equivalent by using the variables
$s_{1}=a_{1}+\dots+a_{k}$, $s_{2}=a_{2}+\dots+a_{k}$, …,
$s_{k-1}=a_{k-1}+a_{k}$ and $s_{k}=a_{k}$.

Note that the summation only has a finite number of non-zero terms. This is
because $\left\langle(a_{1},a_{2},\dots,a_{k})\right\rangle$ is non-zero only
if $s_{1}\geq s_{2}\geq\dots\geq s_{k}\geq 0$ or $-1\geq s_{1}\geq
s_{2}\geq\dots\geq s_{k}$, and there are only a finite number of choices for
$s_{1},s_{2},\dots,s_{k}$ that have the same sign whose sum
$s_{1}+s_{2}+\dots+s_{k}=n+c$ is fixed.

By Pascal Recursion relation (10),

$\displaystyle X_{n}=$
$\displaystyle\sum_{a_{1}+2a_{2}+\dots+ka_{k}=n+c}{\left\langle(a_{1}-1,a_{2},\dots,a_{k})\right\rangle}$
$\displaystyle+\sum_{a_{1}+2a_{2}+\dots+ka_{k}=n+c}{\left\langle(a_{1},a_{2}-1,\dots,a_{k})\right\rangle}$
$\displaystyle+\dots+\sum_{a_{1}+2a_{2}+\dots+ka_{k}=n+c}{\left\langle(a_{1},a_{2},\dots,a_{k}-1)\right\rangle}.$

Let $a_{1}^{\prime}=a_{1}-1$, $a_{2}^{\prime}=a_{2}-1$, …,
$a_{k}^{\prime}=a_{k}-1$. We have

$\displaystyle X_{n}=$
$\displaystyle\sum_{a_{1}^{\prime}+2a_{2}+\dots+ka_{k}=n+c-1}{\left\langle(a_{1}^{\prime},a_{2},\dots,a_{k})\right\rangle}$
$\displaystyle+\sum_{a_{1}+2a_{2}^{\prime}+\dots+ka_{k}=n+c-2}{\left\langle(a_{1},a_{2}^{\prime},\dots,a_{k})\right\rangle}$
$\displaystyle+\dots+\sum_{a_{1}+2a_{2}+\dots+ka_{k}^{\prime}=n+c-k}{\left\langle(a_{1},a_{2},\dots,a_{k}^{\prime})\right\rangle}$
$\displaystyle=X_{n-1}+X_{n-2}+\dots+X_{n-k},$

therefore, $\\{X_{n}\\}$ is a Fibonacci sequence of order $k$. $\blacksquare$

######  Theorem 10.

Let $k\geq 2$. Then

$B_{n}^{(0)}=\sum_{a_{1}+2a_{2}+\dots+ka_{k}=n-k}{\left\langle(a_{1},a_{2},\dots,a_{k})\right\rangle},\mbox{
for all }n\in\mathbb{Z}.$ (11)

Proof. Let $B^{\prime}$ denote the RHS, then by Theorem 9, $B^{\prime}$ is a
Fibonacci sequence. We only need to show its initial values match with those
of $B^{(0)}$.

Again, as in the proof of Theorem 9, we use the variables
$s_{1}=a_{1}+\dots+a_{k}$, $s_{2}=a_{2}+\dots+a_{k}$, …,
$s_{k-1}=a_{k-1}+a_{k}$ and $s_{k}=a_{k}$, then $s_{1}+s_{2}+\dots+s_{k}=n-k$.
When $n=0$, $s_{1}+s_{2}+\dots+s_{k}=-k<0$, so
$\left\langle(a_{1},a_{2},\dots,a_{k})\right\rangle$ is non-zero only if
$-1\geq s_{1}\geq s_{2}\geq\dots\geq s_{k}$. The only possibility is
$s_{1}=s_{2}=\dots=s_{k}=-1$ and this gives $a_{1}=a_{2}=\dots=a_{k-1}=0$,
$a_{k}=-1$ and $B^{\prime}_{0}=\left\langle(0,\dots,0,-1)\right\rangle=1$.

When $1\leq n\leq k-1$, $-(k-1)\leq s_{1}+s_{2}+\dots+s_{k}=n-k<0$. There are
no such $-1\geq s_{1}\geq s_{2}\geq\dots\geq s_{k}$ that satisfy this
condition, so the summation is empty and $B^{\prime}_{n}=0$ for $1\leq n\leq
k-1$. $\blacksquare$

######  Theorem 11.

Let $k\geq 2$. Then

$B_{n}^{(k-1)}=\sum_{a_{1}+2a_{2}+\dots+ka_{k}=n-k+1}{\left\langle(a_{1},a_{2},\dots,a_{k})\right\rangle},\mbox{
for all }n\in\mathbb{Z}.$

Proof. By Theorem 3(iii), $B^{(k-1)}=\mathtt{L}(B^{(0)})$, so using the
formula for $B^{(0)}_{n}$ in Theorem 10 we obtain the desired formula for
$B^{(k-1)}_{n}$. $\blacksquare$

The formula in Theorem 11 is proved in Miles [18] for natural number $n\geq
k-1$. Our Theorem 11 extends it to $n<k-1$ and negative integer $n$.

The Tribonacci sequence $\\{T_{n}\\}_{n\geq 0}$ studied in Rabinowitz [20] is
a Fibonacci sequence of order $k=3$ with initial values $T_{0}=0$, $T_{1}=1$,
$T_{2}=1$. Solving for $T_{-1}$, we have $T_{-1}=0$, so
$T=\mathtt{L}(B^{(2)})$. The formula in Theorem 11 is proved in Rabinowitz
[20] for $k=3$ and $n\geq 2$. Our Theorem 11 extends it to all order $k\geq 2$
and all index $n\in\mathbb{Z}$.

The next theorem give an explicit formula for all basis Fibonacci sequences of
order $k$.

######  Theorem 12.

Let $k\geq 2$. For any $0\leq j\leq k-1$,

$B_{n}^{(j)}=\sum_{n-k-j\leq a_{1}+2a_{2}+\dots+ka_{k}\leq
n-k}{\left\langle(a_{1},a_{2},\dots,a_{k})\right\rangle},\mbox{ for all
}n\in\mathbb{Z}.$

Proof. By Theorem 3(ii), $B^{(j)}=\sum_{i=0}^{j}\mathtt{R}^{i}(B^{(0)})$, so
using the formula for $B^{(0)}_{n}$ in Theorem 10 we obtain the desired
formula for $B^{(j)}_{n}$. $\blacksquare$

Theorem 11 and Theorem 12 give rise to two different formulas for the sequence
$B^{(k-1)}$. It would be interesting to see a combinatorial proof of the
equality of these two formulas.

##  5 A remark on a tiling problem

It is well known that the classical Fibonacci sequence, $F_{0}=0$, $F_{1}=1$,
$F_{n}=F_{n-1}+F_{n-2}$, has a close relation with the tiling problem. The
value $F_{n}$ counts the number of tilings of an $1\times n$-board with
square-tiles $1\times 1$ and domino-tiles $1\times 2$. This is because for
$n\geq 2$, by considering the first tile, if the first tile is a square then
there are $F_{n-1}$ ways to cover the remaining strip of length $n-1$, and if
the first tile is a domino then there are $F_{n-2}$ ways to cover the
remaining strip of length $n-2$. That is how the recursion equation
$F_{n}=F_{n-1}+F_{n-2}$ arises.

If we allow tiles of length up to $k$, then the result is a sequence
$\\{C_{n}\\}_{n\geq 0}$. We have $C_{0}=0$, $C_{1}=1$, $C_{2}=C_{0}+C_{1}$,
$C_{3}=C_{0}+C_{1}+C_{2}$,…, $C_{k-1}=C_{0}+C_{1}+\dots+C_{k-2}$, and for
$n\geq k$, $C_{n}=C_{n-1}+C_{n-2}+\dots+C_{n-k}$. Of course, if we extend the
index to negative integers and set $C_{-1}=C_{-2}=\dots=C_{-(k-2)}=0$ then we
have the Fibonacci recursion equation $C_{n}=C_{n-1}+C_{n-2}+\dots+C_{n-k}$
holds for all $n\geq 2$. This sequence $C$ is just a left shift of the basis
sequence $B^{(k-1)}$. Indeed, $C=\mathtt{R}^{k-2}(B^{(k-1)})$. Many authors
such as Gabai, Philippou, Muwafi, Benjamin, Heberle, Quinn and Su [19, 9, 1,
2] have studied this tiling problem and here we decide to use the letter $C$
to denote this sequence since it is related to a combinatorial problem.

## References

  * [1] A. T. Benjamin and C. R. Heberle, Counting on $r$-Fibonacci numbers, Fibonacci Quarterly 52(2), 121–128, 2014.
  * [2] A. T. Benjamin, J. J. Quinn and F. E. Su, Phased tilings and generalized Fibonacci identities, Fibonacci Quarterly 38(3), 282–289, 2000.
  * [3] M. Bunder and J. Tonien, Generalized Fibonacci numbers and their 2-adic order, Integers, 20, #A105, 2020.
  * [4] A. P. Chaves and D. Marques, A Diophantine equation related to the sum of squares of consecutive $k$-generalized Fibonacci numbers, Fibonacci Quarterly 52(1), 70–74, 2014.
  * [5] T. W. Cusick, On a certain integer associated with a generalized Fibonacci sequence, Fibonacci Quarterly 6(2), 117–126, 1968.
  * [6] M. Ddamulira, C. A. Gomez and F. Luca, On a problem of Pillai with $k$–generalized Fibonacci numbers and powers of 2, Monatshefte fur Mathematik 187, 635–664, 2018.
  * [7] T. P. Dence, Ratios of generalized Fibonacci sequences, Fibonacci Quarterly 25(2), 137–143, 1987.
  * [8] D. E. Ferguson, An expression for generalized Fibonacci numbers, Fibonacci Quarterly 4(3), 270–272, 1966.
  * [9] H. Gabai, Generalized Fibonacci $k$-sequences, Fibonacci Quarterly, 8(1), 31–38, 1970.
  * [10] F. T. Howard and C. Cooper, Some identities for $r$-Fibonacci numbers, Fibonacci Quarterly, 49(3), 231–242, 2011.
  * [11] D. Kessler and J. Schiff, A combinatoric proof and generalization of Ferguson’s formula for $k$-generalized Fibonacci numbers, Fibonacci Quarterly 42(3), 266–273, 2004.
  * [12] I. I. Kolodner, On a generating function associated with generalized Fibonacci sequences, Fibonacci Quarterly 3(4), 272–278, 1965.
  * [13] G-Y. Lee, S-G. Lee, J-S. Kim, and H-K. Shin, The Binet formula and representations of k-generalized Fibonacci numbers, Fibonacci Quarterly, 39(2), 158–164, 2001
  * [14] T. Lengyel and D. Marques, The 2-adic order of some generalized Fibonacci numbers, Integers 17(2017), #A5.
  * [15] D. E. Loeb, Sets with a negative number of elements, Advances in Mathematics, 91(1), 64–74, 1992.
  * [16] D. E. Loeb, A generalization of the binomial coefficients, Discrete Mathematics, 105(1–3), 143–156, 1992.
  * [17] R. S. Melham, Certain classes on finite sums that involve generalized Fibonacci and Lucas numbers, Fibonacci Quarterly 42(1), 47–54, 2004.
  * [18] E. P. Miles Jr, Generalized Fibonacci numbers and associated matrices, The American Mathematical Monthly, 67(8), 745–752, 1960.
  * [19] A. N. Philippou and A. A. Muwafi, Waiting for the $k$th consecutive success and the Fibonacci sequence of order $k$, Fibonacci Quarterly 20(1), 28–32, 1982.
  * [20] S. Rabinowitz, Algorithmic manipulation of third-order linear recurrences, Fibonacci Quarterly 34(5), 447–464, 1996.
  * [21] B. Sobolewski, The 2-adic valuation of generalized Fibonacci sequences with an application to certain Diophantine equations, Journal of Number Theory, 180, 730–742, 2017.