Recurrence relation satisfied by $\lfloor(1+\sqrt{5})^n\rfloor$ 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.
 A: 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$.
