Is $\frac{\left(1+\sqrt{4n^2+1}\right)^n+\left(1-\sqrt{4n^2+1}\right)^n}{2^n}$ always an integer?

Let $$a_n = \frac{\left(1+\sqrt{4n^2+1}\right)^n+\left(1-\sqrt{4n^2+1}\right)^n}{2^n}=2^{1-n} \sum _{k=0}^{\lfloor n/2\rfloor} \binom{n}{2 k} \left(4 n^2+1\right)^k,$$ then we have $$a_1=1,\quad a_2=9,\quad a_3=28,\quad a_4=577,\quad a_5=3251,\quad a_6=105193,\quad...$$ How can we prove that $$a_n$$ is an integer for all positive integer $$n$$?

• This looks like a solution to a recurrence relation. Can you construct such a relation? Oct 17, 2018 at 0:05
• Show that $\dfrac{1\pm\sqrt{4n^2+1}}{2}$ is an algebraic integer, so $a_n\in\mathcal{O}_{\bar{\mathbb{Q}}}\cap\mathbb{Q}=\mathbb{Z}$. Oct 17, 2018 at 0:11
• Oct 17, 2018 at 1:44

I'll give two approaches: In either case, let $$b_{m,n}=\left(\dfrac{1+\sqrt{4m+1}}{2}\right)^n+\left(\dfrac{1-\sqrt{4m+1}}{2}\right)^n$$ thus $$a_n=b_{n^2,n}$$. We will prove $$b_{m,n}\in\mathbb{Z}$$ for all $$m,n\in\mathbb{Z}$$, $$n\geqslant 0$$. In particular, we get $$a_n\in\mathbb{Z}$$.

Approach 1: Show that $$a_n$$ is a rational algebraic integer

The numbers $$\dfrac{1\pm\sqrt{4m+1}}{2}$$ are roots of $$x^2-x-m$$, so are algebraic integers. Hence $$b_{m,n}$$ is an algebraic integer. On the other hand, you know $$b_{m,n}$$ is rational by binomial expansion. So $$b_{m,n}\in\mathbb{Z}$$ as $$\mathbb{Z}$$ is integrally closed.

Approach 2: recurrence relation

We have $$b_{m,n}$$ satisfies a recurrence relation $$b_{m,n+2}=b_{m,n+1}+mb_{m,n}$$ with $$b_{m,0}=2$$ and $$b_{m,1}=1$$. So inductively $$b_{m,n}\in\mathbb{Z}$$ for all $$m,n\in\mathbb{Z}$$, $$n\geqslant 0$$.

Fix some integer $$n$$ and consider the Galois conjugated algebraic integers $$s,t$$ equal to $$\frac 12\Big(\ 1\pm\sqrt{4n^2+1}\ \Big)$$ in the appropiate quadratic field over $$\Bbb Q$$.

They are algebraic integers, because we have $$s+t=1$$, $$st=\frac 14(1-(1+4n^2))\in\Bbb Z$$.

Fix some natural power $$k$$. Then the number $$s^k+t^k$$ is also an algebraic integer, it is fixed by the Galois conjugation exchanging $$s\leftrightarrow t$$, so it lives in $$\Bbb Q$$.

So it is an integer.

Now consider the special case $$k=n$$.