<s>[INST] Prove that $(1 + \sqrt2)^{2n} + (1 - \sqrt{2})^{2n}$ is an even integer. Prove that $(1+\sqrt2)^{2n} + (1-\sqrt2)^{2n}$ is an even integer. 
I'm not sure how to prove that it is an even integer. What would I do for the Inductive Step? And for the basic step, can I plug in zero and prove something from that? 
 [/INST] Note that
$(1+\sqrt2)(1-\sqrt2)
=-1
$
and
$(1+\sqrt2)^2
=3+2\sqrt{2}
$.
Therefore,
if $a
=3+2\sqrt{2}
$,
then
$1/a = 3-2\sqrt{2}
$,
so that
$a+1/a
=6
$
and
$(1+\sqrt2)^{2n} + (1-\sqrt2)^{2n}
=a^n+1/a^n
$.
We now use the identity
true for any $a$
that
$a^{n+1}+1/a^{n+1}
=(a+1/a)(a^n+1/a^n)-(a^{n-1}+a^{n-1})
$.
Therefore,
for this particular $a$,
$a^{n+1}+1/a^{n+1}
=6(a^n+1/a^n)-(a^{n-1}+a^{n-1})
$.
Since
$a^n+1/a^n$
is an integer
for $n=0$
and
$n=1$,
it is an integer
for all $n$.
Explicitly,
if
$u_n = a^n+1/a^n
=(1+\sqrt2)^{2n} + (1-\sqrt2)^{2n}
$,
$u_{n+1}
=6u_n-u_{n-1}
$
with
$u_0 = 1$
and
$u_1 = 6$.
</s>