Converting Recursive Function into Closed/Explicit Form so I have this recursive function here:
$\forall n>1,f(n) = 2(f(n-1)) + n-1$, (where it is $0$ when $n$ is less than $1$)
So I have tried to use iteration for this but it just gets more complicated as I go on, so can anyone help me out here? Thanks so much! Sorry for the bad format as I am new here. Cheers!
 A: You could use generating functions to solve the recurrence relation. We use GFs  as formal power series i.e. purely algebraically without considering convergence or limits. A formidable starter for these techniques is H.Wilf's Generatingfunctionology.

Recurrence relation:
  \begin{align*}
f(n)&=2f(n-1)+n-1\qquad\qquad n\geq 1\\
f(0)&=0
\end{align*}

Let's consider the generating function

\begin{align*}
F(z)=\sum_{n=0}^{\infty}f(n)z^n
\end{align*}

and use the Ansatz:

\begin{align*}
\sum_{n=1}^{\infty}f(n)z^n&=\sum_{n=1}^{\infty}\left(2f(n-1)+n-1\right)z^n\tag{1}\\
&=2\sum_{n=1}^{\infty}f(n-1)z^n+\sum_{n=1}^{\infty}(n-1)z^n\\
&=2\sum_{n=0}^{\infty}f(n)z^{n+1}+\sum_{n=0}^{\infty}nz^{n+1}\tag{2}\\
&=2zF(z)+z^2\sum_{n=0}^{\infty}nz^{n-1}\tag{3}\\
&=2zF(z)+z^2D\left(\frac{1}{1-z}\right)\tag{4}\\
&=2zF(z)+\frac{z^2}{(1-z)^2}
\end{align*}

Comment:


*

*In (2) we made an index shift $n\rightarrow n-1$

*In (3) you may observe that the right sum is the derivative of the geometrical series $\frac{1}{1-z}$

*In (4) we apply the formal differential operator $D$

Since the left hand side of (1) is
  \begin{align*}
\sum_{n=1}^{\infty}f(n)z^n=F(z)-f(0)=F(z)
\end{align*}
  it follows, that the recurrence relation translated in the language of generating functions gives
  \begin{align*}
F(z)=2zF(z)+\frac{z^2}{(1-z)^2}
\end{align*}

Now we calculate $F(z)$ and find a series representation. 

\begin{align*}
F(z)&=\frac{z^2}{(1-z)^2(1-2z)}\tag{5}\\
&=\frac{1}{1-2z}-\frac{1}{(1-z)^2}\\
&=\sum_{n=0}^{\infty}(2z)^n-\sum_{n=0}^{\infty}\binom{-2}{n}(-z)^n\\
&=\sum_{n=0}^{\infty}2^nz^n-\sum_{n=0}^{\infty}\binom{n+1}{n}z^n\tag{6}
\end{align*}

Observe, that we applied partial fraction decomposition in (5).

Now it's time to harvest: Extracting the coefficient $[z^n]F(z)=f(n)$ from the series representation of (6) gives us
  \begin{align*}
[z^n]F(z)=f(n)=2^n-n-1
\end{align*}

A: Start noting, using recursion, that
$$f(n)=2f(n-1)+(n-1)=2^2 f(n-2)+2(n-2)+(n-1)=$$
$$2^3 f(n-3)+2^2(n-3)+2^1(n-2)+(n-1)=...$$
So you should be able to prove (using induction, maybe) that
$$f(n)=2^{n-1} f(1)+\sum_{i=1}^{n-1} 2^{i-1}(n-i)$$
Now
$$\sum_{i=1}^{n-1} 2^{i-1}(n-i)=\sum_{i=1}^{n-1} 2^{i-1} n -i2^{i-1}=n\sum_{i=1}^{n-1} 2^{i-1}-\sum_{i=1}^{n-1} i2^{i-1}$$
Once again, the first sum is geometric. For the other addend, you can work it this way:
$$S_n:=\sum_{i=1}^n i2^{i}$$
$$2S_n=\sum_{i=1}^n i2^{i+1}=\sum_{i=2}^{n+1}(i-1)2^n=\sum_{i=2}^{n+1}i2^n-\sum_{i=2}^{n+1}2^i=S_n-2+(n+1)2^{n+1}-\sum_{i=2}^{n+1}2^i$$
So
$$S_n=(2S_n-S_n)=(n+1)2^{n+1}-2+\sum_{i=2}^{n+1}2^i$$
If I didn't write something wrong somewhere, this is a sketch of how to deal with it. You should now write the explicit result for the geometric sums and you'll be pretty much ok.
