7
$\begingroup$

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.

1 Answers 1

10

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.

There are several ways of checking this fact. For example, by induction. Or by using the Binomial theorem.

  • 0
    By "smaller than 1" I meant "smaller than 1 in absolute value", sorry about the typo.2010-11-30
  • 1
    Andres, you could go back and edit it, you know... :)2010-11-30
  • 0
    Ah, that's nice. I tried all sorts of things with $\sqrt{3}-1$ but never tried adding it.2010-11-30
  • 2
    @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 http://en.wikipedia.org/wiki/Recurrence_relation#Linear_homogeneous_recurrence_relations_with_constant_coefficients. 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.2010-11-30