What particular solution should I guess for this relation? Just trying to solve a non-homogeneous recurrence relation:
$$f(n) = 2f(n-1) + n2^n$$
$$f(0) = 3$$

Characteristic equation is:
$$f(n) - 2f(n-1) = 0$$
$$a-2 = 0$$
$$a = 2$$
Homogeneous solution is:
$$f_H(n) = b_0\cdot (2)^n$$

Right-hand side is:
$$n2^n$$
What is the particular guess I should be taking based on this?
 A: (This is not a guess, but rather an approach to finding the solution.)
Firstly, we rearrange the given relation to get:
$$f(n) - 2f(n-1) = n2^n$$
Divide throughout by $2^n$. This gives us:
$$\frac{f(n)}{2^n} - \frac{f(n-1)}{2^{n-1}} = n$$
Do a summation to exploit the potential cancellations on the LHS:
$$\sum_{i = 1}^n\left(\frac{f(i)}{2^i} - \frac{f(i-1)}{2^{i-1}}\right) = \sum_{i = 1}^n i$$
$$\frac{f(n)}{2^n} - \frac{f(0)}{2^0} = \frac{n(n+1)}{2}$$
$$\frac{f(n)}{2^n} = \frac{n(n+1)}{2} + 3$$
$$f(n) = 2^{n-1}(n^2 + n + 6)$$

In general, if you have stuffs like $a_n - ka_{n-1} = b_n$ where $k$ is a constant, dividing throughout by $k^n$ might be a good way to start.
A: The answer by Yiyuan Lee is very good and clever.  
More generally, you will need to solve the homogeneous as you did and notice that $a = 2$. Then look at the RHS and notice that it also is $2^n$ so you need to look for a solutions of the form :
$$cn2^n$$
However this is the RHS so add a $n^2$ term to try finding a solution of the form :
$$(c_1n^2 + c_2n)2^n$$
Substitute this into the equation and solve for $c_1$ and $c_2$.
A: Suggestion: work it out in three steps.


*

*Try something like the RHS, say $an2^n$.

*If necessary modify this by including "lower order" terms - in this case, change the guess to $(an+b)2^n$.

*Compare the homogeneous solution, here $f_H(n)=A2^n$.  If your guess has any terms shared with $f(n)$, multiply the guess by $n$.  Repeat until there are no shared terms.  In this case $(an+b)2^n$ has the term $b2^n$ in common with $f_H(n)$, so modify the guess to $(an^2+bn)2^n$.  There is now nothing in common with $f_H(n)$, so this is the one to go with.
A: I have tried to compute some values and I found this formula:
$$f(n)=3\cdot2^n+\frac{n^2+n}22^n$$
It is easy to prove it by induction on $n$.
A: Just solve the bugger by using generating functions. Define $F(z) = \sum_{n \ge 0} f(n) z^n$, adjust indices so there aren't subtractions:
$$
f(n + 1) = 2 f(n) + (n + 1) 2^{n + 1}
$$
Multiply by $z^n$, sum over $n \ge 0$, recognize:
\begin{align}
\sum_{n \ge 0} f(n + 1) z^n    &= \frac{F(z) - f(0)}{z} \\
\sum_{n \ge 0} (2 z)^n         &= \frac{1}{1 - 2 z} \\
\sum_{n \ge 0} n 2^n z^{n - 1} &= \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - 2 z} \\
\sum_{n \ge 0} (n + 1) 2^{n + 1} z^n
                               &= \frac{2}{(1 - 2 z)^2}
\end{align}
This gives:
$$
\frac{F(z) - 3}{z} = 2 F(z) + \frac{2}{(1 - 2 z)^2}
$$
Solving for $F(z)$, as partial fractions:
$$
F(z) = \frac{3}{1 - 2 z} - \frac{1}{(1 - 2 z)^2} + \frac{1}{(1 - 2 z)^3}
$$
Using the generalized binomial theorem:
\begin{align}
f(n) &= 3 \binom{-1}{n} (-2)^n - \binom{-2}{n} (-2)^n + \binom{-3}{n} (-2)^n \\
     &= 3 \cdot 2^n - (n + 1) 2^n + \frac{(n + 2) (n + 1)}{2} 2^n \\
     &= (n^2 + n + 6) \cdot 2^{n - 1}
\end{align}
At first glance, this checks, as $f(0) = 3$.
