Prove $(2+\sqrt{13})^n + (2-\sqrt{13})^n$ is natural number without using binomial theorem

Question

Question is as stated in the title.

I attempted to prove this by induction on $n$. Base case is just $2$, so it obviously holds. Assuming it holds for $n=k$, then the case for $n=k+1$ can be converted into something like $2((2+\sqrt{13})^k + (2-\sqrt{13})^k) + \sqrt{13}(2+\sqrt{13})^k - \sqrt{13}(2-\sqrt{13})^k$. The first part is a natural number by our inductive hypothesis, but I'm not sure what to do with the second part: $\sqrt{13}(2+\sqrt{13})^k - \sqrt{13}(2-\sqrt{13})^k$. I can factor out another natural number from this part, and convert it into: $\sqrt{13}((2+\sqrt{13})^k + (2-\sqrt{13})^k) - 2\sqrt{13}(2-\sqrt{13})^k$, but I'm not sure how I can proceed from there.

I'm not sure what tags to put, but I encountered this problem in a combinatorics course, so I added a tag for that. Also since it's about natural numbers, I think maybe there can be some insights from number theory, although it's not a typical number theory problem.

Answer 1

HINT: Let us write for each natural number $k$:

$$c_k = (2+\sqrt{13})^k,$$ and $$d_k = (2-\sqrt{13})^k, $$ and $$e_k = c_k +d_k.$$

Then $c_{n+2}$ satisfies $$c_{n+2} = (4+4\sqrt{13}+4+9)c_n$$ $$=((8+4\sqrt{13}) + 9)c_n$$ $$= 4c_{n+1}+9c_n.$$ Likewise, $d_{n+2}$ satisfies $$d_{n+2} = (4-4\sqrt{13}+4+9)d_n$$ $$=4d_{n+1}+9d_n.$$

Thus $e_{n+2} =c_{n+2}+d_{n+2}$ satisfies $$e_{n+2} = 4e_{n+1}+9e_n.$$

So if $e_n$ is integral and $e_{n+1}$ is integral, then so is $e_{n+2}$. But what were $e_1$ and $e_2$ again...

Answer 2

One good thing to know (and to verify) is that conjugation, i.e., the function that takes an element $x = m + n\sqrt{13}$ to its conjugate $\overline{x} = m - n\sqrt{13}$, preserves multiplication: $\overline{xy} = \overline{x} \cdot \overline{y}$.

Once you have this, then you can prove by induction that the conjugate of $(2 + \sqrt{13})^n$ is $(2 - \sqrt{13})^n$.

Finally, what can you say about an element plus its conjugate?