Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

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|improve this answer
    
By "smaller than 1" I meant "smaller than 1 in absolute value", sorry about the typo. –  Andres Caicedo Nov 30 '10 at 0:20
1  
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
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 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
add comment

Your Answer

 
discard

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.