Solve the linear recurrence with initial conditions $a_n=a_{n-1}+2^n+1$ and $ a_0 =0$

Question

Let $(a_n)_{n\geq0}$ be the sequence defined by $$a_0=0\qquad\text{and}\qquad\forall n\geq0,\ a_n=a_{n-1}+2^n+1.$$

I know this is a non-homogeneous case and so far as I have gotten the general homogeneous solution of A1(1)^n and I am having trouble with the particular solutions. I know I can split them up and solve $2^n$ and $1$ separately but every time I do I get a solution that isn't correct.

Answer 1

Hint: $a_{n-1} = a_{n-2} + 2^{n-1} +1$, so $a_n = a_{n-2} + 2^n+2^{n-1} +2$. Can you handle from here?

Answer 2

Hint: If we let $b_n=a_n-n$ then these have the recursion $b_n=b_{n-1}+2^n$.

Answer 3

You can use: $$a_n-a_0=\sum_{k=0}^{n-1}(a_{k+1}-a_k)=\sum_{k=0}^{n-1}\bigl(2^{k+1}+1\bigr)=2^{n+1}-2+n,$$ hence (since $a_0=0$): $$a_n=2^{n+1}+n-2.$$