<s>[INST] How to solve the difference equation $u_n = u_{n-1} + u_{n-2}+1$ Given that:
$$
\begin{equation}
  u_n=\begin{cases}
    1, & \text{if $0\leq n\leq1$}\\
    u_{n-1} + u_{n-2}+1, & \text{if $n>1$}
  \end{cases}
\end{equation}
$$
How do you solve this difference equation?
Thanks

EDIT:
From @marwalix's answer:
$$
u_n=v_n-1
$$
$$
\begin{equation}
  v_n=\begin{cases}
    2, & \text{if $0\leq n\leq1$}\\
    v_{n-1} + v_{n-2}, & \text{if $n>1$}
  \end{cases}
\end{equation}
$$
Characteristic equation of $v_n$ is
$$
r^2=r+1
$$
Therefore,
$$
r=\frac{1\pm\sqrt{5}}{2}
$$
Therefore, the general solution for $v_n$ is
$$
v_n=A\left(\frac{1+\sqrt{5}}{2}\right)^n+B\left(\frac{1-\sqrt{5}}{2}\right)^n
$$
When $n=0$,
$$
2=A+B
$$
When $n=1$,
$$
2=A\left(\frac{1+\sqrt{5}}{2}\right)+B\left(\frac{1-\sqrt{5}}{2}\right)
$$
Therefore,
$$
A=\frac{5+\sqrt{5}}{5}
$$
$$
B=\frac{5-\sqrt{5}}{5}
$$
Therefore,
$$
u_n=\frac{5+\sqrt{5}}{5}\left(\frac{1+\sqrt{5}}{2}\right)^n+\frac{5-\sqrt{5}}{5}\left(\frac{1-\sqrt{5}}{2}\right)^n-1
$$
 [/INST] Write $u_n=v_n+a$ where $a$ is a constant. In that case the recurrence reads as follows
$$v_n+a=v_{n-1}+v_{n-2}+2a+1$$
So if  we chose $a=-1$ we are left with
$$v_n=v_{n-1}+v_{n-2}$$
And we're back to a Fibonnacci type and in this case we have $v_0=v_1=2$
</s>