# Recurrence relation satisfied by $\lfloor(1+\sqrt{3})^n\rfloor$

This is a follow up to a question I had asked earlier about a linear recurrence relationship satsified by $\lfloor(1+\sqrt{5})^n\rfloor$. I messed up there, and I actually meant to ask about $L(n)=\lfloor(1+\sqrt{3})^n\rfloor$.

Following Douglas' suggestion I have determined that the values (at least the first 1000) satisfy the following recurrence:

$L(2n+5)=8L(2n+3)-4L(2n+1)$

The question is how do I prove something like this. I can prove the recurrence for the values inside the floor function, but floor function in general does not commute with addition and multiplication.

Explicitly, it's easy to show

$(1+\sqrt{3})^{2n+5}=8(1+\sqrt{3})^{2n+3}-4(1+\sqrt{3})^{2n+1}$

but I am not sure how to prove the recurrence from here.

-

Prove the same relation for $1-\sqrt 3$, and check that the resulting powers are all smaller than 1, all negative, and when added to the same powers of $1+\sqrt 3$ you end up with an integer: For all $k=1,2,\dots$, $$(1+\sqrt 3)^k+(1-\sqrt 3)^k$$ is an integer.
Ah, that's nice. I tried all sorts of things with $\sqrt{3}-1$ but never tried adding it. –  Derek Scavo Nov 30 '10 at 0:25
@Derek: If adding powers of $1-\sqrt{3}$ wouldn't occur to you in the first place, but you know what recurrence relation is supposed to be satisfied and the first few values, you can explicitly solve for what the sequence is supposed to be using the method at en.wikipedia.org/wiki/…. You will end up with an explicit formula that involves powers of $1+\sqrt 3$ and $1-\sqrt 3$, and since $|1-\sqrt{3}|\lt 1$, with some estimates you can show that it will never affect your floor value. –  Jonas Meyer Nov 30 '10 at 0:39