[Math] Converting Recursive Function into Closed/Explicit Form

closed-formfunctionsrecursion

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!

Best Answer

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

Related Question