2 Proof of Theorem 1.2

Case 1: $x_3=2$ . Since $k\geq 0$ , $2 \mid k$ and $\phi (x_1)+\phi (x_2)+k=x_3=2$ , we must have $k=0$ and $\phi (x_1)=\phi (x_2)=1$ . Hence, $x_1,x_2\in \{1,2\}$ . Note that if ${\phi (x_n)=\phi (x_{n-1})=1}$ , then $x_{n+1}=\phi (x_n)+\phi (x_{n-1})=2$ . By induction, $x_n=2$ for all $n\geq 3$ . Since $X=x_1+x_2+ 2k\geq 2$ , we have $2^{2X^2+X-3}>2$ . Hence, ${x_n< 2^{2X^2+X-3}}$ for all $n\geq 1$ .

Case 2: $x_3\geq 3$ . Then $x_{4}=\phi (x_3)+\phi (x_2)+k\geq 3$ . Note that if $x_n\geq 3$ with $n\geq 3$ , then

$$ \begin{align*}x_{n+1}=\phi(x_n)+\phi(x_{n-1})+k\geq 3+k\geq 3.\end{align*} $$

By induction, $x_n\geq 3$ for all $n\geq 3$ , so that $2 \mid \phi (x_n)$ for all $n\geq 3$ . Therefore, ${2 \mid \phi (x_{n-1})+\phi (x_{n-2})+k=x_n}$ for all $n\geq 5$ and so

(2.1) $$ \begin{align} \phi(x_n)\leq \dfrac{n}{2} \quad\mbox{for all } n\geq 5. \end{align} $$

Lemma 2.1. For $n=1,2,\ldots ,6$ ,

(2.2) $$ \begin{align} x_n< 2^{X}. \end{align} $$

Proof. We consider each value of n in turn.

$n=1$ or $n=2$ . Then (2.2) holds because $\max \{x_1,x_2\}<x_1+x_2\leq X<2^{X}$ .

$n=3$ . Then (2.2) holds because $3\leq x_3=\phi (x_1)+\phi (x_2)+k\leq x_1+x_2+k\leq X<2^{X}$ .

$n=4$ . Since $\phi (x_3)\leq x_3-1\leq x_1+x_2+k-1$ and $\phi (x_2)\leq x_2$ ,

$$ \begin{align*} x_4=\phi(x_3)+\phi(x_2)+k \leq x_1+2x_2+2k-1 <2X\leq 2^{X} \quad (\text{since}\ 2^X\geq 2X\ \text{for}\ X\geq 2). \end{align*} $$

$n=5$ . Since $\phi (x_4)\leq x_4-1\leq x_1+2x_2+2k-2$ and $\phi (x_3)\leq x_1+x_2+k-1$ ,

(2.3) $$ \begin{align} x_5=\phi(x_4)+\phi(x_3)+k &\leq 2x_1+3x_2+4k-3\nonumber\\[2pt]&=3(x_1+x_2+2k)-x_1-2k-3\nonumber\\[2pt]&\leq 3X-4\quad (\text{since}\ x_1+2k+3\geq 4)\nonumber\\[2pt]&<2^X \quad(\text{since}\ 2^X>3X-4\ \mathrm{for}\ X\geq 2). \end{align} $$

$n=6$ . By (2.1) and (2.3), $\phi (x_5)\leq x_5/2\leq (2x_1+3x_2+4k-3)/2$ . Combining this with the estimate $\phi (x_4)\leq x_1+2x_2+2k-2$ gives

$$ \begin{align*} x_6=\phi(x_5)+\phi(x_4)+k &\leq \dfrac{2x_1+3x_2+4k-3}{2}+(x_1+2x_2+2k-2)+k\\[4pt]&=\dfrac{4x_1+7x_2+10k-7}{2} =\dfrac{7(x_1+x_2+2k)}{2}-\dfrac{3x_1+4k+7}{2}\\&\leq \dfrac{7}{2}X-5\quad(\text{since}\ (3x_1+4k+7)/2\geq 5\\&<2^X\quad(\text{since}\ 2^X>7X/2-5\ \text{for}\ X\geq 2).\\[-35pt] \end{align*} $$

We now return to the proof of Theorem 1.2 when $x_3\ge 3$ (Case 2).

Case 2.1: $k=0$ . Then $x_n=\phi (x_{n-1})+\phi (x_{n-2})$ for all $n\geq 3$ . By (2.1),

(2.4) $$ \begin{align} x_{n+2}=\phi(x_{n+1})+\phi(x_{n})\leq \dfrac{x_{n+1}}{2}+\dfrac{x_n}{2}\quad \text{for all}\ n\geq 5. \end{align} $$

An induction, using Lemma 2.1 and (2.4), shows that $x_n< 2^X$ for all $n\geq 1$ . Hence, $x_n<2^X<2^{2X^2+X-3}$ for all $n\geq 1$ .

Case 2.2: $k\geq 1$ . Let $p_1<p_2<\cdots <p_{2k+2}$ be the first $2k+2$ primes. By the Chinese remainder theorem, there exist infinitely many positive integers x such that

(2.5) $$ \begin{align} x\equiv - i \pmod{p_i}\quad \text{for all}\ i=1,2,\ldots,2k+2. \end{align} $$

Lemma 2.2. Let M be a positive integer satisfying the congruences (2.5) and such that $M\geq \max \{2^{X}-2k-2,kp_{2k+2}-k-2\}$ . Then, for all positive integers n,

(2.6) $$ \begin{align} x_{n}\leq M+2k+2. \end{align} $$

Proof. Since $M+2k+2\geq 2^{X}$ , by Lemma 2.1, (2.6) holds for $n=1,2,\ldots ,6$ . Suppose $n\geq 7$ and assume that Lemma 2.2 is not true. Let m be the smallest positive integer such that $x_m>M+2k+2$ . Then $x_{m-1},x_{m-2}\leq M+2k+2$ and $m\geq 7$ . Thus, $2 \mid x_{m-1}, x_{m-2}$ . Therefore,

$$ \begin{align*} M+2k+2<x_m=\phi(x_{m-1})+\phi(x_{m-2})+k\leq \dfrac{x_{m-1}}{2}+\dfrac{x_{m-2}}{2}+k \end{align*} $$

and so $x_{m-1}+x_{m-2}>2M+2k+4$ . It follows that $x_{m-1},x_{m-2}>M+2$ since $x_{m-1},x_{m-2}\leq M+2k+2$ . Let $x_{m-1}=M+2+r$ and $x_{m-2}=M+2+s$ , where $r,s\in {\mathbb{Z}} $ and $0< r,s\leq 2k$ . Since M satisfies (2.5), there exist odd primes $p,q\leq p_{2k+2}$ such that $p \mid M+2+r=x_{m-1}$ and $q \mid M+2+s=x_{m-2}$ . Therefore, $2p \mid x_{m-1}$ and $2q \mid x_{m-2}$ . Recalling that $x_{m-1},x_{m-2}\leq M+2k+2$ and $p,q\leq p_{2k+2}$ ,

$$ \begin{align*} x_{m}=\phi(x_{m-1})+\phi(x_{m-2})+k &\leq \dfrac{x_{m-1}}{2}\bigg(1-\dfrac{1}{p}\bigg)+\dfrac{x_{m-2}}{2}\bigg(1-\dfrac{1}{q}\bigg)+k\\ &\leq 2\cdot \dfrac{M+2k+2}{2}\bigg(1-\dfrac{1}{p_{2k+2}}\bigg)+k \\ &= (M+2k+2)\bigg(1-\dfrac{1}{p_{2k+2}}\bigg)+k\\ &\leq M+2k+2\quad (\text{since}\ M+2k+2\geq p_{2k+2}k), \end{align*} $$

which contradicts the assumption that $x_m>M+2k+2$ . Therefore, (2.6) holds for all positive integers n. Lemma 2.2 is proved.

Lemma 2.3 (Rosser [Reference Rosser4, Theorem 2])

For all positive integers $n\geq 4$ ,

$$ \begin{align*}p_n<n(\log n+ 2\log \log n),\end{align*} $$

where $p_n$ is the nth prime and $\log $ denotes the natural logarithm.

Lemma 2.4 (Erdős [Reference Erdős2]; see Aigner and Ziegler [Reference Aigner and Ziegler1, Ch. 2, page 10])

For all positive integers $n\geq 2$ ,

$$ \begin{align*}\prod_{p\leq n}p\leq 4^{n-1},\end{align*} $$

where the product is taken over all primes $p\leq n$ .

Lemma 2.5. For all positive integers $n\geq 4$ ,

(2.7) $$ \begin{align}p_{n}<n^2,\end{align} $$

(2.8) $$ \begin{align} p_1p_2\cdots p_{n}<4^{n^2-1}.\end{align} $$

Proof. It is a routine verification that $\log {x}+2\log {\log {x}}<x$ for all $x>1$ . Hence,

(2.9) $$ \begin{align}n(\log{n}+2\log\log{n})<n^2.\end{align} $$

Then (2.7) follows from Lemma 2.3 and inequality (2.9).

Inequality (2.8) is a consequence of Lemma 2.4 and (2.7). Indeed,

$$ \begin{align*} p_1p_2\cdots p_n\leq 4^{p_n-1} < 4^{n^2-1}.\\[-33pt] \end{align*} $$

We return to the proof of Theorem 1.2. Let $\alpha $ be the smallest positive integer satisfying (2.5). Then $\alpha \leq p_1p_2\cdots p_{2k+2}$ . Note that $4\leq 2k+2\leq 2k+x_1+x_2=X$ . It follows from (2.8) that

(2.10) $$ \begin{align} \alpha\leq p_1p_2\cdots p_{2k+2}< 4^{(2k+2)^2-1} \leq 4^{X^2-1}. \end{align} $$

Let $M=\alpha +2^{x_1+x_2}p_1p_2\cdots p_{2k+2}$ . Then M satisfies (2.5). Since $p_1p_2\cdots p_{2k+2}>2^{2k}$ and $p_1p_2\cdots p_{2k+2}>p_kp_{2k+2}>kp_{2k+2}$ ,

$$ \begin{align*}M>2^{x_1+x_2}p_1p_2\cdots p_{2k+2}>2^{x_1+x_2}2^{2k}=2^X\end{align*} $$

and

$$ \begin{align*}M>p_1p_2\cdots p_{2k+2}>kp_{2k+2}.\end{align*} $$

Thus, M satisfies all the conditions in Lemma 2.2. Hence,

(2.11) $$ \begin{align}x_n\leq M+2k+2 \quad\text{for all}\ n\geq 1.\end{align} $$

Since $x_1+x_2=X-2k\leq X-2$ , by (2.10),

(2.12) $$ \begin{align} M=\alpha+2^{x_1+x_2}p_1p_2\cdots p_{2k+2} < (1+2^{X-2})\cdot 4^{X^2-1}. \end{align} $$

Note that $X\leq 2^{X-2}$ since $X\geq 4$ . Thus,

(2.13) $$ \begin{align}2k+2\leq 2k+x_1+x_2=X\leq 2^{X-2}.\end{align} $$

Combining (2.12) and (2.13) gives

(2.14) $$ \begin{align} M+2k+2\leq M+2^{X-2}&< (1+2^{X-2})\cdot 4^{X^2-1}+2^{X-2}\nonumber\\ & <2^{X-2}\cdot 4^{X^2-1}+2^{X-2}\cdot 4^{X^2-1}=2^{2X^2+X-3}.\end{align} $$

It follows from (2.11) and (2.14) that $x_n<2^{2X^2+X-3}$ for all $n\geq 1$ . This completes the proof of Theorem 1.2.