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? 
 A: Hint: Prove by induction on $k$ that $(1+\sqrt2)^k = a+b\sqrt2$ for some integers $a$ and $b$ such that $(1-\sqrt2)^k = a-b\sqrt2$.
Then set $k=2n$.
You can choose either $k=0$ or $k=1$ to be the base case.

Alternatively: Use the binomial theorem on each of $(1+\sqrt2)^{2n}$ and $(1-\sqrt2)^{2n}$. Note that the terms that involve an odd power of $\sqrt2$ cancel out each other between the two sums, and that terms with an even power of $\sqrt2$ are (a) integers and (b) are the same in each of the two sums.
A: Base case: $P(0)$
$$ (1 + \sqrt{2})^0 + (1 - \sqrt{2})^0 = 1 + 1 = 2 $$
which is even since $2 = 2\cdot 1$ and of course $1 \in \mathbb{Z}$.
Inductive step: Assume true for $P(k)$, i.e.
$$ (1 + \sqrt{2})^{2k} + (1 - \sqrt{2})^{2k} $$
is true. Show that $P(k+1)$ is true.
A: For the basic step, yes, you can plug $n=0$ (and also $n=1$, if you want) and do some computations.
On the other hand, for the inductive step you can always use the following equality:
$$x^{2n} + y^{2n} = (x^2+y^2)\cdot (x^{2(n-1)} + y^{2(n-1)}) - x^2y^2\cdot (x^{2(n-2)} + y^{2(n-2)})$$
and use complete induction (after you have observed that $(1+\sqrt{2})^2(1-\sqrt{2})^2 =1$).
A: 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$.
