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.

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

Let $L(n)=\lfloor(1+\sqrt{5})^n\rfloor$. What kind of a linear recurrence is satisfied by $L(n)$? I have no idea how to go about this, because of the presence of the greatest integer function.

Please feel free to retag it as I kept getting an error on every tag I thought was appropriate.

share|cite|improve this question
1 – Aryabhata Nov 27 '10 at 7:46
up vote 4 down vote accepted

Do you have any reason to suspect $L(n)$ should satisfy a linear recurrence? Here's a way you can prove that it doesn't satisfy a linear recurrence of depth 2 (which can be generalised to any depth).

Step 1: Compute $L(n)$ for small $n$: 3, 10, 33, 109, 354, 1148, 3716, ...

Step 2: Assume $b L(n-2)+a L(n-1)=L(n)$ for some $a,b$. Using the data from Step 1 we obtain the system of linear equations:

  • $3b+10a=33$,
  • $10b+33a=109$,
  • $33b+109a=354$.

In fact, we can keep going forever adding equations $109b+354a=1148$, and so on.

Step 3: Solve the system of linear equations (or get your computer to do it for you (using e.g. WolframAlpha)). In this case there are no solutions, so $L(n)$ does not satisfy a linear recurrence of depth 2. If you feel that the starting point shouldn't be $L(1)$, you can use the same argument starting later in the sequence.

Assuming I coded things correctly, I have checked that $L(n)$ doesn't satisfy a linear recurrence of depth 10 (or less). [It's probably a good idea to check this yourself if you end up relying on this result.] I also attempted to find a linear recurrence with polynomial coefficients for $L(n)$ to a limited extent (see A=B about Sister Celine's Technique for more info).

Finally, if you're allowed to use an auxiliary function, then let $s(1)=1+\sqrt{5}$ and for $n \geq 2$ let $s(n)=(1+\sqrt{5}) \cdot s(n-1)$. Then $L(n)=\lfloor s(n) \rfloor$ for all $n \geq 1$.

share|cite|improve this answer
Sorry I messed up here. The question (in a set of notes I am reading) was about $\lfloor(1+\sqrt{3})^n\rfloor$. I wrote up a code and found a recurrence but cannot prove it. I shall write a follow up question. Thanks for the elaborate answer. – Derek Scavo Nov 29 '10 at 20:55
Hmm.. interesting. I wonder why these two similar-looking sequences have different behaviour. – Douglas S. Stones Nov 29 '10 at 22:47
@Douglas The floors are confusing me, but here's an attempt at explanation. Pretend that the given sequence is $[ (1+\sqrt{3})^n ]$ where $[x]$ is the integer closest to $x$. (So, $[1.3] = 1$ and $[1.6]=2$.) Then, $[(1+\sqrt{3})^n] = (1+\sqrt{3})^n + (1-\sqrt{3})^n$ for $n \geq 3$. Now, this satisfies a linear recurrence using standard methods. On the other hand, in the $(1+\sqrt{5})^n$ case, we can still add $(1-\sqrt{5})^n$ to make it an integer, but this observation is not useful since $(1-\sqrt{5})^n$ itself goes to $\infty$ for $n$ large. (I don't yet know how to handle the floors e.g.) – Srivatsan Aug 1 '11 at 16:12

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.