6
$\begingroup$

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
    http://oeis.org/A0571462010-11-27

1 Answers 1

4

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

  • 0
    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.2010-11-29
  • 0
    Hmm.. interesting. I wonder why these two similar-looking sequences have different behaviour.2010-11-29
  • 0
    @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.)2011-08-01