Annihilator method for Difference Equation. Suppose we have some difference equation $f(y(n))$ which is yet to be defined. Now assume it is equal to some function of $n$. When using the annihilator method we first rewrite our difference equation $f(y(n))$ to some characteristic polynomial. Then we must find a difference equation for the RHS, suppose our RHS is equal to $n2^n - 1$. How does one construct a difference equation of the RHS?

To resume and reformulate your problem, we have an inhomogeneous recurrence relation $F(a_n,\ldots,a_0) = g(n)$, which can be rewritten as the more general homogeneous problem $\Phi(a_n,\ldots,a_0) = 0$, with $\Phi = G \circ F$, where $G$ is the annihilator of $g$. In practice, it means that the sequence $b_n = g(n) := n2^n-1$ satisfies $G(b_n,\ldots,b_0) = 0$.
It it to be recalled that solutions of the form $(\alpha_0+\alpha_1n+\alpha_2n^2+\ldots+\alpha_m\alpha^m)\lambda^n$, with $m \le n$, come from the characteristic polynomial $(r-\lambda)^m$, which itself comes from the operator $(S-\lambda)^m$, where $S$ is the shift operator, defined by $Sb_n = b_{n+1}$.
In the present case, we have two roots, namely $\lambda = 1$ and $\lambda = 2$, with a linear prefactor for the second root, hence the characteristic polynomial $(r-1)(r-2)^2$ and the annihilator $G = (S-1)(S-2)^2 = S^3 - 5S^2 + 8S - 4$.
