Converting Recursive Function into Closed/Explicit Form

Question

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!

Answer 1

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.

Answer 2

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