The number $(3+\sqrt{5})^n+(3-\sqrt{5})^n$ is an integer

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.

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.

Hint $\, $ By induction $\,\alpha^n,\,\overline\alpha^{\,n} = j \pm k\sqrt{5}\,$ are $\,\color{#c00}{\rm conjugate}\,$ (so their sum $= 2j\in\Bbb Z)$

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, i.e $\ \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: exloit innate symmetry!

See this answer for an extension to computing the parity of such power sums.