<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\usepackage{pstricks}

\hyphenation{non-ze-ro}
\def\a {\alpha}
\def\K {\mathbb{K}}
\def\Z {\mathbb{Z}}
\def\Q {\mathbb{Q}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

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


\begin{center}
\vskip 1cm{\LARGE\bf On Some Combinations of Non-Consecutive
\\
\vskip .1in
 Terms of a Recurrence Sequence}  
\vskip 1cm
\large
Eva Trojovsk\'a\\
Department of Mathematics\\
Faculty of Science\\
University of Hradec Kr\'alov\'e\\
Czech Republic\\
\href{mailto:eva.trojovska@uhk.cz}{\tt eva.trojovska@uhk.cz} \\
\end{center}

\vskip .2 in


\begin{abstract}
Let $(G_m)_{m\geq 0}$ be an integer linear recurrence sequence (satisfying
some weak technical conditions) and let $x\geq 1$ be an integer. In this paper, among other things, we are interested in non-consecutive combinations $xG_{n+a}+G_{n}$ that belong to the sequence $(G_m)_{m\geq 0}$ for infinitely many positive integers $n$. In this case, we make explicit an upper bound for $x$ that depends only on $a$ and the zeros of the characteristic polynomial of this recurrence (this generalizes previous papers  of Trojovsk\'y). As an application, we study the Fibonacci case.
\end{abstract}



\section{Introduction}


A sequence $(G_n)_{n\geq 0}$ is \textit{a linear recurrence sequence} with coefficients $c_0$, $c_1,\ldots,c_{k-1}$, with $c_0\neq 0,$ if
\begin{equation}\label{recu}
G_{n+k}=c_{k-1}G_{n+k-1}+\cdots + c_1G_{n+1}+c_0G_n,
\end{equation}
for all positive integers $n$. A recurrence sequence is therefore completely determined by the \textit{initial values} $G_0$, $G_1$, $\ldots, G_{k-1}$, and by the coefficients $c_0$, $c_1, \ldots,c_{k-1}$. The integer $k$ is called the {\it order} of the linear recurrence. The \textit{characteristic polynomial} of the sequence $(G_n)_{n\geq 0}$ is given by
\[
\psi(x)=x^{k}-c_{k-1}x^{k-1}-\cdots - c_1x-c_0.
\]
It is well-known that for all $n$ we have
\begin{equation}\label{general}
G_n=g_1(n)\a_1^n+\cdots +g_{\ell}(n)\a_{\ell}^n,
\end{equation}
where $\a_j$ is a zero of $\psi(x)$ and $g_j(x)$ is a polynomial over a certain number field, for $j=1,\ldots,\ell$. In this paper, we consider only integer recurrence sequences, i.e., recurrence sequences whose coefficients and initial values are integers. Hence, $g_j(n)$ is an algebraic number, for all $j=1,\ldots,{\ell}$, and $n\in \mathbb{Z}$. 

In this paper we explore a problem that is related to papers \cite{BrLu, CaSo, MAR1, chaos, chaos2}. Possibly the most famous recurrence sequence is the \textit{Fibonacci sequence} $(F_n)_{n\geq 0}$ defined by the recurrence $F_{n+1}=F_n+F_{n-1}\ (n\geq 1)$ with initial values $F_0=0$ and $F_1=1$. Its companion sequence is the sequence of Lucas numbers $(L_n)_{n\geq 0}$ that are defined by the same recurrence but with initial values $L_0=2$ and $L_1=1$.

The Fibonacci numbers are known for their amazing properties (see \cite{FIB3} for the history, properties, and rich applications of the Fibonacci sequence and some of its variants). Among several attractive algebraic identities involving these numbers, we point out the identities of the form
\[
xF_{n+a}+F_n=F_{n+b}.
\]
For instance, when $a=1$, Trojovsk\'y \cite{chaos} proved that $x=1$ and $x=2$ are the only values providing identities. A question arose: what happens if $a&gt;1$? Are there other identities? The answer is Yes, as for example we have
\[
11F_{n+5}+F_n=F_{n+10}.
\]
Thus, the aim of this work is to combine some Diophantine tools (asymptotic estimates and Galois theory) in order to study the possibilities of existence of such identities in the case of a general linear recurrence. In particular, we show that it is possible to obtain an upper bound for $x$ in the case when $xG_{n+a}+G_{n}$ belongs to the sequence $(G_m)_{m\geq 0}$ for infinitely many integers $m$. This upper bound is effective and can be made explicit by means of $a$ and the recurrence sequence. More precisely, our main result is the following
\begin{theorem}\label{main1}
Let $(G_n)_{n\geq 0}$ be an integer linear recurrence (of order at least $2$) such that
its characteristic polynomial $\psi(x)$ has a simple positive zero that is
the only zero lying outside the unit circle. If $x\geq 1$ is an integer such that $xG_{n+a}+G_{n}$ belongs to $(G_m)_{m\geq 0}$ for infinitely many integers $n$, then
\begin{equation}
 x&lt; \frac{2}{|\beta|^a},
 \end{equation}
 where $\psi(\beta)=0$ and $|\beta|:=\displaystyle\max_{\psi(z)=0, |z|\leq 1} |z|$.
\end{theorem}

Let us give a brief overview of our strategy for proving Theorem \ref{main1}. First, by supposing that $xG_{n+a}+G_{n}=G_{t(n)}$, we prove that $t(n)=n+b$, for some integer $b$ (this is done by using asymptotic results for $G_n$). Next, we use the asymptotic formula for $G_{n+t}/G_n$ (when $t\in \{a,b\}$)  to obtain the equation $x\alpha^a+1=\alpha^{b}$, where $\alpha$ is the dominant root of the sequence $(G_m)_{m\geq 0}$. Since $\alpha&gt;1$, the right-hand side of the previous identity can be very large. However, by conjugating by some convenient automorphism of the Galois group of the characteristic polynomial of the recurrence, we get $|x\beta^a+1|=|\beta|^{b}&lt;1$ (since we are supposing that the algebraic conjugates of $\alpha$ are inside the unit circle). In conclusion, we obtain an upper bound for $x$ depending on $\beta$ and $a$.

As an application of our Theorem \ref{main1}, we completely solve the case when $(G_n)_{n\geq 0}=(F_n)_{n\geq 0}$. More precisely, we prove that

\begin{theorem}\label{main2}
If 
\begin{equation}
xF_{n+a}+F_{n}=F_m
\end{equation}
for infinitely many pairs $(n,m)$ of positive integers, then there exists a nonnegative integer $k$ such that
\begin{center}
$a=2k+1$, $m=n+4k+2$ and $x=L_{2k+1}$. 
\end{center}
In particular, we have the identity
\[
L_{2k+1}F_{n+2k+1}+F_{n}=F_{n+4k+2},
\]
for all $n,k\geq 0$.
\end{theorem}



\section{General recurrence sequences}

\subsection{Auxiliary facts}\label{sec2}



In this section, we recall some results that will be very useful for the proof of the above theorems. Let $\psi(x)$ be the characteristic polynomial of a linear recurrence $(G_n)_{n\geq 0}$. One can factor $\psi(x)$ over the set of complex numbers as
\begin{equation}
\psi(x)=(x-\a_1)^{m_1}(x-\a_2)^{m_2}\cdots (x-\a_{t})^{m_{t}},
\end{equation}
where $\a_1,\ldots,\a_{t}$ are distinct non-zero complex numbers (called the {\it roots} of the recurrence) and $m_1,\ldots,m_{t}$ are positive integers. The fundamental result in the theory of recurrence sequences asserts that there exist uniquely determined non-zero polynomials $g_1,\ldots,g_{\ell}\in \mathbb{Q}(\{\a_j\}_{j=1}^{t})[x]$, with $\deg g_j\leq m_j-1$, for $j=1,\ldots,t$, such that
\begin{equation}\label{written}
G_n=g_1(n)\a_1^n+\cdots +g_{t}(n)\a_{t}^n,\ \mbox{for\ all}\ n.
\end{equation}
For more details, see \cite[Theorem C.1]{shorey}. A root $\a_j$ of the recurrence is called the {\it dominant root} if $|\a_j|&gt;|\a_i|$, for all $j\neq i\in \{1,\ldots,t\}$. The corresponding polynomial $g_j(n)$ is called the \textit{dominant polynomial} of the recurrence.

In the case of the Fibonacci and Lucas sequences, the above formula is known as {\it Binet's formula}:
\begin{equation}\label{binet1}
F_n=\displaystyle\frac{\alpha^n-\beta^n}{\alpha-\beta}\ \mbox{and}\ L_n=\alpha^n+\beta^n,
\end{equation}
where $\alpha=(1+\sqrt{5})/2$ (the golden number) and $\beta=(1-\sqrt{5})/2=-1/\alpha$.
\smallskip
Now we prove some lemmas that are essential ingredients in what follows. Throughout the paper, $\a_1$ denotes the dominant root of $(G_n)_{n\geq 0}$. 

\begin{lemma}\label{l1}
Let $\ell$ be any integer and let $(G_n)_{n\geq 0}$ be any linear integer sequence satisfying the hypotheses of the Theorem \ref{main1}. Then 
\begin{equation}
\displaystyle\lim_{n\to \infty} \frac{G_{n+\ell}}{G_n}=\alpha_1^{\ell}.
\end{equation}
\end{lemma}
\noindent
{\bf Proof.} The proof can be found in \cite[Lemma 1]{chaos}.


Now we are ready to deal with the proofs of our results. 

\subsection{The proof of Theorem 1}\label{s1}



Suppose that $x G_{n+a}+G_{n} = G_{t(n)}$ for infinitely many $n$ (say, $n\in S$), where $t(n)\in \Z$, for all $n$. By dividing the relation $x G_{n+a}+G_{n} = G_{t(n)}$ by $G_n$, we obtain $x \frac{G_{n+a}}{G_n}+1 = \frac{G_{t(n)}}{G_n}$. Now, by letting $n\to \infty$ ($n\in S$) in the previous relation, by using Lemma \ref{l1} and the fact that the algebraic conjugates of $\a_1$ lie on the unit circle, we get $x\a_1^a+1= \lim_{n\to \infty, n\in S}\alpha_1^{t(n)-n}$. Then, since $|\a_1|&gt;1$, the limit $\lim_{n\to \infty, n\in S}{(t(n)-n)}$ exists and is finite. However, $t(n)-n$ is a sequence of integers, and so it must be constant for all sufficiently large $n$ (in $S$). We let  $b$ denote that constant. Therefore, we can rewrite this identity as
\begin{eqnarray}\label{BG}
\alpha_1^a x + 1 = \alpha_1^{b}.
\end{eqnarray}

Set $\K=\Q(\{\a_i\}_{i=1}^t)$. If $\beta\in \{\a_2,\ldots, \a_t\}$ and $|\beta|=\max\{ |\alpha_2|, \dots, |\alpha_t|\}$, then
consider the automorphism $\sigma$ in $\mbox{Gal}(\K/\Q)$ given by $\alpha_1 \mapsto \beta$. By applying $\sigma$ in the equality in (\ref{BG}), we obtain
\begin{equation}
\beta^a x + 1 = \beta^b.
\end{equation}

Now taking absolute values, together with the reverse triangular inequality and by using the fact that $|\beta|&lt;1$, we arrive at
\[
|\beta|^a x - 1 \leq  |\beta^a x + 1 |= | \beta|^{b} &lt; 1.
\]
This implies that $x&lt; 2/|\beta|^a$, which completes our proof.


\section{The Fibonacci case}

In the case of Fibonacci numbers, we use the previous theorem to obtain that if 
\[
xF_{n+a}+F_n
\]
is a Fibonacci number for infinitely many integers $n$, then $x&lt;2/|\beta|^a=2\alpha^a$, since $\a\beta=-1$.

Now we can use the same machinery of the previous section to arrive at the Diophantine equation
\begin{equation}\label{Fib}
x\a^a+1=\a^b. 
\end{equation}
Clearly, this implies that $a&lt;b$ (since $x\geq 1$). Also, by using that $x&lt;2\a^a$, we get
\[
\a^b=x\a^a+1&lt;2\a^{2a}+1&lt;3\a^{2a}&lt;\a^{2a+3},
\]
where we used the fact that $\a^3&gt;3$. Thus, $b&lt;2a+3$. The case $a=1$ was already treated in \cite[Theorem 2]{chaos}. If $a=2$, then we have that $1\leq x&lt;2\alpha^2&lt;6$ and $2&lt;b&lt;7$. By using a simple {\it Mathematica} routine, we obtain that there is no solution to 
\[
x\a^2+1=\a^b 
\]
in the range $1\leq x\leq 5$ and $3\leq b\leq 6$. Thus, we may suppose that $a&gt;2$. 

Now let us conjugate the relation in (\ref{Fib}) by the Galois automorphism $\a\mapsto \beta$. Hence, we have
\begin{equation}\label{Fib2}
x\beta^a+1=\beta^b. 
\end{equation}
By subtracting (\ref{Fib}) and (\ref{Fib2}), we obtain
\[
x(\a^a-\beta^a)=\a^b-\beta^b,
\]
which yields $xF_a=F_b$, by Binet's formula. This implies that $F_a\mid F_b$ and so $a\mid b$. However, $a&lt;b&lt;2a+3\leq 3a$ (this last inequality holds because $a\geq 3$) and therefore $b=2a$. Thus, $x=F_{b}/F_a=F_{2a}/F_a=L_a$. Now it remains to prove that $a$ is an odd number. In fact, by (\ref{Fib}), we have
\[
L_a\a^a+1=\a^{2a}
\]
and by Binet's formula
\[
\a^{2a}=L_a\a^a+1=(\a^a+\beta^a)\a^a+1=\a^{2a}+(\a\beta)^a+1.
\]
Thus, 
\[
0=(\a\beta)^a+1=(-1)^a+1
\]
implying that $a$ is odd. The result is proved. 

\section{Conclusion}

In this paper, we proved that if we have a linear recurrence sequence $(G_n)_{n\geq 0}$ satisfying some weak technical conditions (related to its roots) and if we have an identity of the form $xG_{n+a}+G_{n}=G_m$ valid for infinitely many integers pairs $(n,m)$, then the value of $x$ must be bounded by $2/|\beta|^a$, where $\beta$ is the second largest root (in absolute value) of the recurrence. This result provides a very efficient way of finding possible identities, since this ``second largest root" can be bounded (or even found) in an effective way. 
As an application, we worked on the case of Fibonacci numbers and we determined all identities in this case. In particular, we proved that $x$ is a Lucas number with odd index. 

\section{Acknowledgement}
I wish to thank to an annonymous reviwer for his/her constructive
critisms and I thank for the support the Specific research 2018/No.~2101 of University of Hradec Kr\'alov\'e.


\begin{thebibliography}{9}

\bibitem{BrLu}  J. J.  Bravo and F. Luca,  Coincidences in generalized Fibonacci sequences, {\it J. Number Theory} {\bf 133} (2013), 2121--2137.

\bibitem{CaSo}
L. Carlitz and R. Scoville,  Partially ordered sets associated with Fibonacci representations, {\it Duke Math. J.} {\bf 40} (1973), 511--524.

\bibitem{FIB3} T. Koshy,  {\it Fibonacci and Lucas Numbers with
Applications}, Wiley, 2001.

\bibitem{MAR1} D. Marques,  The proof of a conjecture concerning the
intersection of $k$-generalized Fibonacci sequences, {\it Bull. Brazilian
Math. Soc.} {\bf 44} (2013), 455--468.

\bibitem{shorey}  T. N.  Shorey and R. Tijdeman,  {\it Exponential
Diophantine Equations. Cambridge Tracts in Mathematics 87}, Cambridge
University Press, 1986.

\bibitem{chaos} P. Trojovsk\' y,  On some combinations of terms of a recurrence sequence, {\it Chaos Solitons Fractals} {\bf 82} (2016), 34--37.

\bibitem{chaos2} P. Trojovsk\' y,  On some combinations of $k$-nacci numbers, {\it Chaos Solitons Fractals} {\bf 85} (2016), 135--137.


\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11D61; Secondary 11B39.

\noindent \emph{Keywords: } 
combination, recurrence sequence, characteristic polynomial, Fibonacci number.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A000045}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received February 19 2018;
revised version received  March 11 2018.
Published in {\it Journal of Integer Sequences}, March 12 2018.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                


</pre></body></html>