Let $n \geqslant 0$ be an integer. Show that $2^n | \lceil (3+\sqrt5)^n \rceil.$

Question

Let $n \geqslant 0$ be an integer. Show that $2^n | \lceil (3+\sqrt5)^n \rceil.$

This turned out to be relatively hard. The idea that our lecturer gave was that one should work towards an linear recurrence relation here, but it doesn’t seem to be an trivial task.

Using the binomial theorem on $(3+\sqrt5)^n$ was my first approach to see if there would be any cancellations, but that turned out to be also very messy. What would be the way to approach this?

Answer 1

Let $a_n=(3+\sqrt5)^n+(3-\sqrt5)^n$.

Then can you show $a_0=2$, $a_1=6$, and $a_{n+2}=6a_{n+1}-4a_{n}$?

[$3+\sqrt5$ and $3-\sqrt5$ are roots of $x^2-6x+4=0$.]

It follows that $2^n|(3+\sqrt5)^n+(3-\sqrt5)^n$.

Since $(3+\sqrt5)^n$ is not an integer and $(3-\sqrt5)^n<1$,

it follows that $(3+\sqrt5)^n+(3-\sqrt5)^n=\lceil(3+\sqrt5)^n\rceil$.

Answer 2

As hinted in comment, first solve the following recurrent relation:

$$ F_n = 3F_{n-1} - F_{n-2}, F_0 = 1, F_1 = 3 $$

If you can solve the recurrence, you will know the closed form of the above recurrent relation is $F_n = (\frac{3+\sqrt{5}}{2})^n + (\frac{3-\sqrt{5}}{2})^n \Rightarrow 2^n F_n = (3+\sqrt{5})^n + (3-\sqrt{5})^n$.

Now get a ceil from each side of the equation:

$\lceil 2^n F_n\rceil = \lceil (3+\sqrt{5})^n + (3-\sqrt{5})^n\rceil$

As $(3+\sqrt{5})^n + (3-\sqrt{5})^n$ is integer, we can find that $\lceil (3+\sqrt{5})^n + (3-\sqrt{5})^n\rceil = \lceil (3+\sqrt{5})^n \rceil$. Now, we will find:

$$ 2^n F_n = \lceil (3+\sqrt{5})^n \rceil. $$

Because $F_n$ is integer. Therefore $2^n | \lceil (3+\sqrt{5})^n \rceil$.