How to deduce a closed formula given an equivalent recursive one?

Question

I know how to prove that a closed formula is equivalent to a recursive one with induction, but what about ways of deducing the closed form initially?

For example:

$$ f(n) = 2 f(n-1) + 1 $$

I know how to use induction to prove that $\forall n \ge1$:

$$ f(n) = 2^n f(0) + 2^n - 1 $$

And I was able to come up with that formula in the first place just by examining it informally. It seems like there should have been a straightforward, formal way to deduce the closed form from the recursive definition in the first place, but I'm blanking.

I know it's not always easy (e.g. Fibonacci) but it seems like it ought to be here. For example, how might I go about procedurally deducing the closed form for:

$$ f(n) = 2*f(n-1) + k $$

Thanks.

Answer 1

Here is a generating function method that usually works (not elegant in this case, though).

First of all, remember the infinite geometric progression formula (we'll use it multiple times):

$$|x|<1\implies 1+x+x^2+x^3+\cdots=\sum_{n=0}x^n=\frac{1}{1-x}$$

Let $G(x)=\sum_{n=0}f(n)x^n$. The coefficient of the $x^n$ term is $f(n)$.

Multiply both sides by $x^n$:

$$f(n)x^n=2f(n-1)x^n+kx^n$$

Now, this equation holds $\forall n\ge 1, n\in\mathbb N$, so we add up all the equations that we can create by letting $n=1, n=2$, etc.

$$\begin{align} \sum_{n=1}f(n)x^n &=\sum_{n=1}2f(n-1)x^{n}+k\sum_{n=1}x^n \\ \iff G(x)-f(0) &=2xG(x)+k\left(\frac{1}{1-x}-1\right) \\ \iff G(x)&=\frac{k}{(1-x)(1-2x)}+\frac{f(0)-k}{1-2x} \end{align}$$

Let $\left[ G(x) \right]_{x^n}$ denote the coefficient of the $x^n$ term of the power series $G(x)$.

Note that we have the following facts (we'll use them):

$$\begin{align}\left[ \frac{1}{1-ax} \right]_{x^n}&=a^n \\ \left[ \frac{1}{(1-ax)(1-bx)} \right]_{x^n}&=\sum_{j=0}^{n}a^{j}b^{n-j}\end{align}$$

Thus we have:

$$\begin{align} \left[ G(x) \right]_{x^n}&=\left[ \frac{k}{(1-x)(1-2x)} \right]_{x^n}+\left[ \frac{f(0)}{1-2x} \right]_{x^n}-\left[ \frac{k}{1-2x} \right]_{x^n} \\\\ &=k\sum_{j=0}^{n}1^j2^{n-j}+f(0)\cdot 2^n-2^nk \\\\ &=k\cdot (1+2^1+2^2+2^3+\cdots+2^n)+f(0)\cdot 2^n-2^nk \\\\ &=k\cdot \frac{2^{n+1}-1}{2-1}+f(0)\cdot 2^n-2^nk \\\\ &=2^{n+1}k-k+f(0)\cdot 2^n-2^nk \\\\ &=2^n(2k-k)+f(0)\cdot 2^n-k \\\\ &=2^nk+f(0)\cdot 2^n-k \\\\ &=2^nf(0)+k(2^n-1) \end{align}$$

---

I'm adding some other formulas that might help you in the future:

$$\begin{align}\left[ \frac{1}{(1-x)^k}\right]_{x^n}&=\binom{n+k-1}{n}=\left(\binom{k}{n}\right) \\ \left[(1+x)^k\right]_{x_n}&=\binom{k}{n}\end{align}$$

Here $\left(\binom{k}{n}\right)$ denotes multiset coefficient.

---

A little note: To show how great this method is (and to give you an exercise to see if you understand the method for some practice), I can say that it can be used to find the closed formula for the $n$'th term of the Fibonacci sequence. The useful form of it is (where $F_0=0$):

$$F_n = \frac{(1 + \sqrt{5})^n - (1 - \sqrt{5})^n}{2^n \sqrt{5}}, \forall n\in\mathbb N_0$$

However, our method at first produces this different form:

$$F_n=\frac{\sum_{j=0}^{n-1}(1+\sqrt{5})^{j}(1-\sqrt{5})^{n-j-1}}{2^{n-1}}, \forall n\in\mathbb N_0$$

Using algebraic manipulations, you can change one to the other. The former formula is more useful because it helps us see the shorter formula that we can have:

$$F_n = \lfloor \frac{(1 + \sqrt{5})^n}{2^n \sqrt{5}} + \frac{1}{2} \rfloor=\lfloor \frac{\phi^n}{\sqrt{5}}+\frac{1}{2} \rfloor, \forall n\in\mathbb N_0$$

This question is about learning how to solve recurrence relations in general, so this may be useful.

Answer 2

We can write $f(n)=2f(n-1)+k$ as $$f(n)+k=2(f(n-1)+k)\iff g(n)=2g(n-1)$$ where $g(n)=f(n)+k$ is a geometric progression.

Since we have $g(n)=2^{n}g(0)=2^{n}(f(0)+k)$, we have $$f(n)=g(n)-k=2^{n}(f(0)+k)-k=2^{n}f(0)+(2^{n}-1)k.$$

Answer 3

$$f(n) = 2f(n-1) + k \\ f(n-1) = 2f(n-2) + k \\ f(n-2) = 2f(n-3) + k \\ \dots \\ f(1) = 2f(0) + k$$ $$$$ $$\Rightarrow f(n) = 2f(n-1) + k= \\ 2(2f(n-2) + k)+k= \\ 2^2f(n-2)+(2+1)k=2^2(2f(n-3) + k)+(2+1)k= \\ 2^3f(n-3)+(2^2+2+1)k= \\ \dots \overset{*}{=} \\ 2^nf(0)+(2^{n-1}+2^{n-2}+\dots +2+1)k$$

Therefore, $$f(n)=2^nf(0)+k\sum_{i=0}^{n-1}2^i= \\ 2^nf(0)+k\frac{2^n-1}{2-1}= 2^nf(0)+(2^n-1)k$$

EDIT:

$(*):$ We see that $2^3f(n-3)+(2^2+2+1)k$ is of the form $2^jf(n-j)+(2^{j-1}+2^{j-2}+\dots+2^2+2+1)k$

After some steps we have the following:

$2^nf(n-n)+(2^{n-1}+2^{n-2}+\dots+2^2+2+1)k= \\ 2^nf(0)+(2^{n-1}+2^{n-2}+\dots+2^2+2+1)k$

Answer 4

When I see something like that, I consider multiplying both sides by $2^{-n}$: $$ \overbrace{2^{-n}f(n)}^{g(n)}=\overbrace{2^{1-n}f(n-1)}^{g(n-1)}+2^{-n}k $$ Then, since $g(n)=g(n-1)+a_n\implies g(n)=g(0)+\sum\limits_{j=1}^na_j\,$, we have $$ \begin{align} \overbrace{2^{-n}f(n)}^{g(n)} &=\overbrace{f(0)}^{g(0)}+\sum_{j=1}^n2^{-j}k\\ &=f(0)+\left(1-2^{-n}\right)k \end{align} $$ Thus, multiplying both sides by $2^n$ yields $$ f(n)=2^nf(0)+\left(2^n-1\right)k $$

Answer 5

I'm not 100% sure I got what you mean, but for this sort of problems (arbitrary constants $s, t$) a difference equation is a good approach, as you immediately get rid of $t$: $$ a_k = s a_{k-1} + t\\ a_{k+1} = s a_k + t $$ now define $\Delta a_{k+1} = a_{k+1} - a_k$. You get

$$ \Delta a_{k+1} = s \Delta a_k = s^2 \Delta a_{k-2} =\ldots s^{k-1}\Delta a_1 $$ Now sum over $k$ to 'difference back', do some algebra and you get your result.