Finding every $n$ such that $a_n$ is an integer

Let us define $\{a_n\}$ as $a_1=a_2=1$,$$a_{n+2}=a_{n+1}+\frac{a_n}{2}\ \ (n=1,2,\cdots).$$ Then, is the following conjecture true?

A conjecture : If $a_n$ is an integer, then $n\le 8$.

I conjectured this by using computer, but I don't have any good idea to prove it. Can anyone help?

Let us write $a_n = \frac{p_n}{q_n}$, where $\gcd(p_n,q_n)=1$. Then we have from the recurrence relation that $$\frac{p_{n+2}}{q_{n+2}} = \frac{2q_n p_{n+1} + p_n q_{n+1}}{2q_nq_{n+1}}$$ with $p_1=q_1=p_2=q_2=1$. In particular we see that for each $n$ we can write $q_n = 2^{j_n}$ for some $j_n \ge 0$.

From numerical evidence we guess the following formulas for $j_n$:

• $j_{2k+1} = k$, where $k \ge 0$
• $j_{2(2k+1)} = 2k$, where $k \ge 0$
• $j_4 = 0$
• $j_{2^u(2k+1)} = 2^{u-1} (2k + 1) - u - 1$, where $u \ge 2$, $k \ge 0$, $2^u(2k+1) \neq 4$

Notice that $j_n = 0$ only for $n=1,2,4,8$. These are the only values for which $a_n$ is an integer.

To prove all this, we define the sequence $p_n$ by the recurrence relation $$p_n = 2^{j_n - j_{n-1}} p_{n-1} + 2^{j_n - j_{n-2} - 1} p_{n-2}, p_1 = p_2 = 1.$$ We have to show that $p_n$ is an odd integer for all $n \neq 4$ ($p_4 = 2$). This can be done by induction.

Here are sketches for the induction steps:

Case 1a: $n-1$ is of the form $2(2k+1)$

In this case we have $p_n = 2 p_{n-1} + p_{n-2}$, we are done by induction.

Case 1b: $n-1$ is of the form $2^u(2k+1)$

In this case we have $p_n = 2^{u+1} p_{n-1} + p_{n-2}$, we are done by induction.

Case 2a: $n$ is of the form $2(2k+1)$

In this case we have $p_n = p_{n-1} + 2^u p_{n-2}$, we are done by induction.

Case 2b: $n$ is of the form $2^u(2k+1)$

In this case we have $p_n = \frac{p_{n-1} + p_{n-2}}{2^u}$. We have to show that the largest power of $2$ that divides $p_{n-1} + p_{n-2}$ is $2^u$.

To do this consider the sequence $r_n = p_{4n-1} + p_{4n-2}$. By using the defining relation of $p_n$, one can show that $r_n$ satisfies the recurrence relation $r_n = 14 r_{n-1} - r_{n-2}$ with $r_1 = 4$, $r_2 = 56$. Once we have shown that $r_{2^u(2k+1)}$ is divisible by $2^{u+2}$, we are done.

We can as well consider the sequence $s_n = r_n/4$, defined by the same recurrence relation with initial values $s_1 = 1$, $s_2 = 14$. This is A007655 in OEIS. We have the generating function $$S(x) = \frac{x}{1 - 14x + x^2}.$$ To extract the coefficients of $x^{2^u(2k+1)}$, where $u$ is fixed, we define the sequence of generating functions $$S_n(x) = \frac{S_{n-1}(\sqrt{x}) + S_{n-1}(-\sqrt{x})}{2}, \quad S_1(x) = S(x).$$ By induction we see that $$S_n(x) = \frac{A(1) \dots A(n-1) x}{1 - A(n) x + x^2}$$ where $A(1) = 14$, $A(n+1) = A(n)^2 - 2$. Indeed, $$\begin{eqnarray*} S_n(x) & = & \frac{\frac{A(1) \dots A(n-2) \sqrt{x}}{1 - A(n-1) \sqrt{x} + x} - \frac{A(1) \dots A(n-2) \sqrt{x}}{1 + A(n-1) \sqrt{x} + x}}{2} \\ & = & \frac{A(1) \dots A(n-2) A(n-1) x}{(1 + x)^2 - A(n-1)^2 x} \\ & = & \frac{A(1) \dots A(n-1) x}{1 - (A(n-1)^2 - 2) x + x^2}. \end{eqnarray*}$$ Now $R_u(x) = \frac{S_{u+1}(\sqrt{x}) - S_{u+1}(-\sqrt{x})}{2\sqrt{x}}$ corresponds to the generating function of the terms $r_{2^u(2k + 1)}$, where $u$ is fixed. We have $$\begin{eqnarray*} \frac{S_u(\sqrt{x}) - S_u(-\sqrt{x})}{2\sqrt{x}} & = & \frac{\frac{A(1) \dots A(u-1) \sqrt{x}}{1 - A(u-1) \sqrt{x} + x} + \frac{A(1) \dots A(u-1) \sqrt{x}}{1 + A(u-1) \sqrt{x} + x}}{2\sqrt{x}} \\ & = & \frac{A(1) \dots A(u-1) \sqrt{x}(1 + x)}{\sqrt{x}(1 - A(u) x + x^2)} \\ & = & \frac{A(1) \dots A(u-1) (1 + x)}{1 - A(u) x + x^2}. \end{eqnarray*}$$ Clearly by definition each $A(k)$ is divisible by $2$ but not by $4$. Therefore the product $A(1) \dots A(u-1) A(u)$ in front of $R(u)$ has exactly $u$ factors of $2$. Because $A(u)$ is even, the coefficients of the taylor series of $\frac{1}{1 - A(u) x + x^2}$ alternate between even and odd. Therefore $\frac{1+x}{1 - A(u) x + x^2}$ has odd coefficients. This proves the claim.

I thought I'd write up some observations that I think are essentially a proof, but it could stand to be vetted and better presented. I'll try to come back and do this myself, but I'd be happy if someone else sees a nice way to clean things up and does so in a separate answer. (If you do, please tack on comment on to this answer, so I can put an edit here redirecting readers.)

Starting with the OEIS sequence $1,2,3,8,11,30,41,112,\ldots$ in lhf's answer, which lhf noted consists of alternating odd and even terms, extract the even terms to get the OEIS sequence

$$0, 2, 8, 30, 112, 418, 1560, 5822, 21728, 81090, 302632, 1129438, 4215120, 15731042,\ldots$$

which satisfies the two-term recursion $a(n+1)=4a(n)-a(n-1)$. (Note the addition of $0$ at the beginning. This turns out to be fairly important.) If we factor out a $2$, this again alternates between even and odd:

$$0, 1, 4, 15, 56, 209, 780, 2911, 10864, 40545, 151316, 564719, 2107560, 7865521,\ldots$$

so tossing aside the odd terms gives

$$0,4,56,780,10864,151316,2107560,\ldots$$

Now it's easy to show that anytime you pick out every other term of a sequence with a two-term recursion, the new sequence still satisfies a two-term recursion: If $a(n+1)=\alpha a(n)+\beta a(n-1)$, then $a(2n+2)=(\alpha^2+2\beta)a(2n)-\beta^2a(2n-2)$. Since our $\beta$ is $-1$, this new sequence satisfies the recursion $a(n+1)=14a(n)-a(n-1)$, where $14=4^2-2$. This time we can factor a $4$ out of the sequence, leaving

$$0,1,14,195,2716,37829,526890,\ldots$$

which again alternates odd and even terms, for the simple reason that the $\alpha$ and $\beta$ for its two-term recursion are also even and odd, just as $4$ and $-1$ were in the sequence it came from. So we repeat:

$$0,14,2716,526890,\ldots$$

Factoring out the $14$ makes this

$$0,1,194,37635,\ldots$$

which satisfies the two-term recursion $a(n+1)=194a(n)-a(n-1)$, where $194=14^2-2=(4^2-2)^2-2$. It's becoming clear what's happening: At the $m$th step, we wind up with a sequence of the form

$$0,1,r_m,r_m^2-1,r_m^3-2r_m,\ldots$$

which satisfies the recursion $a(n+1)=r_ma(n)-a(n-1)$, with $r_m=r_{m-1}^2-2$. In particular, the sequence of $r_m$'s is $4,14,194,\ldots$, so that after the first $4$, all the terms are $2$ times an odd number. So when you pass to the next batch of even terms,

$$0,r_m,r_m^3-2r_m,\ldots$$

and then factor out the $r_m$ to get the next sequence $0,1,r_{m+1},r_{m+1}^2-1,\ldots$, you are taking out only one power of $2$. If you think carefully about what all this means, I think it explains the serrations in lhf's graph and shows that you wind up with large powers of $2$ in the denominator of the OP's original sequence after the eighth term, as conjectured.

Partial answer. Work in progress.

Let $b_n= 2^{\lfloor n/2 \rfloor} a_n$. This sequence is well known: oeis.org/A048788: $$ 1, 2, 3, 8, 11, 30, 41, 112, 153, 418, 571, 1560, 2131, 5822, \dots $$

It satisfies $$ b_{2n} = 2b_{2n-1} + b_{2n-2} $$ $$ b_{2n+1} = b_{2n} + b_{2n-1} $$

It is clear from these equations and the initial conditions that $b_n \bmod 2$ is $1,0,1,0,1,\dots$. In particular, $b_n$ is odd for $n$ odd. This implies that $a_n$ is not an integer for $n$ odd.

My original strategy, which lead to the approach above, is to consider the number of decimal places required to represent $a_n$. Empirically, it follows $n/2$, as the argument above shows, but for some $n$. notably powers of $2$, the number of decimal places goes down noticeably. See the picture below. The approach above shows that $n/2$ suffice but I need a lower bound, not an upper bound.