\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>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< \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>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}<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|>|\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|>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|<1$, we arrive at \[ |\beta|^a x - 1 \leq |\beta^a x + 1 |= | \beta|^{b} < 1. \] This implies that $x< 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<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 $a3$. Thus, $b<2a+3$. The case $a=1$ was already treated in \cite[Theorem 2]{chaos}. If $a=2$, then we have that $1\leq x<2\alpha^2<6$ and $22$. 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