<s>[INST] if $S_n = (3 + \sqrt{5})^n + (3 - \sqrt {5})^n$ then show that $S_n$ is an integer by induction this is all that i have tried:
let $n=1$ so equation gives $(3 + \sqrt {5}) + (3 - \sqrt {5}) = 6$ which is an integer
so it is true for $n=1$
now let it be true for $k \ge n$ then we have:
$(3 + \sqrt {5})^k + (3 - \sqrt {5})^k$ is an integer
for k+1: $(3 + \sqrt {5})^k(3 + \sqrt {5}) + (3 - \sqrt {5})^k(3 - \sqrt {5})$
$= 3((3 + \sqrt {5})^k + (3 - \sqrt {5})^k) + \sqrt {5}((3 + \sqrt {5})^k - (3 - \sqrt {5})^k)$
$= (integer) + \sqrt {5}((3 + \sqrt {5})^k - (3 - \sqrt {5})^k)$
from here I started facing a problem.
I wasn't able to prove $\sqrt {5}((3 + \sqrt {5})^k - (3 - \sqrt {5})^k)$ an integer.
can someone please help me out?

(ONLY USING INDUCTION!)

 [/INST] Use the fact that $$a^{n+1} + b^{n+1} = (a+b)(a^n + b^n) - ab(a^{n-1} + b^{n-1}),$$ so that if $a = 3 + \sqrt{5}$, $b = 3 - \sqrt{5}$, then $ab = 3^2 - 5 = 4$, hence $$S_{n+1} = 6S_n - 4S_{n-1}.$$  Consequently your induction base case should cover two consecutive values of $n$, and your induction step relies on the fact that the previous two values of $S$ are integers.
</s>