% -------------------------------------------------------------
% NOTES ON SOME HACKS USED IN THIS FILE:
% -------------------------------------------------------------
% One of my pet peeves with amsthm is its use of italics in the theorem and
% proposition environments; this makes math and text indistinguishable in said
% enviroments. To avoid this, I redefine the enviroments to use the standard
% font and to use a hanging indent, along with a bold vertical bar to its
% left, to distinguish these environments from surrounding text. (Along with
% the advantage of distinguishing math from text, this also allows nesting
% several such environments inside each other, like a definition inside a
% remark. I'm not sure how good of an idea this is, though. There are also
% downsides related to the hanging indentation, such as footnotes out of it
% being painful to do right.) This is done starting from the line
% \theoremstyle{definition}
% and until the line
% {\end{leftbar}\end{exmp}}
\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage[breaklinks=true]{hyperref}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Monday, June 11, 2018 00:05:20}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\newcounter{exera}
\numberwithin{exer}{section}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\ihead{Zeckendorf family identities generalized (long version)}
\ohead{page \thepage}
\cfoot{}
\begin{document}
\title{Zeckendorf family identities generalized}
\author{Darij Grinberg}
\date{
%TCIMACRO{\TeXButton{today}{\today}}%
%BeginExpansion
\today
%EndExpansion
, long version}
\maketitle
\begin{abstract}
\textbf{Abstract.} In \cite{1}, Philip Matchett Wood and Doron Zeilberger have
constructed identities for the Fibonacci numbers $f_{n}$ of the form%
\begin{align*}
1f_{n} & =f_{n}\text{ for all }n\geq1;\\
2f_{n} & =f_{n-2}+f_{n+1}\text{ for all }n\geq3;\\
3f_{n} & =f_{n-2}+f_{n+2}\text{ for all }n\geq3;\\
4f_{n} & =f_{n-2}+f_{n}+f_{n+2}\text{ for all }n\geq3;\\
& \text{etc.;}\\
kf_{n} & =\sum_{s\in S_{k}}f_{n+s}\text{ for all }n>\max\left\{ -s\mid s\in
S_{k}\right\} \text{,}%
\end{align*}
where $S_{k}$ is a fixed ``lacunar'' set of integers (``lacunar'' means that
no two elements of this set are consecutive integers) depending only on $k$.
(The condition $n>\max\left\{ -s\mid s\in S_{k}\right\} $ is only to make
sure that all addends $f_{n+s}$ are well-defined. If the Fibonacci sequence is
properly continued to the negative, this condition drops out.)\newline In this
note we prove a generalization of these identities: For any family $\left(
a_{1},a_{2},\ldots,a_{p}\right) $ of integers, there exists one and only one
finite lacunar set $S$ of integers such that every $n$ (high enough to make
the Fibonacci numbers in the equation below well-defined) satisfies
\[
f_{n+a_{1}}+f_{n+a_{2}}+\cdots+f_{n+a_{p}}=\sum\limits_{s\in S}f_{n+s}.
\]
The proof uses the Fibonacci-approximating properties of the golden ratio. It
would be interesting to find a purely combinatorial proof.
\end{abstract}
%NOT proofreading completed
\hrule
\begin{statement}
This is a detailed version of my note \cite{this.short}. It contains the proof
outlined in \cite{this.short} in much more detail and was written for the
purpose of persuading myself that my proofs are correct.
\end{statement}
\hrule
\section{The main result}
The purpose of this note is to establish a generalization of the so-called
\textit{Zeckendorf family identities} which were discussed in \cite{1}. Before
we can state it, we need a few definitions:
\begin{definition}
A subset $S$ of $\mathbb{Z}$ is called \textit{lacunar} if it satisfies
$\left( s+1\notin S\text{ for every }s\in S\right) $.
\end{definition}
In other words, a subset $S$ of $\mathbb{Z}$ is lacunar if and only if it
contains no two consecutive integers.
\begin{definition}
\label{def.fib}The \textit{Fibonacci sequence} $\left( f_{1},f_{2}%
,f_{3},\ldots\right) $ is a sequence of positive integers defined recursively
by the initial values $f_{1}=1$ and $f_{2}=1$ and the recurrence relation
$\left( f_{n}=f_{n-1}+f_{n-2}\text{ for all }n\in\mathbb{N}\text{ satisfying
}n\geq3\right) $.
\end{definition}
(Here and in the following, $\mathbb{N}$ denotes the set $\left\{
0,1,2,\ldots\right\} $.)
\begin{remark}
Many authors define the Fibonacci sequence slightly differently: They define
it as a sequence $\left( f_{0},f_{1},f_{2},\ldots\right) $ of nonnegative
integers defined recursively by the initial values $f_{0}=0$ and $f_{1}=1$ and
the recurrence relation $\left( f_{n}=f_{n-1}+f_{n-2}\text{ for all }%
n\in\mathbb{N}\text{ satisfying }n\geq2\right) $. Thus, this sequence begins
with a $0$, unlike the Fibonacci sequence defined in our Definition
\ref{def.fib}. However, starting at its second term $f_{1}=1$, this sequence
takes precisely the same values as the Fibonacci sequence defined in our
Definition \ref{def.fib} (because both sequences satisfy $f_{1}=1$ and
$f_{2}=1$, and from here on the recurrence relation ensures that their values
remain equal). So it differs from the latter sequence only in the presence of
one extra term $f_{0}=0$ at the front.
\end{remark}
The Fibonacci sequence is one of the best known integer sequences from
combinatorics. It has had conferences, books and a journal devoted to it. By
way of example, let us only mention Vorobiev's book \cite{Vorobi02}, which is
entirely concerned with Fibonacci numbers, and Benjamin's and Quinn's text
\cite{BenQui03} on bijective proofs, which includes many identities for
Fibonacci numbers.
In \cite{1}, Wood and Zeilberger discuss bijective proofs of the so-called
\textit{Zeckendorf family identities}. These identities are a family of
identities for Fibonacci numbers (one for each positive integer); the first
seven of these identities are%
\begin{align*}
1f_{n} & =f_{n}\text{ for all }n\geq1;\\
2f_{n} & =f_{n-2}+f_{n+1}\text{ for all }n\geq3;\\
3f_{n} & =f_{n-2}+f_{n+2}\text{ for all }n\geq3;\\
4f_{n} & =f_{n-2}+f_{n}+f_{n+2}\text{ for all }n\geq3;\\
5f_{n} & =f_{n-4}+f_{n-1}+f_{n+3}\text{ for all }n\geq5;\\
6f_{n} & =f_{n-4}+f_{n+1}+f_{n+3}\text{ for all }n\geq5;\\
7f_{n} & =f_{n-4}+f_{n+4}\text{ for all }n\geq5.
\end{align*}
In general, for each positive integer $k$, the $k$-th Zeckendorf family
identity expresses $kf_{n}$ (for each sufficiently large integer $n$) as a sum
of the form $\sum\limits_{s\in S}f_{n+s}$, where $S$ is a finite lacunar
subset of $\mathbb{Z}$. Of course, the subset $S$ does not depend on $n$.
Our main theorem is the following:
\begin{theorem}
[generalized Zeckendorf family identities]\label{thm.1} Let $T$ be a finite
set, and let $a_{t}$ be an integer for every $t\in T$.
Then, there exists one and only one finite lacunar subset $S$ of $\mathbb{Z}$
such that\footnotemark%
\[
\left(
\begin{array}
[c]{c}%
\sum\limits_{t\in T}f_{n+a_{t}}=\sum\limits_{s\in S}f_{n+s}\text{ for every
}n\in\mathbb{Z}\text{ which}\\
\text{satisfies }n>\max\left( \left\{ -a_{t}\mid t\in T\right\}
\cup\left\{ -s\mid s\in S\right\} \right)
\end{array}
\right) .
\]
\end{theorem}
\footnotetext{Here and in the following, $\max\varnothing$ is understood to be
$0$.}
\begin{remark}
\begin{enumerate}
\item Theorem~\ref{thm.1} generalizes the Zeckendorf family identities (which
correspond to the case when all $a_{t}$ are $=0$).
\item The condition $n>\max\left( \left\{ -a_{t}\mid t\in T\right\}
\cup\left\{ -s\mid s\in S\right\} \right) $ in Theorem~\ref{thm.1} is just
a technical condition made in order to ensure that the Fibonacci numbers
$f_{n+a_{t}}$ for all $t\in T$ and $f_{n+s}$ for all $s\in S$ are
well-defined. (If we would define the Fibonacci numbers $f_{n}$ for integers
$n\leq0$ by extending the recurrence relation $f_{n}=f_{n-1}+f_{n-2}$ ``to the
left'', then we could drop this condition.)
\end{enumerate}
\end{remark}
The proof we shall give for Theorem~\ref{thm.1} is not combinatorial. It will
use inequalities and the properties of the golden ratio; in a sense, its
underlying ideas come from analysis (although it will not actually use any
results from analysis).
\section{Basics on the Fibonacci sequence}
We begin with some lemmas and notations:
We denote by $\mathbb{N}$ the set $\left\{ 0,1,2,\ldots\right\} $ (and not
the set $\left\{ 1,2,3,\ldots\right\} $, like some other authors do). Also,
we denote by $\mathbb{N}_{2}$ the set $\left\{ 2,3,4,\ldots\right\}
=\mathbb{N}\setminus\left\{ 0,1\right\} $.
Also, let $\phi=\dfrac{1+\sqrt{5}}{2}$. This number $\phi$ is known as the
\textit{golden ratio}. We notice that $\phi\approx1.618\ldots$ and that
$\phi^{2}=\phi+1$. Binet's formula states that $f_{n}=\dfrac{\phi^{n}%
-\phi^{-n}}{\sqrt{5}}$ for every positive integer $n$. (See, e.g.,
\cite[Identity 240]{BenQui03} or \cite[(1.20)]{Vorobi02} for proofs of Binet's formula.)
We observe that the Fibonacci sequence $\left( f_{1},f_{2},f_{3}%
,\ldots\right) $ consists of positive integers (indeed, its two starting
values $f_{1}=1$ and $f_{2}=1$ are positive integers, and thus the recurrence
relation $f_{n}=f_{n-1}+f_{n-2}$ clearly ensures that all the following values
are also positive integers). Thus, $f_{n} > 0$ for each positive integer $n$.
Now, for each integer $n \geq2$, we have $f_{n-1} > 0$ (since the Fibonacci
sequence $\left( f_{1},f_{2},f_{3},\ldots\right) $ consists of positive
integers). The recurrence relation of the Fibonacci sequence shows that for
each integer $n \geq2$, we have $f_{n+1} = f_{n} + f_{n-1} > f_{n}$ (because
$f_{n-1} > 0$), so that $f_{n} < f_{n+1}$. In other words, $f_{2} < f_{3} <
f_{4} < \cdots$. In other words, the Fibonacci sequence is strictly increasing
beginning with its second term $f_{2}$. Furthermore, $f_{1} = 1 = f_{2}$, so
that $f_{1} = f_{2} < f_{2} < f_{3} < f_{4} < \cdots$. Hence, the Fibonacci
sequence is weakly increasing.
We recall some basic and well-known facts about the Fibonacci sequence:
\begin{lemma}
\label{lem.2} Let $S$ be a finite lacunar subset of $\mathbb{N}_{2}$. Then,
$\sum\limits_{t\in S}f_{t}0$.
On the other hand, every $i\in\left\{ 1,2,\ldots,k-1\right\} $ satisfies
$s_{i}+1\leq s_{i+1}-1$\ \ \ \ \footnote{\textit{Proof.} Let $i\in\left\{
1,2,\ldots,k-1\right\} $. Thus, both $i$ and $i+1$ belong to $\left\{
1,2,\ldots,k\right\} $.
\par
The set $S$ is lacunar, and thus $s+1\notin S$ for every $s\in S$. Applying
this to $s=s_{i}$, we get $s_{i}+1\notin S$ (since $s_{i}\in\left\{
s_{1},s_{2},\ldots,s_{k}\right\} =S$), so that $s_{i}+1\neq s_{i+1}$ (since
$s_{i+1}\in\left\{ s_{1},s_{2},\ldots,s_{k}\right\} =S$).
\par
Since $s_{1}0\right) \\
& =f_{\max S+1}%
\end{align*}
(since $s_{k}=\max S$). This proves Lemma~\ref{lem.2}.
\end{proof}
\begin{lemma}
[existence part of the Zeckendorf theorem]\label{lem.3} Let $n \in\mathbb{N}$.
Then, there exists a finite lacunar subset $T$ of $\mathbb{N}_{2}$ such that
$n=\sum\limits_{t\in T}f_{t}$.
\end{lemma}
\begin{proof}
[Proof of Lemma~\ref{lem.3}.]We are going to prove Lemma~\ref{lem.3} by strong
induction over $n$:
\textit{Induction base:} Let $n=0$. Then, there exists a finite lacunar subset
$T$ of $\mathbb{N}_{2}$ such that $n=\sum\limits_{t\in T}f_{t}$ (namely,
$T=\varnothing$), and thus Lemma~\ref{lem.3} holds for $n=0$, and the
induction base is completed.
\textit{Induction step:} Let $\nu\in\mathbb{N}$ be such that $\nu>0$. Assume
that Lemma~\ref{lem.3} holds for every nonnegative integer $n<\nu$. We must
now prove that Lemma~\ref{lem.3} holds for $n=\nu$.
In fact, we have $\nu>0$, so that $\nu\geq1$ (since $\nu$ is an integer).
Thus, $f_{2}=1\leq\nu$.
Let $t_{1}$ be the maximal integer $\tau$ from $\mathbb{N}_{2}$ satisfying
$f_{\tau}\leq\nu$\ \ \ \ \footnote{Such an integer $t_{1}$ exists, because of
the following:
\par
The Fibonacci sequence $\left( f_{1},f_{2},f_{3},\ldots\right) $ is strictly
increasing beginning with $f_{2}$ and therefore unbounded from above (because
every strictly increasing sequence of integers is unbounded from above).
Hence, \textquotedblleft sooner or later\textquotedblright\ this sequence will
surpass any given integer. Thus, in particular, there are \textbf{only
finitely many} integers $\tau$ from $\mathbb{N}_{2}$ satisfying $f_{\tau}%
\leq\nu$.
\par
On the other hand, $2$ is an integer $\tau$ from $\mathbb{N}_{2}$ satisfying
$f_{\tau}\leq\nu$ (since $f_{2}\leq\nu$). Hence, there exists \textbf{at least
one} integer $\tau$ from $\mathbb{N}_{2}$ satisfying $f_{\tau}\leq\nu$. Thus,
there exists a \textbf{maximal integer} $\tau$ from $\mathbb{N}_{2}$
satisfying $f_{\tau}\leq\nu$ (because we have already shown that there are
\textbf{only finitely many} integers $\tau$ from $\mathbb{N}_{2}$ satisfying
$f_{\tau}\leq\nu$). This is what we wanted to prove.}. Then, $f_{t_{1}}\leq
\nu$ but $f_{t_{1}+1}>\nu$ (since $t_{1}$ is maximal). Hence, $\nu-f_{t_{1}}$
is a nonnegative integer (since $f_{t_{1}}\leq\nu$) and $<\nu$ (since
$f_{t_{1}}>0$). Thus, Lemma~\ref{lem.3} holds for $n=\nu-f_{t_{1}}$ (since we
assumed that Lemma~\ref{lem.3} holds for every nonnegative integer $n<\nu$).
In other words, there exists a finite lacunar subset $T$ of $\mathbb{N}_{2}$
such that $\nu-f_{t_{1}}=\sum\limits_{t\in T}f_{t}$. We rename this subset $T$
as $S$ (so as not to confuse it with the set $T$ that we want to construct for
$n=\nu$). Thus, we have a finite lacunar subset $S$ of $\mathbb{N}_{2}$ such
that $\nu-f_{t_{1}}=\sum\limits_{t\in S}f_{t}$.
The relation $f_{n}=f_{n-1}+f_{n-2}$ (applied to $n=t_{1}+1$) yields
$f_{t_{1}+1}=f_{t_{1}}+f_{t_{1}-1}$, so that $f_{t_{1}+1}-f_{t_{1}}%
=f_{t_{1}-1}$. Now, from $\nu\max S+1>\max S$, and thus $t_{1}\notin S$
(because if an integer $x$ satisfies $x>\max S$, then $x\notin S$). Also,
$t_{1}+1>t_{1}>\max S$, so that $t_{1}+1\notin S$ (because if an integer $x$
satisfies $x>\max S$, then $x\notin S$). Combining $t_{1}+1\notin S$ with
$t_{1}+1\notin\left\{ t_{1}\right\} $ (which is obvious), we obtain
$t_{1}+1\notin S\cup\left\{ t_{1}\right\} $.
Again, let $s\in S$. From (\ref{pf.lem.3.ineq1}), we obtain $s+1 0$. This
contradicts $\sum\limits_{t\in T}f_{t} = n = 0$. This contradiction shows that
our assumption was wrong, qed.}. Similarly, $T^{\prime}=\varnothing$.
Comparing this with $T = \varnothing$, we obtain $T=T^{\prime}$. Hence, we
have shown that Lemma~\ref{lem.4} holds for $n=0$, and the induction base is completed.
\textit{Induction step:} Let $\nu\in\mathbb{N}$ be such that $\nu>0$. Assume
that Lemma~\ref{lem.4} holds for every nonnegative integer $n<\nu$. We must
now prove that Lemma~\ref{lem.4} holds for $n=\nu$.
So let $T$ and $T^{\prime}$ be two finite lacunar subsets of $\mathbb{N}_{2}$
such that $\nu=\sum\limits_{t\in T}f_{t}$ and $\nu=\sum\limits_{t\in
T^{\prime}}f_{t}$. Then, we want to prove that $T=T^{\prime}$.
Since $\sum\limits_{t\in T}f_{t}=\nu>0$, we have $T\neq\varnothing$. Thus,
$\max T\in T$. Similarly, $\max T^{\prime}\in T^{\prime}$.
But $f_{\max T}$ is an addend in the sum $\sum\limits_{t\in T}f_{t}$ (since
$\max T \in T$). Since the Fibonacci numbers $f_{t}$ are all nonnegative, we
thus obtain $f_{\max T}\leq\sum\limits_{t\in T}f_{t}=\nu=\sum\limits_{t\in
T^{\prime}}f_{t} 0$), we can thus apply Lemma~\ref{lem.4}
to $\nu-f_{\mu}$ instead of $n$ and to the lacunar subsets $S$ and $S^{\prime
}$ instead of $T$ and $T^{\prime}$ (since we assumed that Lemma~\ref{lem.4}
holds for every nonnegative integer $n<\nu$), and we obtain $S=S^{\prime}$.
Now, $S=T\setminus\left\{ \mu\right\} $ yields $T=S\cup\left\{ \mu\right\}
$ (since $\mu\in T$), and similarly $T^{\prime}=S^{\prime}\cup\left\{
\mu\right\} $, so that $T=\underbrace{S}_{=S^{\prime}}\cup\left\{
\mu\right\} =S^{\prime}\cup\left\{ \mu\right\} =T^{\prime}$. This proves
Lemma~\ref{lem.4} for the case $n=\nu$. Thus, the induction step is completed,
and the induction proof of Lemma~\ref{lem.4} is done.
\end{proof}
\begin{theorem}
[Zeckendorf theorem]\label{thm.5} Let $n \in\mathbb{N}$. Then, there exists
one and only one finite lacunar subset $T$ of $\mathbb{N}_{2}$ such that
$n=\sum\limits_{t\in T}f_{t}$.
\end{theorem}
\begin{proof}
[Proof of Theorem~\ref{thm.5}.]There exists a finite lacunar subset $T$ of
$\mathbb{N}_{2}$ such that $n=\sum\limits_{t\in T}f_{t}$ (according to
Lemma~\ref{lem.3}), and such a subset is unique (because any two such subsets
are equal (according to Lemma~\ref{lem.4})). Thus, there exists \textbf{one
and only one} finite lacunar subset $T$ of $\mathbb{N}_{2}$ such that
$n=\sum\limits_{t\in T}f_{t}$. This proves Theorem~\ref{thm.5}.
\end{proof}
Theorem~\ref{thm.5} is a classical result known as the \textit{Zeckendorf
theorem}; it can be found in various places. In particular, the proof given in
\cite{Hender16} is rather close to ours. Hoggatt proved a generalization of
Theorem~\ref{thm.5} in \cite{Hoggat72}.
\begin{definition}
Let $n\in\mathbb{N}$. Theorem~\ref{thm.5} shows that there exists one and only
one finite lacunar subset $T$ of $\mathbb{N}_{2}$ such that $n=\sum
\limits_{t\in T}f_{t}$. We will denote this set $T$ by $Z_{n}$. Thus,
$n=\sum\limits_{t\in Z_{n}}f_{t}$.
\end{definition}
\section{Inequalities for the golden ratio}
Next, we state a completely straightforward (and well-known) theorem, which
shows that the Fibonacci sequence grows roughly exponentially (with the
exponent being the golden ratio $\phi$):
\begin{theorem}
\label{thm.6} For every positive integer $n$, we have $\left\vert f_{n+1}-\phi
f_{n}\right\vert =\dfrac{1}{\sqrt{5}}\left( \phi-1\right) ^{n}$.
\end{theorem}
Theorem~\ref{thm.6} can easily be derived from \cite[Chapter 9, Corollary
34]{BenQui03}. For the sake of self-containedness, let us nevertheless give a
proof of it here.
\begin{proof}
[Proof of Theorem~\ref{thm.6}.]It is easy to see that $\phi^{-1}=\phi-1$ and
$1-\phi^{-2}=\phi-1$. Also, $\left( \phi-1\right) ^{n} \geq0$ (since $\phi-1
\geq0$) and thus $\dfrac{1}{\sqrt{5}} \left( \phi-1\right) ^{n} \geq0$.
Let $n$ be a positive integer. By Binet's formula, we have%
\[
f_{n}=\dfrac{\phi^{n}-\phi^{-n}}{\sqrt{5}}=\dfrac{\phi^{n}\left( 1-\phi
^{-2n}\right) }{\sqrt{5}}=\dfrac{1}{\sqrt{5}}\phi^{n}\left( 1-\phi
^{-2n}\right) .
\]
Applying this to $n+1$ instead of $n$, we get%
\[
f_{n+1}=\dfrac{1}{\sqrt{5}}\phi^{n+1}\left( 1-\phi^{-2\left( n+1\right)
}\right) .
\]
These two equalities yield%
\begin{align*}
f_{n+1}-\phi f_{n} & =\dfrac{1}{\sqrt{5}}\phi^{n+1}\left( 1-\phi^{-2\left(
n+1\right) }\right) -\underbrace{\phi\cdot\dfrac{1}{\sqrt{5}}\phi^{n}%
}_{=\dfrac{1}{\sqrt{5}}\phi\phi^{n}}\left( 1-\phi^{-2n}\right) \\
& =\dfrac{1}{\sqrt{5}}\phi^{n+1}\left( 1-\phi^{-2\left( n+1\right)
}\right) -\dfrac{1}{\sqrt{5}}\underbrace{\phi\phi^{n}}_{=\phi^{n+1}}\left(
1-\phi^{-2n}\right) \\
& =\dfrac{1}{\sqrt{5}}\phi^{n+1}\left( 1-\phi^{-2\left( n+1\right)
}\right) -\dfrac{1}{\sqrt{5}}\phi^{n+1}\left( 1-\phi^{-2n}\right) \\
& =\dfrac{1}{\sqrt{5}}\phi^{n+1}\left( \underbrace{\left( 1-\phi^{-2\left(
n+1\right) }\right) -\left( 1-\phi^{-2n}\right) }_{=\phi^{-2n}%
-\phi^{-2\left( n+1\right) }}\right) \\
& =\dfrac{1}{\sqrt{5}}\phi^{n+1}\left( \phi^{-2n}-\underbrace{\phi
^{-2\left( n+1\right) }}_{=\phi^{-2n-2}=\phi^{-2n}\phi^{-2}}\right) \\
& =\dfrac{1}{\sqrt{5}}\phi^{n+1}\left( \phi^{-2n}-\phi^{-2n}\phi
^{-2}\right) =\dfrac{1}{\sqrt{5}}\underbrace{\phi^{n+1}\phi^{-2n}}%
_{=\phi^{\left( n+1\right) +\left( -2n\right) }=\phi^{-\left( n-1\right)
}=\left( \phi^{-1}\right) ^{n-1}}\left( 1-\phi^{-2}\right) \\
& =\dfrac{1}{\sqrt{5}}\left( \underbrace{\phi^{-1}}_{=\phi-1}\right)
^{n-1}\underbrace{\left( 1-\phi^{-2}\right) }_{=\phi-1}=\dfrac{1}{\sqrt{5}%
}\underbrace{\left( \phi-1\right) ^{n-1}\left( \phi-1\right) }_{=\left(
\phi-1\right) ^{n}}=\dfrac{1}{\sqrt{5}}\left( \phi-1\right) ^{n},
\end{align*}
so that%
\[
\left\vert f_{n+1}-\phi f_{n}\right\vert =\left\vert \dfrac{1}{\sqrt{5}%
}\left( \phi-1\right) ^{n}\right\vert =\dfrac{1}{\sqrt{5}}\left(
\phi-1\right) ^{n}\ \ \ \ \ \ \ \ \ \ \left( \text{since }\dfrac{1}{\sqrt
{5}}\left( \phi-1\right) ^{n}\geq0\right) ,
\]
and Theorem~\ref{thm.6} is proven.
\end{proof}
Let us show yet another lemma for later use:
\begin{lemma}
\label{lem.7} Let $S$ be a finite lacunar subset of $\mathbb{N}_{2}$. Then,
$\sum\limits_{s\in S}\left( \phi-1\right) ^{s}\leq\phi-1$.
\end{lemma}
\begin{proof}
[Proof of Lemma~\ref{lem.7}.]We WLOG assume that $S$ is nonempty (since
otherwise, Lemma~\ref{lem.7} follows easily from $0\leq\phi-1$).
Let $\psi=\phi-1$. It is easily seen that $0<\psi<1$. Also, $\psi=\phi-1$
yields $\psi^{2}=\left( \phi-1\right) ^{2}=\underbrace{\phi^{2}}_{=\phi
+1}-2\phi+1=\left( \phi+1\right) -2\phi+1=2-\phi$ and thus $1-\psi
^{2}=1-\left( 2-\phi\right) =\phi-1=\psi$, so that $\dfrac{\psi^{2}}%
{1-\psi^{2}}=\dfrac{\psi^{2}}{\psi}=\psi$. Also, from $0<\psi<1$, we obtain
$0<\psi^{2}<1$, so that $1-\psi^{2}>0$.
Let us write the set $S$ in the form $\left\{ s_{1},s_{2},\ldots
,s_{k}\right\} $, where $s_{1}0$),
we get $\sum\limits_{s\in S}\psi^{s}\leq\dfrac{\psi^{2}}{1-\psi^{2}}=\psi$.
Replacing $\psi$ by $\phi-1$ in this inequality (since $\psi=\phi-1$), we
rewrite it as $\sum\limits_{s\in S}\left( \phi-1\right) ^{s}\leq\phi-1$.
This proves Lemma~\ref{lem.7}.
\end{proof}
\section{Proving Theorem~\ref{thm.1}}
Let us now come to the proof of Theorem~\ref{thm.1}. First, we formulate the
existence part of this theorem:
\begin{theorem}
[existence part of the generalized Zeckendorf family identities]\label{thm.8}
Let $T$ be a finite set, and let $a_{t}$ be an integer for every $t\in T$.
Then, there exists a finite lacunar subset $S$ of $\mathbb{Z}$ such that
\[
\left(
\begin{array}
[c]{c}%
\sum\limits_{t\in T}f_{n+a_{t}}=\sum\limits_{s\in S}f_{n+s}\text{ for every
}n\in\mathbb{Z}\text{ which}\\
\text{satisfies }n>\max\left( \left\{ -a_{t}\mid t\in T\right\}
\cup\left\{ -s\mid s\in S\right\} \right)
\end{array}
\right) .
\]
\end{theorem}
Before we start proving this, let us introduce a notation:
\begin{definition}
Let $K$ be a subset of $\mathbb{Z}$, and let $a\in\mathbb{Z}$. Then, $K+a$
will denote the subset $\left\{ k+a\ \mid\ k\in K\right\} $ of $\mathbb{Z}$.
\end{definition}
Clearly, $\left( K+a\right) +b=K+\left( a+b\right) $ for any two integers
$a$ and $b$. Also, $K+0=K$. Finally,%
\begin{equation}
\text{if }K\text{ is a lacunar subset of }\mathbb{Z}\text{, and if }%
a\in\mathbb{Z}\text{, then }K+a\text{ is lacunar as well} \label{lacunar-plus}%
\end{equation}
\footnote{\textit{Proof.} Let $K$ be a lacunar subset of $\mathbb{Z}$. Let
$a\in\mathbb{Z}$. Let $q\in K+a$. We shall prove that $q+1\notin K+a$.
\par
Assume the contrary. In other words, assume that $q+1\in K+a$. Thus, $q+1\in
K+a=\left\{ k+a\ \mid\ k\in K\right\} $. Hence, there exists some $\ell\in
K$ such that $q+1=\ell+a$. Consider this $\ell$.
\par
Now, $q\in K+a=\left\{ k+a\ \mid\ k\in K\right\} $ yields that there exists
some $k\in K$ such that $q=k+a$. Consider this $k$. Since $K$ is a lacunar
set, we have $\left( s+1\notin K\text{ for every }s\in K\right) $. Applying
this to $s=k$, we get $k+1\notin K$. But $\ell+a=\underbrace{q}_{=k+a}%
+1=k+a+1$ yields $\ell=\left( k+a+1\right) -a=k+1\notin K$, contradicting
$\ell\in K$. This contradiction shows that our assumption was wrong. Hence,
$q+1\notin K+a$ is proven.
\par
Now, forget that we fixed $q$. We thus have shown that $q+1\notin K+a$ for
every $q\in K+a$. Renaming the variable $q$ as $s$ in this statement, we
obtain $\left( s+1\notin K+a\text{ for every }s\in K+a\right) $. In other
words, the subset $K+a$ of $\mathbb{Z}$ is lacunar. Qed.}.
Let us furthermore make two basic observations:
\begin{itemize}
\item If $u$ and $v$ are two real numbers, then
\begin{equation}
\left\vert u-v\right\vert \leq\left\vert u\right\vert +\left\vert v\right\vert
. \label{pf.thm.8.triangle1}%
\end{equation}
(Indeed, this is one of the forms of the triangle inequality.)
\item If $m$ is a positive integer, then
\begin{equation}
f_{m}=f_{m+2}-f_{m+1}. \label{pf.thm.8.fm=}%
\end{equation}
[\textit{Proof of (\ref{pf.thm.8.fm=}):} Let $m$ be a positive integer. Thus,
$m\geq1$, so that $m+2\geq1+2=3$. But recall that every integer $n\geq3$
satisfies $f_{n}=f_{n-1}+f_{n-2}$, so that $f_{n-2}=f_{n}-f_{n-1}$. Applying
this to $n=m+2$, we obtain $f_{\left( m+2\right) -2}=f_{m+2}-f_{\left(
m+2\right) -1}$. This simplifies to $f_{m}=f_{m+2}-f_{m+1}$. Thus,
(\ref{pf.thm.8.fm=}) is proven.]
\end{itemize}
\begin{proof}
[Proof of Theorem~\ref{thm.8}.]Let us define a real constant $C$ by
$C=\sum\limits_{t\in T}\dfrac{1}{\sqrt{5}}\left( \phi-1\right) ^{a_{t}}$.
Clearly, $C\geq0$ (since $\phi-1>0$).
First, notice that $0<\phi-1<1$ yields $\lim\limits_{n\rightarrow\infty
}\left( \phi-1\right) ^{n}=0$, so that $\lim\limits_{n\rightarrow\infty
}\left( \left( \phi-1\right) ^{n}C\right) =\underbrace{\lim
\limits_{n\rightarrow\infty}\left( \phi-1\right) ^{n}}_{=0}\cdot C=0$ as
well. Therefore, for every $\varepsilon>0$, every sufficiently high integer
$N$ satisfies $\left( \phi-1\right) ^{N}C<\varepsilon$. In particular,
taking $\varepsilon=2-\phi$ (here we are using that $2-\phi>0$), we see that
every sufficiently high integer $N$ satisfies $\left( \phi-1\right)
^{N}C<2-\phi$. Also, obviously, every sufficiently high integer $N$ satisfies
$N>\max\left\{ -a_{t}\mid t\in T\right\} $. Hence, if we take our integer
$N$ high enough, we can ensure that it will satisfy \textit{both} $\left(
\phi-1\right) ^{N}C<2-\phi$ and $N>\max\left\{ -a_{t}\mid t\in T\right\} $.
So let us fix some integer $N\in\mathbb{N}_{2}$ high enough that it satisfies
both $\left( \phi-1\right) ^{N}C<2-\phi$ and $N>\max\left\{ -a_{t}\mid t\in
T\right\} $.
Since $N>\max\left\{ -a_{t}\mid t\in T\right\} $, we have $N>-a_{t}$ for
every $t\in T$, and thus $N+a_{t}>0$ for every $t\in T$. This shows that the
Fibonacci number $f_{N+a_{t}}$ is well-defined for every $t\in T$. (This was
exactly the reason why we have required $N>\max\left\{ -a_{t}\mid t\in
T\right\} $. The reason for the second condition $\left( \phi-1\right)
^{N}C<2-\phi$ will become clear later in the proof.)
Let $\nu=\sum\limits_{t\in T}f_{N+a_{t}}$. Recall that $Z_{\nu}$ is a finite
lacunar subset of $\mathbb{N}_{2}$ such that $\nu=\sum\limits_{t\in Z_{\nu}%
}f_{t}$ (by the definition of $Z_{\nu}$). Let $S=Z_{\nu}+\left( -N\right) $.
Then, the set $S=Z_{\nu}+\left( -N\right) $ is lacunar (by
(\ref{lacunar-plus}) (applied to $K=Z_{\nu}$ and $a=-N$), because $Z_{\nu}$ is
a lacunar subset of $\mathbb{Z}$) and finite (since $Z_{\nu}$ is finite), and
satisfies%
\begin{align*}
\nu & =\sum\limits_{t\in Z_{\nu}}f_{t}=\sum\limits_{s\in Z_{\nu}+\left(
-N\right) }f_{N+s}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we substituted }N+s\text{ for }t\text{, because the map}\\
Z_{\nu}+\left( -N\right) \rightarrow Z_{\nu},\text{ }s\mapsto N+s\text{ is a
bijection}%
\end{array}
\right) \\
& =\sum\limits_{s\in S}f_{N+s}\ \ \ \ \ \ \ \ \ \ \left( \text{since }%
Z_{\nu}+\left( -N\right) =S\right) .
\end{align*}
So now we know that $\sum\limits_{t\in T}f_{N+a_{t}}=\sum\limits_{s\in
S}f_{N+s}$ (because both sides of this equation equal $\nu$).
So, we have chosen a large $N$ and found a finite lacunar subset $S$ of
$\mathbb{Z}$ which satisfies $\sum\limits_{t\in T}f_{N+a_{t}}=\sum
\limits_{s\in S}f_{N+s}$. In other words, we have showed that the equation
\begin{equation}
\sum\limits_{t\in T}f_{n+a_{t}}=\sum\limits_{s\in S}f_{n+s} \label{main}%
\end{equation}
holds for $n=N$. But we must show that this equation holds for \textit{every}
$n>\max\left( \left\{ -a_{t}\mid t\in T\right\} \cup\left\{ -s\mid s\in
S\right\} \right) $. In order to do this, first let us prove that
(\ref{main}) holds for $n=N+1$. Actually, we are going to show a bit more:
\begin{statement}
\textit{Assertion }$\alpha$\textit{:} Let $m\geq N$ be an integer such that
(\ref{main}) holds for $n=m$. Then, (\ref{main}) also holds for $n=m+1$.
\end{statement}
[\textit{Proof of Assertion }$\alpha$\textit{:} Since (\ref{main}) holds for
$n=m$, we have $\sum\limits_{t\in T}f_{m+a_{t}}=\sum\limits_{s\in S}f_{m+s}$.
Now,%
\begin{align*}
& \sum\limits_{t\in T}\underbrace{f_{\left( m+1\right) +a_{t}}%
}_{\substack{=f_{m+a_{t}+1}\\=\left( f_{m+a_{t}+1}-\phi f_{m+a_{t}}\right)
+\phi f_{m+a_{t}}}}-\sum\limits_{s\in S}\underbrace{f_{\left( m+1\right)
+s}}_{=f_{m+s+1}}\\
& =\underbrace{\sum\limits_{t\in T}\left( \left( f_{m+a_{t}+1}-\phi
f_{m+a_{t}}\right) +\phi f_{m+a_{t}}\right) }_{=\sum\limits_{t\in T}\left(
f_{m+a_{t}+1}-\phi f_{m+a_{t}}\right) +\phi\sum\limits_{t\in T}f_{m+a_{t}}%
}-\sum\limits_{s\in S}f_{m+s+1}\\
& =\sum\limits_{t\in T}\left( f_{m+a_{t}+1}-\phi f_{m+a_{t}}\right)
+\phi\underbrace{\sum\limits_{t\in T}f_{m+a_{t}}}_{=\sum\limits_{s\in
S}f_{m+s}}-\sum\limits_{s\in S}f_{m+s+1}\\
& =\sum\limits_{t\in T}\left( f_{m+a_{t}+1}-\phi f_{m+a_{t}}\right)
+\underbrace{\phi\sum\limits_{s\in S}f_{m+s}-\sum\limits_{s\in S}f_{m+s+1}%
}_{=\sum\limits_{s\in S}\left( \phi f_{m+s}-f_{m+s+1}\right) =-\sum
\limits_{s\in S}\left( f_{m+s+1}-\phi f_{m+s}\right) }\\
& =\sum\limits_{t\in T}\left( f_{m+a_{t}+1}-\phi f_{m+a_{t}}\right)
-\sum\limits_{s\in S}\left( f_{m+s+1}-\phi f_{m+s}\right) ,
\end{align*}
so that%
\begin{align}
& \left\vert \sum\limits_{t\in T}f_{\left( m+1\right) +a_{t}}%
-\sum\limits_{s\in S}f_{\left( m+1\right) +s}\right\vert =\left\vert
\sum\limits_{t\in T}\left( f_{m+a_{t}+1}-\phi f_{m+a_{t}}\right)
-\sum\limits_{s\in S}\left( f_{m+s+1}-\phi f_{m+s}\right) \right\vert
\nonumber\\
& \leq\left\vert \sum\limits_{t\in T}\left( f_{m+a_{t}+1}-\phi f_{m+a_{t}%
}\right) \right\vert +\left\vert \sum\limits_{s\in S}\left( f_{m+s+1}-\phi
f_{m+s}\right) \right\vert \label{Estimate1}%
\end{align}
(by (\ref{pf.thm.8.triangle1}), applied to $u=\sum\limits_{t\in T}\left(
f_{m+a_{t}+1}-\phi f_{m+a_{t}}\right) $ and $v=\sum\limits_{s\in S}\left(
f_{m+s+1}-\phi f_{m+s}\right) $).
Now, the triangle inequality yields%
\begin{align*}
& \left\vert \sum\limits_{t\in T}\left( f_{m+a_{t}+1}-\phi f_{m+a_{t}%
}\right) \right\vert \\
& \leq\sum\limits_{t\in T}\underbrace{\left\vert f_{m+a_{t}+1}-\phi
f_{m+a_{t}}\right\vert }_{\substack{=\dfrac{1}{\sqrt{5}}\left( \phi-1\right)
^{m+a_{t}}\\\text{(by Theorem~\ref{thm.6}, applied to}\\m+a_{t}\text{ instead
of }n\text{)}}}=\sum\limits_{t\in T}\dfrac{1}{\sqrt{5}}\underbrace{\left(
\phi-1\right) ^{m+a_{t}}}_{=\left( \phi-1\right) ^{m}\left( \phi-1\right)
^{a_{t}}}=\left( \phi-1\right) ^{m}\underbrace{\sum\limits_{t\in T}\dfrac
{1}{\sqrt{5}}\left( \phi-1\right) ^{a_{t}}}_{=C}\\
& =\underbrace{\left( \phi-1\right) ^{m}}_{\substack{\leq\left(
\phi-1\right) ^{N}\text{ (since}\\0<\phi-1<1\text{ and }m\geq N\text{)}%
}}C\leq\left( \phi-1\right) ^{N}C\ \ \ \ \ \ \ \ \ \ \left( \text{since
}C\geq0\right) \\
& <2-\phi.
\end{align*}
On the other hand, $S$ is a lacunar subset of $\mathbb{Z}$, and thus the set
$S+m$ is lacunar as well (by (\ref{lacunar-plus}), applied to $S$ and $m$
instead of $K$ and $a$), and besides $\underbrace{S}_{=Z_{\nu}+\left(
-N\right) }+m=\left( Z_{\nu}+\left( -N\right) \right) +m=Z_{\nu}+\left(
\left( -N\right) +m\right) =\left\{ z+\left( \left( -N\right)
+m\right) \ \mid\ z\in Z_{\nu}\right\} \subseteq\mathbb{N}_{2}%
$\ \ \ \ \footnote{because every $z\in Z_{\nu}$ satisfies $\underbrace{z}%
_{\substack{\geq2\\\text{(since }z\in Z_{\nu}\subseteq\mathbb{N}_{2}\text{)}%
}}+\left( \left( -N\right) +\underbrace{m}_{\geq N}\right) \geq2+\left(
\left( -N\right) +N\right) =2$ and thus $z+\left( \left( -N\right)
+m\right) \in\mathbb{N}_{2}$}. Thus, $S+m$ is a finite lacunar subset of
$\mathbb{N}_{2}$ (indeed, the set $S+m$ is finite since $S$ is finite). Hence,
Lemma~\ref{lem.7} (applied to $S+m$ instead of $S$) yields $\sum\limits_{s\in
S+m}\left( \phi-1\right) ^{s}\leq\phi-1$.
The triangle inequality yields%
\begin{align*}
& \left\vert \sum\limits_{s\in S}\left( f_{m+s+1}-\phi f_{m+s}\right)
\right\vert \\
& \leq\sum\limits_{s\in S}\underbrace{\left\vert f_{m+s+1}-\phi
f_{m+s}\right\vert }_{\substack{=\dfrac{1}{\sqrt{5}}\left( \phi-1\right)
^{m+s}\\\text{(by Theorem~\ref{thm.6}, applied to}\\m+s\text{ instead of
}n\text{)}}}=\sum\limits_{s\in S}\dfrac{1}{\sqrt{5}}\left( \phi-1\right)
^{m+s}=\dfrac{1}{\sqrt{5}}\sum\limits_{s\in S}\left( \phi-1\right) ^{m+s}\\
& =\dfrac{1}{\sqrt{5}}\underbrace{\sum\limits_{s\in S+m}\left(
\phi-1\right) ^{s}}_{\leq\phi-1}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we substituted }s\text{ for }m+s\text{, since the map}\\
S\rightarrow S+m,\ s\mapsto m+s\text{ is a bijection}%
\end{array}
\right) \\
& \leq\underbrace{\dfrac{1}{\sqrt{5}}}_{<1}\cdot\left( \phi-1\right)
<\phi-1\ \ \ \ \ \ \ \ \ \ \left( \text{since }\phi-1>0\right) .
\end{align*}
Thus, (\ref{Estimate1}) becomes%
\begin{align}
\left\vert \sum\limits_{t\in T}f_{\left( m+1\right) +a_{t}}-\sum
\limits_{s\in S}f_{\left( m+1\right) +s}\right\vert & \leq
\underbrace{\left\vert \sum\limits_{t\in T}\left( f_{m+a_{t}+1}-\phi
f_{m+a_{t}}\right) \right\vert }_{<2-\phi}+\underbrace{\left\vert
\sum\limits_{s\in S}\left( f_{m+s+1}-\phi f_{m+s}\right) \right\vert
}_{<\phi-1}\nonumber\\
& <\left( 2-\phi\right) +\left( \phi-1\right) =1.\nonumber
\end{align}
Since $\sum\limits_{t\in T}f_{\left( m+1\right) +a_{t}}-\sum\limits_{s\in
S}f_{\left( m+1\right) +s}$ is an integer, we thus conclude that
$\sum\limits_{t\in T}f_{\left( m+1\right) +a_{t}}-\sum\limits_{s\in
S}f_{\left( m+1\right) +s}$ is an integer with an absolute value $<1$. But
the only integer with an absolute value $<1$ is $0$. Thus, $\sum\limits_{t\in
T}f_{\left( m+1\right) +a_{t}}-\sum\limits_{s\in S}f_{\left( m+1\right)
+s}=0$, so that $\sum\limits_{t\in T}f_{\left( m+1\right) +a_{t}}%
=\sum\limits_{s\in S}f_{\left( m+1\right) +s}$. In other words, (\ref{main})
holds for $n=m+1$. This proves Assertion $\alpha$.]
Assertion $\alpha$ almost immediately yields the following:
\begin{statement}
\textit{Assertion }$\beta$\textit{:} The equation (\ref{main}) holds for every
$n\geq N$.
\end{statement}
[\textit{Proof of Assertion }$\beta$\textit{:} We are going to prove Assertion
$\beta$ by induction over $n$:
As the \textit{induction base} we take the case $n=N$. In this case, the
equation (\ref{main}) holds (as we already know), so that Assertion $\beta$ is
proved for $n=N$, and thus the induction base is completed.
\textit{Induction step:} Let $m\geq N$ be an integer. Assume that Assertion
$\beta$ holds for $n=m$. In other words, the equation (\ref{main}) holds for
$n=m$. Then, Assertion $\alpha$ yields that the equation (\ref{main}) holds
for $n=m+1$ as well. In other words, Assertion $\beta$ holds for $n=m+1$ as
well. This completes the induction step, and thus Assertion $\beta$ is proven
by induction over $n$.]
With Assertion $\beta$ we now know that (\ref{main}) holds for all
sufficiently high $n$, namely for all $n\geq N$. But in order to prove Theorem
8, we must show that it also holds for all $n>\max\left( \left\{ -a_{t}\mid
t\in T\right\} \cup\left\{ -s\mid s\in S\right\} \right) $; usually, these
$n$ are not all $\geq N$. What remains to do is \textquotedblleft backwards
induction\textquotedblright\ or an application of the maximum principle. Here
are the details:
Let $M=\max\left( \left\{ -a_{t}\mid t\in T\right\} \cup\left\{ -s\mid
s\in S\right\} \right) $. We thus must show that (\ref{main}) holds for all
$n>M$.
Define a subset $\mathcal{R}$ of $\mathbb{Z}$ by%
\begin{equation}
\mathcal{R}=\left\{ n\in\mathbb{Z}\ \mid\ \text{we have }n>M\text{, and
(\ref{main}) does not hold}\right\} . \label{defR}%
\end{equation}
This set $\mathcal{R}$ is bounded from above by $N$ (in fact, it does not
contain any $n\geq N$, because (\ref{main}) does hold for all $n\geq N$
(according to Assertion $\beta$)), and bounded from below by $M$ (because
every element of this set is $>M$ by definition). Thus, this set $\mathcal{R}$
is finite (since any subset of $\mathbb{Z}$ that is bounded from above and
bounded from below is finite).
Let us assume (for the sake of contradiction) that $\mathcal{R}$ is nonempty.
Then, the set $\mathcal{R}$ is a nonempty finite set of integers, and thus has
a maximum (since a nonempty finite set of integers always has a maximum). Let
$\lambda$ be this maximum. Then, $\lambda\in\mathcal{R}=\left\{
n\in\mathbb{Z}\ \mid\ \text{we have }n>M\text{, and (\ref{main}) does not
hold}\right\} $. In other words, $\lambda$ is an element of $\mathbb{Z}$
satisfying $\lambda>M$, and (\ref{main}) does not hold for $n=\lambda$. On the
other hand,%
\begin{equation}
\text{for every integer }\mu>\lambda\text{, the equation (\ref{main}) holds
for }n=\mu\label{back-induct}%
\end{equation}
\footnote{\textit{Proof.} Let $\mu>\lambda$ be an integer. We must prove that
the equation (\ref{main}) holds for $n=\mu$.
\par
Assume the contrary. Thus, the equation (\ref{main}) does not hold for $n=\mu
$. Hence, $\mu$ is an integer with the property that $\mu>M$ (since
$\mu>\lambda>M$), and (\ref{main}) does not hold for $n=\mu$. In other words,
$\mu\in\left\{ n\in\mathbb{Z}\ \mid\ \text{we have }n>M\text{, and
(\ref{main}) does not hold}\right\} $. In view of (\ref{defR}), this rewrites
as $\mu\in\mathcal{R}$.
\par
But $\lambda$ is the maximum of $\mathcal{R}$. Thus, every $r\in\mathcal{R}$
satisfies $r\leq\lambda$. Applying this to $r=\mu$, we obtain $\mu\leq\lambda$
(since $\mu\in\mathcal{R}$). This contradicts $\mu>\lambda$. This
contradiction shows that our assumption was wrong. Hence, the equation
(\ref{main}) holds for $n=\mu$. This proves (\ref{back-induct}).}. In
particular, applying (\ref{back-induct}) to $\mu=\lambda+1$, we see that
(\ref{main}) holds for $n=\lambda+1$; in other words, $\sum\limits_{t\in
T}f_{\lambda+1+a_{t}}=\sum\limits_{s\in S}f_{\lambda+1+s}$. Besides, applying
(\ref{back-induct}) to $\mu=\lambda+2$, we see that (\ref{main}) holds for
$n=\lambda+2$; in other words, $\sum\limits_{t\in T}f_{\lambda+2+a_{t}}%
=\sum\limits_{s\in S}f_{\lambda+2+s}$.
Now, we are going to prove the equation $\sum\limits_{t\in T}f_{\lambda+a_{t}%
}=\sum\limits_{s\in S}f_{\lambda+s}$. (We notice that this equation indeed
makes sense, because the Fibonacci number $f_{\lambda+a_{t}}$ is well-defined
for every $t\in T$\ \ \ \ \footnote{\textit{Proof.} In fact, $\lambda
>M=\max\left( \underbrace{\left\{ -a_{t}\mid t\in T\right\} \cup\left\{
-s\mid s\in S\right\} }_{\supseteq\left\{ -a_{t}\mid t\in T\right\}
}\right) \geq\max\left\{ -a_{t}\mid t\in T\right\} $ yields that
$\lambda>-a_{t}$ for every $t\in T$. Thus, for every $t\in T$, we have
$\lambda+a_{t}>0$, and thus $f_{\lambda+a_{t}}$ is well-defined.}, and because
the Fibonacci number $f_{\lambda+s}$ is well-defined for every $s\in
S$\ \ \ \ \footnote{\textit{Proof.} In fact, $\lambda>M=\max\left(
\underbrace{\left\{ -a_{t}\mid t\in T\right\} \cup\left\{ -s\mid s\in
S\right\} }_{\supseteq\left\{ -s\mid s\in S\right\} }\right) \geq
\max\left\{ -s\mid s\in S\right\} $ yields that $\lambda>-s$ for every $s\in
S$. Thus, for every $s\in S$, we have $\lambda+s>0$, and thus $f_{\lambda+s}$
is well-defined.}.) Applying (\ref{pf.thm.8.fm=}) to $m=\lambda+a_{t}$, we
obtain
\begin{equation}
f_{\lambda+a_{t}}=\underbrace{f_{\lambda+a_{t}+2}}_{=f_{\lambda+2+a_{t}}%
}-\underbrace{f_{\lambda+a_{t}+1}}_{=f_{\lambda+1+a_{t}}}=f_{\lambda+2+a_{t}%
}-f_{\lambda+1+a_{t}} \label{pf.thm.8.back1}%
\end{equation}
for every $t\in T$. On the other hand, applying (\ref{pf.thm.8.fm=}) to
$m=\lambda+s$, we obtain%
\begin{equation}
f_{\lambda+s}=\underbrace{f_{\lambda+s+2}}_{=f_{\lambda+2+s}}%
-\underbrace{f_{\lambda+s+1}}_{=f_{\lambda+1+s}}=f_{\lambda+2+s}%
-f_{\lambda+1+s} \label{pf.thm.8.back2}%
\end{equation}
for every $s\in S$. Thus,%
\begin{align*}
\sum\limits_{t\in T}\underbrace{f_{\lambda+a_{t}}}_{\substack{=f_{\lambda
+2+a_{t}}-f_{\lambda+1+a_{t}}\\\text{(by (\ref{pf.thm.8.back1}))}}} &
=\sum\limits_{t\in T}\left( f_{\lambda+2+a_{t}}-f_{\lambda+1+a_{t}}\right)
=\underbrace{\sum\limits_{t\in T}f_{\lambda+2+a_{t}}}_{=\sum\limits_{s\in
S}f_{\lambda+2+s}}-\underbrace{\sum\limits_{t\in T}f_{\lambda+1+a_{t}}}%
_{=\sum\limits_{s\in S}f_{\lambda+1+s}}\\
& =\sum\limits_{s\in S}f_{\lambda+2+s}-\sum\limits_{s\in S}f_{\lambda
+1+s}=\sum\limits_{s\in S}\underbrace{\left( f_{\lambda+2+s}-f_{\lambda
+1+s}\right) }_{\substack{=f_{\lambda+s}\\\text{(by (\ref{pf.thm.8.back2}))}%
}}=\sum\limits_{s\in S}f_{\lambda+s}.
\end{align*}
In other words, (\ref{main}) holds for $n=\lambda$. This contradicts our
knowledge that (\ref{main}) does not hold for $n=\lambda$. This contradiction
shows that our assumption (the assumption that the set $\mathcal{R}$ is
nonempty) was wrong. Hence, the set $\mathcal{R}$ is empty. In other words,
the set%
\[
\left\{ n\in\mathbb{Z}\ \mid\ \text{we have }n>M\text{, and (\ref{main}) does
not hold}\right\}
\]
is empty (since $\mathcal{R}=\left\{ n\in\mathbb{Z}\ \mid\ \text{we have
}n>M\text{, and (\ref{main}) does not hold}\right\} $). In other words, there
exists no $n\in\mathbb{Z}$ satisfying $n>M$ such that (\ref{main}) does not
hold. In other words, (\ref{main}) holds for every $n\in\mathbb{Z}$ satisfying
$n>M$. Since \newline$M=\max\left( \left\{ -a_{t}\mid t\in T\right\}
\cup\left\{ -s\mid s\in S\right\} \right) $, this is equivalent to saying
that (\ref{main}) holds for every $n\in\mathbb{Z}$ satisfying $n>\max\left(
\left\{ -a_{t}\mid t\in T\right\} \cup\left\{ -s\mid s\in S\right\}
\right) $. Consequently, Theorem~\ref{thm.8} is proven.
\end{proof}
All that remains now is the (rather trivial) uniqueness part of
Theorem~\ref{thm.1}:
\begin{lemma}
[uniqueness part of the generalized Zeckendorf family identities]\label{lem.9}
Let $T$ be a finite set, and let $a_{t}$ be an integer for every $t\in T$.
Let $S$ be a finite lacunar subset of $\mathbb{Z}$ such that%
\begin{equation}
\left(
\begin{array}
[c]{c}%
\sum\limits_{t\in T}f_{n+a_{t}}=\sum\limits_{s\in S}f_{n+s}\text{ for every
}n\in\mathbb{Z}\text{ which}\\
\text{satisfies }n>\max\left( \left\{ -a_{t}\mid t\in T\right\}
\cup\left\{ -s\mid s\in S\right\} \right)
\end{array}
\right) . \label{eq.lem.9.ass1}%
\end{equation}
Let $S^{\prime}$ be a finite lacunar subset of $\mathbb{Z}$ such that%
\begin{equation}
\left(
\begin{array}
[c]{c}%
\sum\limits_{t\in T}f_{n+a_{t}}=\sum\limits_{s\in S^{\prime}}f_{n+s}\text{ for
every }n\in\mathbb{Z}\text{ which}\\
\text{satisfies }n>\max\left( \left\{ -a_{t}\mid t\in T\right\}
\cup\left\{ -s\mid s\in S^{\prime}\right\} \right)
\end{array}
\right) . \label{eq.lem.9.ass2}%
\end{equation}
Then, $S=S^{\prime}$.
\end{lemma}
\begin{proof}
[Proof of Lemma~\ref{lem.9}.]Let%
\[
n=\max\left( \left\{ -a_{t}\mid t\in T\right\} \cup\left\{ -s\mid s\in
S\right\} \cup\left\{ -s\mid s\in S^{\prime}\right\} \right) +2.
\]
Then,%
\begin{align*}
n & >\max\left( \underbrace{\left\{ -a_{t}\mid t\in T\right\}
\cup\left\{ -s\mid s\in S\right\} \cup\left\{ -s\mid s\in S^{\prime
}\right\} }_{\supseteq\left\{ -a_{t}\mid t\in T\right\} \cup\left\{ -s\mid
s\in S\right\} }\right) \\
& \geq\max\left( \left\{ -a_{t}\mid t\in T\right\} \cup\left\{ -s\mid
s\in S\right\} \right) ,
\end{align*}
so that%
\begin{align*}
\sum\limits_{t\in T}f_{n+a_{t}} & =\sum\limits_{s\in S}f_{n+s}%
\ \ \ \ \ \ \ \ \ \ \left( \text{by (\ref{eq.lem.9.ass1})}\right) \\
& =\sum\limits_{t\in S+n}f_{t}\ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we substituted }t\text{ for }n+s\text{, since the map}\\
S\rightarrow S+n,\ s\mapsto n+s\text{ is a bijection}%
\end{array}
\right) .
\end{align*}
Similarly, $\sum\limits_{t\in T}f_{n+a_{t}}=\sum\limits_{t\in S^{\prime}%
+n}f_{t}$.
Now, $S+n$ is a lacunar set (by (\ref{lacunar-plus}) (applied to $K=S$ and
$a=n$), since $S$ is a lacunar subset of $\mathbb{Z}$) and a subset of
$\mathbb{N}_{2}$\ \ \ \ \footnote{\textit{Proof.} Since%
\[
n=\underbrace{\max\left( \left\{ -a_{t}\mid t\in T\right\} \cup\left\{
-s\mid s\in S\right\} \cup\left\{ -s\mid s\in S^{\prime}\right\} \right)
}_{\substack{\geq\max\left\{ -s\mid s\in S\right\} \\\text{(since }\left\{
-a_{t}\mid t\in T\right\} \cup\left\{ -s\mid s\in S\right\} \cup\left\{
-s\mid s\in S^{\prime}\right\} \supseteq\left\{ -s\mid s\in S\right\}
\text{)}}}+2\geq\max\left\{ -s\mid s\in S\right\} +2,
\]
we have $n-2\geq\max\left\{ -s\mid s\in S\right\} $, and thus $n-2\geq-s$
for every $s\in S$. Hence, every $s\in S$ satisfies $n-2+s\geq0$, which
rewrites as $s+n\geq2$. Equivalently, $s+n\in\mathbb{N}_{2}$. Thus, we have
shown that $s+n\in\mathbb{N}_{2}$ for each $s\in S$. In other words, $\left\{
s+n\ \mid\ s\in S\right\} \subseteq\mathbb{N}_{2}$. Hence,
\[
S+n=\left\{ s+n\ \mid\ s\in S\right\} \subseteq\mathbb{N}_{2}.
\]
}. In other words, $S+n$ is a finite lacunar subset of $\mathbb{N}_{2}$ (since
$S+n$ is finite (because $S$ is finite)). Similarly, $S^{\prime}+n$ is a
finite lacunar subset of $\mathbb{N}_{2}$. Applying Lemma~\ref{lem.4} to
$S+n$, $S^{\prime}+n$ and $\sum\limits_{t\in T}f_{n+a_{t}}$ instead of $T$,
$T^{\prime}$ and $n$ yields that $S+n=S^{\prime}+n$ (because $\sum
\limits_{t\in T}f_{n+a_{t}}=\sum\limits_{t\in S+n}f_{t}$ and $\sum
\limits_{t\in T}f_{n+a_{t}}=\sum\limits_{t\in S^{\prime}+n}f_{t}$). Hence,%
\begin{align*}
S & =S+\underbrace{0}_{=\left( n+\left( -n\right) \right) }=S+\left(
n+\left( -n\right) \right) =\underbrace{\left( S+n\right) }_{=S^{\prime
}+n}+\left( -n\right) \\
& =\left( S^{\prime}+n\right) +\left( -n\right) =S^{\prime}%
+\underbrace{\left( n+\left( -n\right) \right) }_{=0}=S^{\prime
}+0=S^{\prime}.
\end{align*}
This proves Lemma~\ref{lem.9}.
\end{proof}
\begin{proof}
[Proof of Theorem~\ref{thm.1}.]There exists a finite lacunar subset $S$ of
$\mathbb{Z}$ such that
\[
\left(
\begin{array}
[c]{c}%
\sum\limits_{t\in T}f_{n+a_{t}}=\sum\limits_{s\in S}f_{n+s}\text{ for every
}n\in\mathbb{Z}\text{ which}\\
\text{satisfies }n>\max\left( \left\{ -a_{t}\mid t\in T\right\}
\cup\left\{ -s\mid s\in S\right\} \right)
\end{array}
\right)
\]
(according to Theorem~\ref{thm.8}), and such a subset is unique (because any
two such subsets are equal (according to Lemma~\ref{lem.9})). Thus, there
exists \textbf{one and only one} such subset. This proves Theorem~\ref{thm.1}.
\end{proof}
\begin{thebibliography}{99999999} %
\bibitem[BenQui03]{BenQui03}Arthur T. Benjamin and Jennifer J. Quinn,
\textit{Proofs that Really Count: The Art of Combinatorial Proof}, The
Mathematical Association of America, 2003.
\bibitem[Grinbe11]{this.short}Darij Grinberg, \textit{Zeckendorf family
identities generalized},
%TCIMACRO{\TeXButton{today}{\today}}%
%BeginExpansion
\today
%EndExpansion
, *brief version*.\newline%
\url{http://www.cip.ifi.lmu.de/~grinberg/zeckendorfBRIEF.pdf}\newline Also
available as \href{https://arxiv.org/abs/1103.4507v2}{arXiv preprint
arXiv:1103.4507v2}.
\bibitem[Hender16]{Hender16}Nik Henderson, \textit{What is Zeckendorf's
Theorem?}, 23 July 2016.\newline\url{https://math.osu.edu/sites/math.osu.edu/files/henderson_zeckendorf.pdf}
\bibitem[Hoggat72]{Hoggat72}V. E. Hoggatt, Jr., \textit{Generalized Zeckendorf
theorem}, The Fibonacci Quarterly \textbf{10} (1972), Issue 1, pp.
89--94.\newline\url{https://www.fq.math.ca/Scanned/10-1/hoggatt2.pdf}
\bibitem[Vorobi02]{Vorobi02}Nicolai N. Vorobiev, \textit{Fibonacci numbers},
translated from the Russian by Mircea Martin, Springer 2002.
\bibitem[WooZei09]{1}Philip Matchett Wood, Doron Zeilberger, \textit{A
translation method for finding combinatorial bijections}, Annals of
Combinatorics \textbf{13} (2009), pp. 383--402. \newline\url{http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/trans-method.html}
\end{thebibliography}
\end{document}