I am having trouble figuring out if the following recurrence has a closed form: $$f(n)=2f(n-1)+(n-1)2^{n-2}$$
I have never really done such problems, so I dont know what is a good strategy. I will appreciate any hints!
Edit: $f$ is defined for $n\geq 1$ and $f(1)=0$.
Hint: Let $g(n)=\dfrac{f(n)}{2^{n-2}}$. Then $g(n)=g(n-1)+(n-1)$, which is very easy to solve.
There is a general method for linear equations with constant terms: $$a_kf(n+k)+a_{k-1}f(n+k-1)+\cdots+a_0f(n)=\phi(n)$$
And it consist in solving the characteristic equation $a_kr^k+a_{k-1}r^{k-1}+\cdots+a_0=0$.
The roots $r_i$ give the general solution of the homogeneous equation (i.e. when $\phi=0$) under the form
$$f(n)=\alpha_k(r_k)^n + \alpha_{k-1}(r_{k-1})^n + \cdots + \alpha_0(r_0)^n$$
Then find just $1$ particular solution when RHS is the actual $\phi$ and add it to the general solution found before (exactly like we do for differential equations solving).
Let's apply it here:
$f(n)-2f(n-1)=(n-1)2^{n-2}$ can be transformed to $$f(n+1)-2f(n)=n\,2^{n-1}$$
The characteristic equation is very simple: $$r-2=0$$
With a single root $r=2$.
Thus the solutions of $f(n+1)-2f(n)=0$ are given by $f(n)=\alpha\, 2^n$
Now we have to find a particular solution with RHS $\quad\phi(n)=n\,2^{n-1}=\frac n2\times 2^n$
When RHS contains $2^n$ where $2^n$ is also a term of the general solution of homogeneous equation, we search for a polynomial of degree +1.
So we will search for a solution of the form $p(n)=(an^2+bn+c)\times 2^n$
$\require{cancel}\begin{align}p(n+1)-2p(n)&=(a(n+1)^2+b(n+1)+c)2^{n+1}-2(an^2+bn+c)2^n\\&=2^{n+1}\bigg[\cancel{an^2}+2an+a+\cancel{bn}+b+\cancel{c}-\cancel{an^2}-\cancel{bn}-\cancel{c}\bigg]\\&=2^{n+1}[2an+a+b]=2^{n+1}\times\frac n4\end{align}$
Thus $2a=\frac 14$ and $a+b=0$ and $\quad p(n)=\dfrac{n(n-1)}8$
Finally the global solution is $$f(n)=2^n\left(\alpha+\frac{n(n-1)}8\right)$$
The final step is to use initial condition: $f(1)=0$
$f(1)=2(\alpha+0)\implies \alpha=0$ thus
$$\bbox[5px,border:2px solid red]{f(n)=n(n-1)2^{n-3}}$$
I was thinking on using the Z-transform here: $$ f(n) = 2f(n-1) + (n-1)2^{n-2} $$ using $f(n) = x_n$ and $ f(n-1) = x_{n-1}$ we get: $$ x_n = 2x_{n-1}+n\frac{2^n}{4}-\frac{2^n}{4} $$ Taking the transform on both sides: $$ X(z) = 2(z^{-1}X(z)+x_{-1}) + \frac{2z}{4(z-2)^2}-\frac{z}{4(z-2)} $$ $$ X(z) = 2(z^{-1}X(z)+\frac{1}{8}) + \frac{2z}{4(z-2)^2}-\frac{z}{4(z-2)} $$ $$ X(z)(1-\frac{2}{z}) = \frac{2z-z(z-2)}{4(z-2)^2} + \frac{1}{4}$$ $$ X(z) = \frac{z^2(4-z)}{4(z-2)^3} + \frac{z}{4(z-2)}$$ Taking the inverse Z transform we get a result: $$ x_n = n(n-1)2^{n-3} $$
