Can I solve this recurrence relation with characteristic polynomials

Question

Solve the following recurrence relations subject to the initial condition: $$a_{n}=2a_{n-1}+2^n, a_{1}=1$$

I have successfully solved this problem via telescoping, however I would like to solve this problem with characteristic polynomials. Is there a way a way to solve this, or more preferably recurrence relations with constant terms?

Edit:

I am uncomfortable with telescoping because it doesn't always work, if there is a deterministic approach to solve recurrence relations(at least first order) with constant term other than generating functions, please mention.

Answer 1

I like the method of annihilators:

Let $L$ be the left shift operator on sequences, i.e. $L(c_0,c_1,\ldots) = (c_1,\ldots)$.

The given recurrence is $(L-2)a_n = 2^n$. But $L-2$ annihilates the right-hand side, so $(L-2)^2a_n = 0$, i.e. we have the homogeneous recurrence $a_n - 4a_{n-1} + 4a_{n-2}=0$.

This corresponds to the characteristic equation $(x-2)^2 = 0$, and the general solution is $a_n = A2^n + Bn2^n$.

Plugging into the original recurrence, we get $(A2^n + Bn2^n) = 2(A2^{n-1} + B(n-1)2^{n-1}) + 2^n$ $= (A-B+1)2^n + Bn2^n$, so $A = A-B+1$, i.e. $B=1$. (we can simplify this calculation by just plugging in $Bn2^n$, because with some thought the $A$ terms must cancel out)

So the solution, without the initial condition, is $a_n = (n+A)2^n$, and $a_1=1$ gives us $a_n = (n-1/2)2^n$.

Answer 2

Let $a_n=t^n$ be the solution. On substitution in the given equation with RHS as zero, you get $t=2$ thereby giving $c.2^n$ ($c$ is arbitrary constant) as the solution of homogeneous part.

To find solution corresponding to $2^n$ appearing on RHS of the given equation, take trial solution as $An.2^n$ and substitute it in given equation. On comparing the like terms you can easily get $A=1/2$. Now, write $a_n=c.2^n+n.2^{n-1}$ as the complete solution.