Establishing formula from recurrence

Solution 1:

As you can see from Git Gud’s link, there are many techniques for finding closed forms for recurrences. Some are of quite limited applicability, while others (e.g., generating functions) are much more powerful. Here’s a technique of very limited applicability that handles recurrences of the type $f(n)=af(n-1)+b$ very nicely; I’ll illustrate it with the recurrence

$$\begin{align*} f(n)&=-4f(n-1)+3\quad\text{for}\quad n>1\\ f(1)&=1\;. \end{align*}\tag{1}$$

The idea is to make a substitution to replace $f$ by a function $g$ that grows exponentially. Let $g(n)=f(n)-d$ for some as yet undetermined constant $d$, so that $f(n)=g(n)+d$. Substitute into the recurrence in $(1)$ to get

$$g(n)+d=-4\big(g(n-1)+d\big)+3=-4g(n-1)+3-4d\;,$$

which simplifies to $g(n)=-4g(n-1)+3-5d$. Now choose $d$ so that $3-5d=0$, i.e., $d=\frac35$; then $g(n)=-4g(n-1)$, $g(1)=f(1)-d=\frac25$, and we can replace $(1)$ with

$$\begin{align*} g(n)&=-4g(n-1)\quad\text{for}\quad n>1\\ g(1)&=\frac25\;. \end{align*}\tag{2}$$

But $(2)$ is trivial: it has the closed form $g(n)=\dfrac25(-4)^{n-1}$. It follows that

$$f(n)=g(n)+d=\frac25(-4)^{n-1}+\frac35=\frac{3-(-1)^n2^{2n-1}}5\;.$$