<s>[INST] Show that $(\sqrt{3}+1)^{2n}+(\sqrt{3}-1)^{2n}$ and $(\sqrt{3}+1)^{2n+1}+(1-\sqrt{3})^{2n+1}$.........? Show that $(\sqrt{3}+1)^{2n}+(\sqrt{3}-1)^{2n}$ and $(\sqrt{3}+1)^{2n+1}+(1-\sqrt{3})^{2n+1}$ are both divisible by $2^{n+1}$. Is this the highest power of $2$ dividing either of the numbers?
I am not well versed with binomial theorem hence I am not able to proceed. I am also interested in the different ways this problem can be solved.
Any help would be appreciated.
 [/INST] Let $a_n = (1+\sqrt{3})^n + (1 - \sqrt{3})^n$ for $n \ge 0$.
Since $1 \pm \sqrt{3}$ are roots of $(\lambda - 1)^2 - 3 = \lambda^2 - 2\lambda - 2$, $a_n$ satisfies a recurrence relation:
$$a_{n+2} = 2(a_{n+1} + a_n)$$
Define two auxiliary sequences $b_n, c_n$ by
$\begin{cases}
b_n &= 2^{-(n+1)} a_{2n}\\
c_n &= 2^{-(n+1)} a_{2n+1}
\end{cases}$, we have
$$\begin{align}
b_{n} &= 2^{-(n+1)}a_{2n} = 2^{-n}(a_{2n-1} + a_{2n-2}) = c_{n-1} + b_{n-1}\\
c_{n} &= 2^{-(n+1)}a_{2n+1} = 2^{-n}(a_{2n} + a_{2n-1}) = 2b_n + c_{n-1} = 2b_{n-1} + 3c_{n-1}
\end{align}$$
or in matrix form:
$$\begin{bmatrix}b_n \\ c_n\end{bmatrix} = 
\begin{bmatrix} 1 & 1\\ 2 & 3\end{bmatrix} \begin{bmatrix}b_{n-1} \\ c_{n-1}\end{bmatrix}$$
Since $a_0 = a_1 = 2 \implies b_0 = c_0 = 1$, this leads to following representation of $(a_{2n}, a_{2n+1})$:
$$\begin{bmatrix}a_{2n} \\ a_{2n+1}\end{bmatrix}
= 2^{n+1}\begin{bmatrix}b_n \\ c_n\end{bmatrix}
= 2^{n+1}\begin{bmatrix} 1 & 1\\ 2 & 3\end{bmatrix}^n \begin{bmatrix}1 \\ 1\end{bmatrix}$$
From above expression, it is easy to see $(b_n, c_n)$ are integers. This implies $2^{n+1}$ divides both $a_{2n}$ and $a_{2n+1}$.
In fact, since $c_0 = 1$ is odd and
$$c_{n} = 2b_{n-1} + 3c_{n-1} \equiv c_{n-1} \pmod 2$$
all $c_n$ are odd. From this, we can deduce $2^{n+1}$ is the highest factor of $2$ that divides both $a_{2n}$ and $a_{2n+1}$.
</s>