<s>[INST] 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)$
 [/INST] 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. 
</s>