Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:


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


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

share|cite|improve this question
up vote 10 down vote accepted

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.

share|cite|improve this answer
By "smaller than 1" I meant "smaller than 1 in absolute value", sorry about the typo. – Andrés E. Caicedo Nov 30 '10 at 0:20
Andres, you could go back and edit it, you know... :) – J. M. Nov 30 '10 at 0:23
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…. 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.