The number $(3+\sqrt{5})^n+(3-\sqrt{5})^n$ is an integer Prove by induction that this number is an integer:
$$u_n=(3+\sqrt{5})^n+(3-\sqrt{5})^n$$
Progress
I assumed that it holds for $n$ and I tried to do it for $n+1$ but the algebra gets quite messy and I'm unable to prove that the following term is an integer: $\sqrt{5}((3+\sqrt{5})^n-(3-\sqrt{5})^n)$
 A: Let $v_n = (3+\sqrt{5})^n - (3-\sqrt{5})^n$, then
$$
u_1 = 6, v_1 = 2\sqrt{5}
$$
And
$$
u_{n+1} = (3+\sqrt{5})(3+\sqrt{5})^n + (3-\sqrt{5})(3-\sqrt{5})^n = 6u_n + \sqrt{5}v_n
$$
$$
v_{n+1} = (3+\sqrt{5})(3+\sqrt{5})^n - (3-\sqrt{5})(3-\sqrt{5})^n = 6v_n +\sqrt{5}u_n
$$
If $v_n$ is an integer multiple of $\sqrt{5}$ and $u_n$ is an integer, then $v_{n+1}$ is an integer multiple of $\sqrt{5}$ and $u_{n+1}$ is an integer.
A: If $n$ is odd then for all reals 
$x, y$
we have
$$(x+y)^{n} + (x-y)^{n} = 2x^n + 2\sum_{j\ \text{odd}}\binom{n}{j}x^{j}y^{n-j};$$
if $n$ is even then for all reals $x, y$ we have
$$(x+y)^{n} + (x-y)^{n} = 2x^n + 2y^n + 2\sum_{j\ \text{even}}\binom{n}{j}x^{j}y^{n-j}.$$
Putting
$x := 3$ and $y := \sqrt{5}$
finishes the proof,
for the irrational terms are all cancelled out.
A: Hint $\, $ By induction $\,\alpha^n,\,\overline\alpha^{\,n} = \overbrace{j \pm k\sqrt{5}}^{\large j,k\ \in\ \Bbb Z}\,$ are $\,\color{#c00}{\overbrace{\rm conjugate}^{\textstyle {\overline{\alpha^n}}=\,\color{#c00}{{\overline\alpha}^n}}}\:$  (so their sum $= 2j\in\Bbb Z,\ \bf\small QED)$
with easy inductive step:  $\,\ \overline{\alpha^{n+1}} =\, \color{#0a0}{\overline{\alpha\,\alpha^n} 
=\,\overline\alpha}\,\color{#c00}{\overline{\alpha^n}}\,\overset{\color{#c00}{\rm induct}}=\overline\alpha\,\color{#c00}{{\overline\alpha}^n} = {\overline\alpha}^{\,n+1}\ $ by $\ \color{#0a0}{\overline{xy}\, =\, \overline x\, \overline y}$
Remark $\ $ Hence we see that the proof is a special case of the $n$-ary inductive extension of the $\color{#0a0}{\text{multiplicativity}}$ of conjugation: $\,\ \overline{\alpha_1\cdots \alpha_n}\, =\, \overline\alpha_1\cdots \overline\alpha_n,\,$ in our special power case: $\,\alpha_i = \alpha.\,$  The same proof works for any quadratic integer $\,\alpha.\,$ As always: exploit innate symmetry!
See this answer for an extension to computing the parity of such power sums.
A: Outline: For the (strong) induction step, we can use the fact that
$$(3+\sqrt{5})^{n+1}+(3-\sqrt{5})^{n+1}=\left[(3+\sqrt{5})^{n}+(3-\sqrt{5})^{n}\right]\left[(3+\sqrt{5})+(3-\sqrt{5})\right]-(3+\sqrt{5})(3-\sqrt{5})\left[(3+\sqrt{5})^{n-1}+(3-\sqrt{5})^{n-1}\right].$$
Note that $(3+\sqrt{5})+(3-\sqrt{5})$ and $(3+\sqrt{5})(3-\sqrt{5})$ are integers.
Remark: There are better "non-induction" ways. For example, imagine expanding each of $(3+\sqrt{5})^n$ and $(3-\sqrt{5})^n$, using the Binomial Theorem. Now add.  The terms in odd powers of $\sqrt{5}$ cancel. 
A: From the theory of sequences defined by a linear recurrence relation with constant coefficients, the sequence $u_n$ satisfies $u_{n+2}=6u_{n+1}-4u_n$ and $u_0=2$ and $u_1=6$.
Then, if you assume that $u_n$ and $u_{n+1}$ are integers, it follows immediately that $u_{n+2}$ is also an integer. You can write a strong induction from this to have a complete proof.
A: See here -- the solutions of $a_n=Aa_{n-1}+Ba_{n-2}$ are given by $a_n=C\lambda_1^n+D\lambda_2^n$ if $\lambda_1\neq \lambda_2$, where $C,D$ are constants created by $a_0,a_1$, and $\lambda_1, \lambda_2$ are the solutions of $\lambda^2-A\lambda-B=0$ (the characteristic polynomial), and $a_n=C\lambda^n+Dn\lambda^n$ if $\lambda_1=\lambda_2=\lambda$.
$u_n=(3+\sqrt{5})^n+(3-\sqrt{5})^n$.
In this case, you want $\lambda_1=3+\sqrt{5}$, $\lambda_2=3-\sqrt{5}$, $C,D$ created by $u_0=2$, $u_1=6$.
Apply Vieta's formulas.
$\lambda_1+\lambda_2=6=A$, $\lambda_1\lambda_2=4=-B$.
The characteristic polynomial is $\lambda^2-6\lambda+4=0$.
The recurrence relation is $u_{n+1}=6u_n-4u_{n-1}$ with $u_0=2$, $u_1=6$.
$u_n$ is an integer because $u_0$, $u_1$ are integers and the recurrence relation shows that $u_2=6u_1-4u_0\in\mathbb Z$, etc. You could use induction here.
(I.e., if $u_k$, $u_{k+1}$ are integers for some $k\in\mathbb Z$, $k\ge 0$, then $u_{k+2}=6u_{k+1}-4u_k$ is also an integer).
Furthermore, $u_n$ is the next integer greater than $(3+\sqrt{5})^n$ because
$3-\sqrt{5}=$
$=\sqrt{3^2}-\sqrt{2^2+1}\in(0,1)$
because more generally for $m\in\mathbb Z$, $m\ge 1$,
$\sqrt{(m+1)^2}=1+\sqrt{m^2}$
$<1+\sqrt{m^2+1}$.
Similar facts are applicable for Pell's equations. See, e.g., this answer.
In this case, you want $x_1=3$, $y_1=1$, $D=5$,
but $3^2-5\cdot 1^2\neq 1$, so a Pell equation isn't easily possible for this sequence, unlike in this one.
