closed form for this recurrence

Question

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$.

Answer 1

Hint: Let $g(n)=\dfrac{f(n)}{2^{n-2}}$. Then $g(n)=g(n-1)+(n-1)$, which is very easy to solve.

Answer 2

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}}$$

Answer 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} $$