How to solve the difference equation $u_n = u_{n-1} + u_{n-2}+1$

Question

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

Answer 1

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$

Answer 2

Same (essentially) as marwalix ... Can you do the homogeneous equation? Can you find a particular solution to the inhomogeneous equation? Put them together to get the general solution. Then use your initial values to get your solution.