Prove by induction that for every $n \in \mathbb{N}$, $(1 + \sqrt{3})^n + (1 - \sqrt{3})^n \in \mathbb{Z}$.

Question

Prove by induction that for every $n \in \mathbb{N}$, $(1 + \sqrt{3})^n + (1 - \sqrt{3})^n \in \mathbb{Z}$.

Answer 1

Hint: Use the binomial theorem.

Answer 2

HINT: If you know the binomial theorem, you can prove this very easily without induction. If you must prove it by induction, you may find it easier to prove a stronger statement:

Let $\alpha=1+\sqrt3$ and $\beta=1-\sqrt3$. Then for each $n\in\Bbb N$ both $\alpha^n+\beta^n$ and $\sqrt3(\alpha^n-\beta^n)$ are integers.

The following calculation will be useful for the induction step:

$$\begin{align*} \alpha^{n+1}+\beta^{n+1}&=\alpha^n+\sqrt3\alpha^n+\beta^n-\sqrt3\beta^n\\ &=(\alpha^n+\beta^n)+\sqrt3(\alpha^n-\beta^n)\\ \end{align*}$$

You will want a similar one involving $\alpha^{n+1}-\beta^{n+1}$.

(This is an example of a not uncommon phenomenon: sometimes an induction argument requires a stronger hypothesis than the obvious one and works only after you realize that you can prove a stronger statement.)

Answer 3

Let $a_n$ be your expression. Show that $a_n$ satisfies a linear recurrence of the form $a_{n+2} = A a_{n+1} +B a_n$ and that $a_0,a_1$ are integers. Then prove your claim by induction.

Answer 4

A start: For convenience let our numbers be $a$ and $b$. For the induction step, use the identity $$a^{k+1}+b^{k+1}=(a^k+b^k)(a+b)-ab(a^{k-1}+b^{k-1}).$$ Technically speaking, you will be using strong induction.

Answer 5

$$ A^{n+1} + B^{n+1} = (A+B)(A^n + B^n)-AB(A^{n-1} + B^{n-1}) $$