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