Justifying a recurrence relationship I have a recurrence relationship here that I have to justify:

$A_n = A_{n-1} + A_{n-2} + 1 $ and $A_0 $ = 1 and $A_1 $ = 1

I know that the first step is to turn this into a characteristic equation of order 2, and then go on to solve that equation. I can't seem to get over that first hump in finding the characteristic equation for the above recurrence relationship. I think it's the + 1 that's stopping me from being able to factor out $x^{n-2} $ to find the appropriate quadratic equation to solve. I just wanted to know how I can go about starting this one as I know how to do the rest.
Like we do for linear ODEs, we can talk about homogeneous equation and particular solution.

Here homogeneous equation is $A_n=A_{n-1}+A_{n-2}$ or similarly $A_{n+2}-A_{n+1}-A_n=0$ 

leading to characteristic equation  $r^2-r-1=0$ with solution $r=\varphi,\bar\varphi$

And $A_n=a\,\varphi^n+b\,\bar\varphi^n$ characteristic of Fibonacci sequence.

Now when considering the whole equation with an RHS, you need to find a particular solution for it. Equation's linearity ensures that the sum of the general homogeneous solution and the particular solution is the overall general solution.

Here there is an obvious particular solution $A_n=-1$ since $-1=-1-1+1$.

But you can also search for polynomial solutions $A_n=(cn+d)$ and after substitution find $cn+d=2cn+2d-3c+1\iff c=0,d=-1$.


Finally, $A_n=a\,\varphi^n+b\,\bar\varphi^n-1$ and you find $a,b$ so that the values for $A_0$ and $A_1$ agree to initial conditions.

$\begin{cases}A_0=a+b-1=1\\ A_1=a\varphi+b\bar\varphi-1=1\end{cases}\iff\begin{cases}a=1+\dfrac 1{\sqrt{5}}\\b=1-\dfrac 1{\sqrt{5}}\end{cases}$


  $A_n=(\varphi^n+\bar\varphi^n)+\frac 1{\sqrt{5}}(\varphi^n-\bar\varphi^n)-1$
For this specific case, it can be observed that it is $2$ times the Fibonacci Sequence's closed form minus $1$.

So that is,

$$\frac{2}{\sqrt 5}\left( \left( \frac{1+\sqrt 5}{2} \right)^n - \left( \frac{1- \sqrt 5}{2} \right)^n \right) -1$$

One can prove this with induction.