\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}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

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

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}

\newcommand{\tmop}[1]{\ensuremath{\operatorname{#1}}}

\newtheorem{open problem}{Open Problem}


\begin{center}
\vskip 1cm{\LARGE\bf On Fibonacci-Like Sequences
}
\vskip 1cm
\large
Le Anh Vinh \\
School of Mathematics\\
University of New South Wales\\
Sydney 2052 NSW\\
Australia\\
\href{mailto:vinh@maths.unsw.edu.au}{\tt vinh@maths.unsw.edu.au} \\
\end{center}

\vskip .2 in
\begin{abstract}
In this note, we study Fibonacci-like sequences that are defined by the
recurrence $S_k = a$, $S_{k + 1} = b$, $S_{n + 2} \equiv S_{n + 1} +
S_n$ (mod $n + 2$) for all $n \geq k$, where $k, a, b \in \mathbb{N}$,
$0 \leq a < k$, $0 \leq b < k+ 1$, and $(a,b)\ne (0,0)$. We will show
that the number $\alpha = 0.S_k S_{k+1} S_{k+2} \cdots$ is irrational.
We also propose a conjecture on the pattern of the sequence $\{S_n\}_{n
\geq k}$.
\end{abstract}

\section{Introduction}

Given a sequence of natural numbers $a_1, a_2, \ldots$,
the question of determining the irrationality
of the number $\alpha = 0.a_1a_2\cdots$ is a 
classical and interesting question.
For example, if $a_1,a_2,\ldots$ is the sequence of all prime numbers,
then $\alpha$ is irrational (\cite{hegyvari}).
Another well-known example is the set of generalized Mahler sequences.
Let $m \geq 1$, $h \geq 2$ be integers, and
\[(m)_h= m_1h^{r-1}+m_2h^{r-2}+\cdots+m_r\]
for some integer $r > 0$ and $0 \leq m_i <h$ for all $1\leq i \leq r$.
Mahler \cite{mahler} showed that for $t \geq 2$ then the number
\[a(t) = 0.(t^0)_{10}(t^1)_{10}(t^2)_{10}\cdots\] is irrational. Bundschuh \cite{bundschuh} generalized this result to arbitrary bases.  More precisely,
he showed that for any $t, r \geq 2$ then the number
\[a_r(t)=0.(t^0)_r(t^1)_r(t^2)_r\cdots\]
is irrational.
Readers can find several proofs of this result in \cite{niederreiter, shan}. In the most general form, one studies the number
\[a_r(t) = a_r^{(n_i)}(t) = 0.(t^{n_0})_r(t^{n_1})_r(t^{n_2})_r\cdots\]
for given $r,t\geq 2$ and sequence $(n_i)_{i\geq 0}$ of non-negative integers. 
In \cite{shanwang}, Shan and Wang showed that $a_r(t)$ is irrational if $(n_i)$ is an unbounded sequence. Several criteria for irrationality of $a_r(t)$ for bounded $(n_i)$ were obtained by Sander \cite{sander}, and Shorey and Tijdeman \cite{shoreytijdeman}. Motivated by these papers, we will study an analogous result for some Fibonacci-like sequences. 

Recall that the Fibonacci sequence is defined by the following recurrence:
\[ F_0 = 0,\ F_1 = 1,\ F_{n + 2} = F_{n + 1} + F_n \ \tmop{for} \tmop{all} \  n
   \geq 0. \]
In this note, we will study some properties of Fibonacci-like sequences that
are defined by the following recurrence:
\begin{equation}\label{mot} S_k = a,\ S_{k + 1} = b,\ S_{n + 2} \equiv S_{n + 1} + S_n \tmop{(mod} n + 2
   \tmop{)} \qquad \tmop{for} \tmop{all} \qquad n \geq k, \end{equation}
for some $k, a, b \in \mathbb{N}$, $0 \leq a < k$ and $0 \leq b < k
+ 1$. For any triple $( k, a, b ) \in \mathbb{N}^3$ with $0 \leq a < k$
and $0 \leq b < k + 1$, we denote $S_{a, b}^k = \{ S_{a, b}^k ( n ) \}_{n
= k}^{\infty}$ the sequence defined by recurrence (\ref{mot}). 

The main result of this note is the following theorem.

\begin{theorem} \label{main}
  Suppose that $a, b, k$ are natural numbers with $0 \leq a < k, 0
  \leq b < k + 1$. Then
  \begin{equation}\label{v} \alpha_{a, b}^k = 0. S_{a, b}^k ( k ) S_{a, b}^k ( k + 1 ) S_{a, b}^k ( k
     + 2 ) \ldots \end{equation}
  is irrational.  Here expression (\ref{v})
means that the decimal expansion of $\alpha_{a,b}^k$ is obtained by the
concatenation of the integers $S_{a,b}^k(n)$ written in decimal form.
\end{theorem}

It is worth noticing
that most of papers inspired by Mahler deal with exponentially increasing
sequences, while $S_{a,b}^k$ is always less than $n$. Furthermore, while the Fibonacci
sequence is well-known and has been studied extensively in the literature,
it seems that the
sequence $S_{a, b}^k$ has not been studied before. The only reference we found
about these sequences refers to $S_{0, 1}^0$.
This sequence is known as sequence \seqnum{A056542}
in Sloane's Online Encyclopedia of Integer Sequences \cite{seq}. 

\section{Irrationality}

In order to give a proof for Theorem \ref{main}, we first need some lemmas.

\begin{lemma}\label{theorem 1}
  Suppose that $a, b, k \in \mathbb{N}$ such that $0 \leq a < k, 0
  \leq b < k + 1$, $( a, b ) \neq ( 0, 0 )$. Then the sequence $S_{a,
  b}^k$ is not bounded.
\end{lemma}

\begin{proof}
Suppose that $S_{a, b}^k$ is bounded for some $a, b, k$. Let $M =
\max_{n\geq k} \{ S_{a, b}^k ( n ) \}$.  Then, for every $n > 2M$, we have
$S_{a,b}^k(n) = S_{a,b}^k(n-1) + S_{a,b}^k(n-2)$, since
$S_{a,b}^k(n-1) \leq M$ and $S_{a,b}^k(n-2) \leq M$. Thus, the
sequence $S_{a,b}^k$ eventually coincides with a usual linear
recurrence sequence taking non-negative values.  Since $S_{a,b}^k$ is
bounded it immediately follows that 
$$S_{a,b}^k(n-1) = S_{a,b}^k(n-2) = 0.$$
By backward induction, we have $S_{a,b}^k(n) = 0$ for all $n$,
which is a contradiction. This concludes the proof of the lemma.
\end{proof}

\begin{lemma} \label{lemma 1}
For any sufficiently large $m$,
there exists $n$ such that $S_{a, b}^k ( n )$ has
exactly $m$ digits. In other words, there exists $n$ such that $10^{m - 1}
\leq S_{a, b}^k ( n ) < 10^m$.
\end{lemma}

\begin{proof}
  From Lemma \ref{theorem 1}, the sequence $\{ S_{a, b}^k ( n ) \}_{n\geq k}$ is unbounded. Hence
  there exists $n$ such that $S_{a, b}^k ( n ) \geq 10^{m - 1}$. We
  choose $n$ as small as possible. Then $S_{a, b}^k ( n - 1 ), S_{a, b}^k ( n - 2
  ) < 10^{m - 1}$. This implies that
  \[ S_{a, b}^k ( n ) \leq S_{a, b}^k ( n - 1 ) + S_{a, b}^k ( n - 2 ) <
     2 \times 10^{m - 1} < 10^m . \]
  This concludes the proof of the lemma.
\end{proof}

Using Lemma \ref{theorem 1} and Lemma \ref{lemma 1}, we get the following proof of Theorem \ref{main}.

\begin{proof} (of Theorem \ref{main})
  Suppose that $\alpha_{a, b}^k$ is a rational number for some $a, b, k$. Then
  it has an eventually periodic decimal expansion. Thus we can write
  \[ \alpha_{a, b}^k = 0. a_1 \ldots a_s b_1 \ldots b_t b_1 \ldots b_t \ldots
  \]
  We choose $n$ large enough such that $S_{a, b}^k ( n )$ starts from a
  position after $a_s$. Then for any $r \geq n$, the number $\alpha_r =
  S_{a, b}^k ( r ) S_{a, b}^k ( r + 1 ) S_{a, b}^k ( r + 2 ) \ldots$ is  
  periodic of period $w t$ for any positive integer $w$. We choose $m = v t$ for some large positive integer $v$
  such that $10^{m - 1} > S_{a, b}^k ( i ) $ for all $i \leq n$. From
  Lemma \ref{lemma 1}, there exists $l$ such that $S_{a, b}^k ( l )$ has exactly $m$
  digits. We choose $l$ to be as small as possible;
  then $l > n$.
  
  If $S_{a, b}^k ( l - 1 ) = 0$, then $S_{a, b}^k ( l - 2 ) = S_{a, b}^k
  ( l )$ has exactly $m$ digits, which is a contradiction. Hence $0 < S_{a,
  b}^k ( l - 1 ) < 10^{m - 1}$.  Similarly, we have $0 < S_{a, b}^k ( l - 2 )
  < 10^{m - 1}$. Hence
  \begin{eqnarray*}
    S_{a, b}^k ( l ) \leq S_{a, b}^k ( l - 2 ) + S_{a, b}^k ( l - 1 ) < 2
    \times 10^{m - 1},\\
    S_{a, b}^k ( l + 1 ) \leq S_{a, b}^k ( l - 1 ) + S_{a, b}^k ( l ) < 3
    \times 10^{m - 1}. 
  \end{eqnarray*}
  Therefore, $S_{a, b}^k ( l + 1 )$ has no more than $m$ digits. We have two
  separate cases.
  \begin{itemize}
    \item[1.]   Suppose that $S_{a, b}^k ( l + 1 ) \equiv S_{a, b}^k ( l - 1 ) +
    S_{a, b}^k ( l )$ (mod $l + 1$) has $m$ digits. But $\alpha_l = S_{a, b}^k
    ( l ) S_{a, b}^k ( l + 1 ) S_{a, b}^k ( l + 2 ) \ldots$ is periodic of
    period $m = v t$ so $S_{a, b}^k ( l + 1 ) = S_{a, b}^k ( l )$. This
    implies that $S_{a, b}^k ( l - 1 ) = 0$ which is a contradiction.
    
    \item[2.] Suppose that $S_{a, b}^k ( l + 1 ) \equiv S_{a, b}^k ( l - 1 ) +
    S_{a, b}^k ( l )$ (mod $l + 1$) has less than $m$ digits. Let $p = S_{a,
    b}^k ( l + 1 )$. Since $\alpha_l = S_{a, b}^k ( l ) S_{a, b}^k ( l + 1 )
    S_{a, b}^k ( l + 2 ) \ldots$ is periodic of period $m = v t$ so $S_{a,
    b}^k ( l ) = p * q$ for some $q$ where $p*q$ denotes the concatenation of $p$ and $q$. We have
    \[ S_{a, b}^k ( l + 2 ) \leq S_{a, b}^k ( l + 1 ) + S_{a, b}^k ( l )
       < 10^{m - 1} + 2 \times 10^{m - 1} < 3 \times 10^{m - 1} . \]
    So $S_{a, b}^k ( l + 2 )$ has no more than $m$ digits. We have two
    subcases.
    \begin{itemize}
      \item[(a)] Suppose that $S_{a, b}^k ( l + 2 )$ has exactly $m$ digits. Then
      by the periodicity of $\alpha_l$ we have $S_{a, b}^k ( l ) S_{a, b}^k (
      l + 1 ) S_{a, b}^k ( l + 2 ) = p *q *p *q * p$. If $S_{a, b}^k ( l ) + S_{a,
      b}^k ( l + 1 ) \geq l + 2$ then
      \[ S_{a, b}^k ( l ) + S_{a, b}^k ( l + 1 ) < l + 10^{m - 1} < l + 2 +
         10^{m - 1}, \]
      which implies that $S_{a, b}^k ( l + 2 ) < 10^{m - 1}$ which is a
      contradiction. Hence
      \[ S_{a, b}^k ( l ) + S_{a, b}^k ( l + 1 ) < l + 2 . \]
      This implies that $q* p = S_{a, b}^k ( l + 2 ) = S_{a, b}^k ( l ) + S_{a,
      b}^k ( l + 1 ) = p* q + p$. Suppose that $p* q = 10^h p + q$ and $q* p =
      10^z q + p$. Then $q ( 10^z - 1 ) = 10^h p$. Thus, $10^h  \mid q$. But $p* q = 10^h p + q$ so $q < 10^h$. Hence $q = 0$ and $p=0$ which is a contradiction.
      
      \item[(b)] Suppose that $S_{a, b}^k ( l + 2 )$ has less than $m$ digits. Then
      we can replace $k$ by $l + 1$. And we choose $l'$ to be the smallest $l' >
      l$ such that $S_{a, b}^l ( l' )$ has exactly $m$ digits.  Apply the
      above argument for the new sequence $S_{a, b}^l$ until either we come up
      with a contradiction or we can choose $l'$ large enough such that $l' +
      1 > 3 \times 10^{m - 1}$. But in this case
      \[ S_{a, b}^k ( l' + 1 ) \leq S_{a, b}^k ( l' - 1 ) + S_{a, b}^k (
         l' ) < 3 \times 10^{m - 1} < l' + 1. \]
      So $S_{a + b}^k ( l' + 1 )$ has exactly $m$ digits. And we go to the
      case 1 which implies a contradiction.
    \end{itemize}
  \end{itemize}
  This concludes the proof of the theorem.
\end{proof}

We close this section by an open question.
\begin{open problem}
For $a, b, k$ are natural numbers with $0 \leq a < k, 0
\leq b < k + 1$. Is $\alpha_{a, b}^k$ an algebraic or transcendental
number?
\end{open problem}

\section{Occurrence of zeros}

By examining several sequences for small values of $a, b$ and $k$, we notice a
curious property of the sequence $S_{a, b}^k$: this sequence always
contains many zeros.  We are unable to prove this statement.
Precisely, we propose the
following conjecture.

\begin{conjecture}\label{conj 1}
Let $a, b, k$ be natural numbers with $0 \leq a < k, 0
\leq b < k + 1$. Then the sequence $S_{a, b}^k$ contains infinitely many
zero elements.
\end{conjecture}

Suppose that the sequence $S_{a, b}^k$ contains only finitely many zero elements for
some $a, b, k$. Let $v$ be the largest index such that $S_{a, b}^k ( v ) = 0$.
Let $c = S_{a, b}^k ( v + 1 )$ and $d = S_{a, b}^k ( v + 2 )$. Then the
sequence $S_{c, d}^{v + 1}$ contains no zero element. Therefore the conjecture
is equivalent to the statement ``there exists $n$ such that $S_{a, b}^k ( n )
= 0$ for any $a, b, k$''.

If Conjecture \ref{conj 1} holds, let $v_k ( a, b )$ be the index of the
first zero element in sequence $S_{a, b}^k$. We define
\[ v_k = \max_{0 \leq a < k, 0 \leq b < k + 1} v_k ( a, b ) . \]
For any $0 \leq a < k$ and $0 \leq b < k + 1$ then $S_{a,
b}^k = \{a\} \cup S_{b, c}^{k + 1}$ for some $0 \leq c < k + 2$.
Thus, $v_k \leq v_{k + 1}$ for any $k$. Furthermore, $v_{v_k + 1} \geq
v_k + 1 > v_k$ for any $k$. Hence
\[ \lim_{k \rightarrow \infty} v_k = \infty . \]
Using computer, we computed some values of the sequence $\{ v_k \}_{k
\in \mathbb{N}}$
\[ \{ v_k \}_{k \geq 1} = \{ 28, 28, 108, 108, 130, 130, 184, 184, 184,
   1523, 1523, \ldots \} . \]

\section{Acknowledgment}

The author would like to thank the referee for giving many useful
comments which helped improve the presentation of this note, as well as
pointing out some papers related to the work.


\begin{thebibliography}{99}

\bibitem{amou}
M. Amou, Approximation to certain transcendental decimal fractions by algebraic numbers, \textit{J. Number Theory} \textbf{37} (1991), 231--241.

\bibitem{becker}
P. G. Becker, Exponential diophantine equations and the irrationality of certain real numbers, \textit{J. Number Theory} \textbf{39} (1991), 108--116.


\bibitem{beckersander}
P. G. Becker and J. W. Sander, Irrationality and codes, \textit{Semigroup Forum} \textbf{51} (1995), 117--124.

\bibitem{bundschuh} P. Bundschuh, Generalization of a recent irrationality result of Mahler, \textit{J. Number Theory} \textbf{19} (1984), 248--253.

\bibitem{hegyvari}
N. Hegyvari, On some irrational decimal fractions, \textit{Amer. Math. Monthly} \textbf{100} (1993), 779--780.

\bibitem{mahler}
K. Mahler, On some irrational decimal fractions, \textit{J. Number Theory} \textbf{13} (1981), 268--269.

\bibitem{niederreiter}
H. Niederreiter, On an irrationality theory of Mahler and Bundschuh, \textit{J. Number Theory} \textbf{24} (1986), 197--199.

\bibitem{sander}
J. W. Sander, Irrationality criteria for Mahler's numbers,
\textit{J. Number Theory} \textbf{52} (1995), 145--156.


\bibitem{shan}
Z. Shan, A note on irrationality of some numbers, \textit{J. Number Theory} \textbf{25} (1987), 211--212.

\bibitem{shanwang}
Z. Shan and E. T. H. Wang, Generalization of a theorem of Mahler, \textit{J. Number Theory} \textbf{32} (1989), 111--113.

\bibitem{shoreytijdeman}
T. N. Shorey and R. Tijdeman, Irrationality criteria for numbers of Mahler's type, in Y. Motohashi, ed., \textit{Analytic Number Theory}, London Mathematical Lecture Note Series \textbf{247}, Cambridge, 1997, pp.\ 343--351.

\bibitem{seq}
N. J. A. Sloane,
{\em The On-Line Encyclopedia of Integer Sequences},
published electronically at 
\href{http://www.research.att.com/~njas}{\tt http://www.research.att.com/\char'176njas}.

\bibitem{vijayaraghavan}
T. Vijayaraghavan, On the irrationality of a certain decimal, \textit{Proc. Indian Acad. Sci. Sect. A} \textbf{10} (1939), 341.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: 05A15.

\noindent \emph{Keywords: } Fibonacci sequence, irrationality, Mahler-type problem.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A056542}.)
\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 21 2005; 
revised version received November 28 2007.
Published in {\it Journal of Integer Sequences}, November 28 2007.

\bigskip
\hrule
\bigskip

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



\end{document}