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

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$.