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.


1 Answer 1


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$.

  • $\begingroup$ 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. $\endgroup$ Nov 29, 2010 at 20:55
  • $\begingroup$ Hmm.. interesting. I wonder why these two similar-looking sequences have different behaviour. $\endgroup$ Nov 29, 2010 at 22:47
  • $\begingroup$ @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.) $\endgroup$
    – Srivatsan
    Aug 1, 2011 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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