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?
On
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.
On
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$.
On
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$.
On
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$.
(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.