Finding $(a+\sqrt b)^n+(a-\sqrt b)^n$ where $n$ is natural For the expression $\left(a+\sqrt{b}\right)^n+\left(a-\sqrt{b}\right)^n$ where $n \in \mathbb{N}$, and $a,b, \in \mathbb{Q}$, the radical is always ends up cancelled, and the result is always in $\mathbb{Q}$.  Is there any way that this could be reexpressed with the assumption that n is always a positive integer without the use of a square root operation, such as an alternative closed form for even $n$, and another closed form for odd $n$, or am I always stuck having to calculate a square root?
 A: Note: $(x + y)^n = x^n + {n \choose 1} x^{n-1}y + \dotsc + y^n$
While $(x - y)^n = x^n - {n \choose 1} x^{n-1}y + \dotsc \pm y^n$ 
The even terms are opposite parity while the odd terms are the same so
$(x + y)^n + (x - y)^n = 2x^n + 2{n \choose 2}x^{n-2}y^2 + \dotsc$
So $(a + \sqrt{b})^n + (a - \sqrt{b})^n = 2(a^{n} + {n \choose 2}a^{n -2}\sqrt{b}^{2} + \dotsc)$
So we are only taking $\sqrt{b} $ to even powers, and $\sqrt{b}^{2k} = b^k$.
So $\displaystyle(a + \sqrt{b})^n + (a - \sqrt{b})^n = 2 \sum_{i = 0; \,i \text{ even}}^n {n  \choose i}a^{n - i}b^{i/2}$.
...
Or if you don't like taking a sum with only even summands:
$\displaystyle(a + \sqrt{b})^n + (a - \sqrt{b})^n = 2\sum_{k = 0}^{\lfloor n/2 \rfloor} {n  \choose 2k}a^{n - 2k}b^{k}$
A: Define the sequence starting with $u_0=2$ and $u_1=2a$, and for $n\ge2$,
$$
u_n=2au_{n-1}-(a^2-b)u_{n-2}\tag{1}
$$
Solving the Linear Recurrence in $(1)$, we get the solution
$$
u_n=\left(a+\sqrt{b}\right)^n+\left(a-\sqrt{b}\right)^n\tag{2}
$$
since
$$
(x-a-\sqrt{b})(x-a+\sqrt{b})=x^2-2ax+a^2-b\tag{3}
$$
A: Since 
$$\begin{bmatrix}
A & B \\
1 & A
\end{bmatrix} = \begin{bmatrix}
1 & 1 \\
\frac{-1}{\sqrt B} & \frac{1}{\sqrt B}
\end{bmatrix} \begin{bmatrix}
A - \sqrt B & 0 \\
0 & A + \sqrt B
\end{bmatrix} \begin{bmatrix}
1 & 1 \\
\frac{-1}{\sqrt B} & \frac{1}{\sqrt B}
\end{bmatrix}^{-1}
$$
It follows that
$$\begin{bmatrix}
A & B \\
1 & A
\end{bmatrix}^n = \begin{bmatrix}
1 & 1 \\
\frac{-1}{\sqrt B} & \frac{1}{\sqrt B}
\end{bmatrix} \begin{bmatrix}
A - \sqrt B & 0 \\
0 & A + \sqrt B
\end{bmatrix}^n \begin{bmatrix}
1 & 1 \\
\frac{-1}{\sqrt B} & \frac{1}{\sqrt B}
\end{bmatrix}^{-1}
$$
$$Q = \begin{bmatrix}
1 & 1 \\
\frac{-1}{\sqrt B} & \frac{1}{\sqrt B}
\end{bmatrix}^{-1} \begin{bmatrix}
A & B \\
1 & A
\end{bmatrix}^n \begin{bmatrix}
1 & 1 \\
\frac{-1}{\sqrt B} & \frac{1}{\sqrt B}
\end{bmatrix} = \begin{bmatrix}
(A - \sqrt B)^n & 0 \\
0 & (A + \sqrt B)^n
\end{bmatrix}
$$
If you assume that $\begin{bmatrix}
A & B \\
1 & A
\end{bmatrix}^n = \begin{bmatrix} H & I \\ J & K \end{bmatrix}$ then multiply out the above it follows that $(A - \sqrt B)^n + (A + \sqrt B)^n = Q_{1,1} + Q_{2,2} = H + K$.
In summary, $$(A - \sqrt B)^n + (A + \sqrt B)^n = \text{trace}\left(\begin{bmatrix}
A & B \\
1 & A
\end{bmatrix}^n\right)$$
