I'm quite stuck on how to solve recurrence/difference equations.
For example I have the following linear inhomogeneous equation: $a_n = 2a_{n-1} + 2^n n$, and $a_0 = 1/2$
I know that $2a_{n-1} = 1/2(2^n)$, and then we have $a_n = 1/2(2^n) + n(2^n)$. This is where I'm stuck though and the inhomogeneous part is throwing me off.
Am I in the right direction thinking that: $a_n = \frac12 \prod 2^n n$ ?
No answers please but some nudges in the right direction would be greatly appreciated. Thanks!
On
You didn't use the generating-functions tag, so here is more than a nudge for that approach. Let $A(z)=\sum_{n=0}^\infty a_n z^n$ be the ordinary generating function for $(a_n)$. Then the recurrence and initial condition imply that \begin{align} A(z) &= \frac{1}{2} z^0 + \sum_{n=1}^\infty \left(2 a_{n-1} + 2^n n\right)z^n \\ &= \frac{1}{2} + 2z \sum_{n=1}^\infty a_{n-1} z^{n-1} + 2z\sum_{n=1}^\infty n (2z)^{n-1} \\ &= \frac{1}{2} + 2z A(z) + 2z \frac{1}{(1-2z)^2}, \end{align} so \begin{align} A(z) &= \frac{1/2 + 2z /(1-2z)^2}{1-2z} \\ &= \frac{1+4z^2}{2(1-2z)^3} \\ &= \frac{1}{(1 - 2 z)^3} - \frac{1}{(1 - 2 z)^2} + \frac{1/2}{1 - 2 z} \\ &= \sum_{n=0}^\infty \binom{n+2}{2} (2 z)^n - \sum_{n=0}^\infty \binom{n+1}{1} (2 z)^n + \frac{1}{2}\sum_{n=0}^\infty \binom{n+0}{0} (2 z)^n \\ &= \sum_{n=0}^\infty \frac{(n+2)(n+1)-2(n+1)+1}{2} (2 z)^n \\ &= \sum_{n=0}^\infty (n^2+n+1) 2^{n-1} z^n, \end{align} which immediately implies that $a_n = (n^2+n+1) 2^{n-1}$.
Hint:
Set $b_n = \frac{a_n}{2^n}$. Then dividing your recurrence by $2^n$ gives
$$b_n = b_{n-1} + n.$$
Do you see how to find a closed form for $b_n$? Do you see how to turn this into a closed form for $a_n$?
As a general "life pro tip", when you see a recurrence with a geometric term (i.e. something that looks like $r^n$) that's otherwise linear, you should try dividing by it. Since $r^{n+1} = r \cdot r^n$, this procedure turns your geometric term into a constant one, which is easier to handle.
I hope this helps ^_^