Unwind this recursive function

Question

given the function $f(n)= \begin{cases} 1 & n = 0 \\ 4f(n-1) + 2(n-1) & n \geq 0 \end{cases} $. Unwind this function into a non-recursive definition. I tried and was able to get upto: $4^{n}+2\cdot4^n\sum_{i=1}^{n-1}((\frac{1}{4})^ii)$. I don't know what to do next, nor do I know if this is correct in the first place.

Answer 1

You can add $\frac{2}{3}\left(n-1 \right)$ to both sides of $f\left(n \right)=4f\left(n-1 \right)+2\left(n-1 \right)$ and rearrange to obtain that $$f\left(n \right)+\frac{2}{3}\left(n-1 \right)=4\left( f\left(n-1 \right)+\frac{2}{3}\left(n-1 \right)\right)$$ Now for any $1 \le n$ denote $g\left(n\right) \equiv f\left(n \right)+\frac{2}{3}\left(n-1 \right)$, hence obtain that $$g\left(n\right) = 4\left( g\left(n-1 \right)+\frac{2}{3}\right)$$ for any $1 \le n$. Now add $\frac{8}{9}$ to both sides of $g\left(n\right) = 4\left( g\left(n-1 \right)+\frac{2}{3}\right)$ and rearrange to obtain that $$g\left(n\right)+\frac{8}{9} = 4\left( g\left(n-1 \right)+\frac{8}{9}\right)$$ for any $1 \le n$. Now for any $1 \le n$ denote $h\left(n\right) \equiv g\left(n\right)+\frac{8}{9}$, hence obtain that $$h\left(n\right)=4h\left(n-1\right) $$ for any $1 \le n$. Now observe that $h\left(n\right)$ is a geometric progression and therefore $$h\left(n\right)=h\left(1\right)4^{n-1}$$ Substitute $g$ into $h$ and $f$ into $g$ to obtain that $$f\left(n\right)=g\left(n\right)-\frac{2}{3}\left(n-1 \right)=\left(h\left(n\right)-\frac{8}{9}\right)-\frac{2}{3}\left(n-1 \right)=h\left(1\right)4^{n-1}-\frac{2}{3}n-\frac{2}{9}$$ for any $1 \le n$ Now to find $h\left(1\right)$ just substitute $n=1$ to the latter equation and use the definition of $f$ to obtain that $$4=4f\left(0\right)+0=4f\left(1-1\right)+2\left(1-1\right)=h\left(1\right)4^{1-1}-\frac{2}{3}-\frac{2}{9}=h\left(1\right)-\frac{8}{9}$$ thus $h\left(1\right)=\frac{44}{9}$. In summation $$f\left(n\right)=\frac{11}{9}4^{n}-\frac{2}{3}n-\frac{2}{9}$$ for any $1 \le n$.

Answer 2

This is a linear difference equation where the solution is the sum of the homogeneous solution and a particular solution.

Let $f(n) =a^n$ to find the solution for the homogeneous difference equation and you get $a=4$

For the particular solution let $f_p (n) = An+B$ and you get $A=-2/3$ and $B=-2/9$

Thus your solution is $$f(n) = K(4)^n-2/3 n -2/9 $$

The initial condition of $f(0)=1$ is used to find $K=\frac {11}{9}$

The final result is $$ f(n) =\frac {11}{9} (4)^n -\frac {2n}{3}- \frac {2}{9}$$