# Arithmetic of integers (based on mathematical induction)

If $$f(n) = (3+\sqrt{5})^n + (3-\sqrt{5})^n$$ show that $$f(n)$$ is an integer and that $$f(n+1)= 6f(n) - 4f(n-1).$$ Deduce that the next integer greater than $$(3+\sqrt{5})^n$$ is divisible by $$2^n.$$ I am not getting a way to approach such a question. So, please help me regarding that...

• Have you tried it for small $n$? This screams for an induction proof. The point is that the $\sqrt 5$'s cancel out. I recommend Aurturo Magidin's answer to this question for a good intro – Ross Millikan Apr 20 at 2:00
• Please use MathJax to format your posts. You'll get a lot more help if your questions are easy to read. – saulspatz Apr 20 at 3:15
• It is a lot easier to see that $f(n)$ is an integer once you have established the given formula for $f(n+1)$ :)z – Erick Wong Apr 20 at 5:18

Proof for showing $$f(n) = (3+\sqrt{5})^n + (3-\sqrt{5})^n$$ is an integer :
$$(3+\sqrt{5})^n = C_0 + C_1 \cdot 3^{n - 1} \cdot 5 ^{1/2} + C_2 \cdot 3^{n - 2} \cdot 5^{2/2} + \dots + C_n \cdot 5^{n/2}$$
$$(3-\sqrt{5})^n = C_0 - C_1 \cdot 3^{n - 1} \cdot 5 ^{1/2} + C_2 \cdot 3^{n - 2} \cdot 5^{2/2} + \dots + (-1)^r \cdot 3^{n - r} \cdot 5^{r/2} + \dots + (-1)^n \cdot 5^{n/2}$$
Adding these two equations we notice that for $$n$$ that is odd the respective terms cancel out in the above equations. So only the terms for which $$n$$ is even are present in $$(3+\sqrt{5})^n + (3-\sqrt{5})^n$$ and thus $$f(n)$$ is an integer.