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$?
 A: 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$.
A: 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$. 
