# Express recursive function in Fibonacci

Given the Fibonacci function and the function $L_n = L_{n-1} + L_{n-2} + 1$, how do I go from this: $L_n + 1 = L_{n-1} + L_{n-1} + 1 + 1 \\ (L_n + 1) = (L_{n-1} + 1) + (L_{n-2} + 1)$

To this: $L_n = 2 \cdot F_n - 1$

When $L_0 = L_1 = 1 = F_0 = F_1$. I don't understand it, because $L_2 = F_1 + 1$ and $L_0 = F_{-1} + 1$, but there are no values next to each other where this is true. Can someone explain how to get to the second formula?

$$(L_n+1)=(L_{n-1}+1)+(L_{n-2}+1)$$

and

$$L_0+1=2, L_1+1=2$$.

Comparing with $$2F_n=2F_{n-1}+2F_{n-2}$$

and $$2F_0=2, 2F_1=2$$.

We get $$L_n+1=2F_n$$

The sequence $A_n = L_n + 1$ obey the Fibonacci recursion $A_n = A_{n-1} + A_{n - 2}$. The initial values are $2, 2$, so we have $A_n = 2F_n$. Now substitute $A_n= L_n + 1$, move the $1$ over to the other side, and you've done.