Solving $g(n)=2g(n-1)+n+2^n$

Question

I am learning how to solve recurrence relations and I have an equation that got me to a dead end:

$$g(n)=2g(n-1)+n+2^n$$

My problem is the non-homogeneous part.

Answer 1

The brutal way is to take: $$ f(x) = \sum_{n\geq 0} g(n)\,x^n $$ and assuming $g(0)=0$, $$ x\cdot f(x) = \sum_{n\geq 1} g(n-1)\,x^{n} $$ so: $$ f(x)-2x f(x)=\sum_{n\geq 1}(n+2^n) x^n = \frac{x}{(1-x)^2}+\frac{2x}{1-2x} $$ leads to: $$ f(x) = \frac{x}{(1-x)^2(1-2x)}+\frac{2x}{(1-2x)^2} $$ and now we may recover the coefficients $g(n)$ from partial fraction decomposition, leading to:

$$ g(n) = (n+2)(2^n-1).$$

---

Alternative approach, without generating functions. If we set: $$\Delta_n = g(n+1)-2 g(n) = n+1+2^{n+1} $$ we have: $$\Delta_n + 2 \Delta_{n-1} +\ldots + 2^k \Delta_{n-k} = g(n+1)-2^{k+1}g(n-k)$$ so: $$ \sum_{k=0}^{n}\Delta_{n-k}2^k = g(n+1)-2^{n+1}g(0) $$ from which: $$ g(n+1)=2^{n+1}g(0) + \sum_{k=1}^{n+1}2^{n+1-k}\left(k+2^{k}\right) $$ or: $$ g(n) = 2^n g(0) + 2^n\sum_{k=1}^{n}\frac{k+2^k}{2^k} = 2^n g(0) + (n+2)(2^{n}-1).$$