Using induction, show ${(1+\sqrt{2})}^{2n}+{(1-\sqrt{2})}^{2n}$ is an even integer.

Question

I'm having serious difficulties with that task, so it should be nice, if there is someone that can help!

The task says:

Prove that the number $${(1+\sqrt{2})}^{2n}+{(1-\sqrt{2})}^{2n}$$ is an even integer for all $n\in\mathbb{N}$

Answer 1

If $x,y$ exists such that $x+y$ is an even integer and $xy$ is an integer, then $x^n+y^n$ is always a even integer where $n \in \mathbb{N}$. This follows from induction using the fact that $$x^{n+1}+y^{n+1}=(x+y)(x^n+y^n)-xy(x^{n-1}+y^{n-1})$$

To elaborate, you can prove it is true for $1,2$, where $$x^2+y^2=(x+y)^2-2xy \equiv (x+y)^2 \equiv 0 \pmod 2$$ Then show that if we assume that it is true for $n,n+1$, then it follows that it is true for $n+2$.

Answer 2

Binomial expansion: all the $\sqrt{2}$ terms will cancel and you'll be left with only the powers of two, including $2^0=1$ but that's okay since there's two of them!

EDIT: I relented and actually did the working...

\begin{align*} (1+\sqrt{2})^{2n} + (1-\sqrt{2})^{2n} &= \sum_{r=0}^{2n}\ ^{2n}C_r \sqrt{2}^{\ r} +\sum_{r=0}^{2n}(-1)^r\ ^{2n}C_r \sqrt{2}^{\ r}\\ &=\sum_{r=0}^{2n}\ ^{2n}C_r \sqrt{2}^{\ r}+(-1)^r\ ^{2n}C_r \sqrt{2}^{\ r}\\ &=\sum_{r=0}^{n}2\ ^{2n}C_{2r} \sqrt{2}^{2r}\\ &=2\sum_{r=0}^{n}\ ^{2n}C_{2r} 2^r \end{align*}

Which is clearly an even integer!

Answer 3

If $a_n=pr^n+qs^n$, with $r\ne s$, the sequence $a_n$ satisfies the recurrence relation $$ a_0=p+q,\qquad a_1=pr+qs,\qquad a_{n+2}-(r+s)a_{n+1}+rsa_n $$ Indeed, \begin{align} a_{n+2}-(r+s)a_{n+1}+rsa_n &=pr^{n+2}+qs^{n+2}-(r+s)(pr^{n+1}+qs^{n+1})+rs(pr^n+qs^n) \\ &=p(r^{n+2}-r^{n+2}-sr^{n+1}+sr^{n+1}) \\ &\qquad+q(s^{n+2}-rs^{n+1}-s^{n+2}+rs^{n+1})\\ &=0 \end{align} In our case $p=q=1$, $r=(1+\sqrt{2})^2=3+2\sqrt{2}$, $s=(1-\sqrt{2})^2=3-2\sqrt{2}$; thus $r+s=6$ and $rs=1$.

Therefore the recurrence relation is $$ a_0=2,\qquad a_1=6, \qquad a_{n+2}-6a_{n+1}+a_n=0 $$ Since $a_0$ and $a_1$ are even (base of the induction), if we assume $a_k$ even for every $k$ with $0\le k<n+2$, then $$ a_{n+2}=6a_{n+1}-a_n $$ is even too.

---

A similar strategy is considering $b_n=(1+\sqrt{2})^n+(1-\sqrt{2})^n$. The recurrence relation is $$ b_0=2,\qquad b_1=2,\qquad b_{n+2}-2b_{n+1}-b_n=0 $$ We want to see that $b_{2n}$ is even; the statement is true for $n=0$. Suppose $b_{2n}$ is even; then $$ b_{2n+2}=2b_{n+1}+b_n $$ is even as well.

Answer 4

This might seem pulled out of hat if you are not familiar with the concept, but the idea is applicable in other similar cases as well, most notably with complex numbers.

Consider the set $\mathbb Z[\sqrt 2]=\{a+b\sqrt 2\,|\, a,b\in\mathbb Z\}$ and define $\overline{a+b\sqrt 2}=a-b\sqrt 2$. We need couple of facts:

• $\mathbb Z[\sqrt 2]$ is multiplicatively closed, i.e. if $x,y\in\mathbb Z[\sqrt 2]$, then $x\cdot y\in\mathbb Z[\sqrt 2]$. In particular, $x^n\in\mathbb Z[\sqrt 2]$ for all $x\in\mathbb Z[\sqrt 2]$, by induction.

• $(a+b\sqrt 2)+\overline{(a+b\sqrt 2)} = 2a$, i.e. $x+\overline x\in 2\mathbb Z$, for all $x\in\mathbb Z[\sqrt 2]$.

• $\overline{x\cdot y} =\overline x\cdot\overline y$ for any $x,y\in\mathbb Z[\sqrt 2]$. Therefore, $\overline{x}^n=\overline{x^n}$, by induction, for all $x\in\mathbb Z[\sqrt 2]$.

Now, set $x = 1 +\sqrt 2$ and we have $$(1+\sqrt 2)^{2n} + (1-\sqrt 2)^{2n} = x^{2n} + \overline x^{2n} = x^{2n} + \overline {x^{2n}} \in 2\mathbb Z$$

If you've never seen these arguments, it might seem too involved, but actually, you are already familiar with all of this if you know anything about complex numbers. In that case, instead of $\mathbb Z[\sqrt 2]$, we have $\mathbb Z[i] = \{a+bi\,|\, a,b\in\mathbb Z\}$ and $\overline z$ is the familiar complex conjugate, for which we have $\overline{z\cdot w}=\overline z\cdot\overline w$, and $z+\overline z = 2\operatorname{Re} z\in 2\mathbb Z$.

Hopefully, this will be helpful.