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 $$


  • 3
    $\begingroup$ 'straightforward, formal way to deduce the closed form from the recursive definition in the first place': 1) difference equations, 2) generating functions $\endgroup$ – Alex Aug 25 '14 at 11:15
  • $\begingroup$ en.wikipedia.org/wiki/Arithmetico-geometric_sequence $\endgroup$ – user5402 Aug 25 '14 at 13:16
  • 3
    $\begingroup$ It is a fact of life that some very strange looking differential equations $y'=f(t,y)$ have a "closed form solution" (which can be found in a systematic way), whereas relatively simple recursive equations $y_{n+1}=f(n,y_n)$ don't. $\endgroup$ – Christian Blatter Aug 25 '14 at 17:59

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$:


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.


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.$$

  • $\begingroup$ Thanks, but I'm not actually fully satisfied with getting from g(n) = 2*g(n-1) to g(n) = 2^n * g(0). Yes, it's obviously true, but I'm wondering if there could be more rigorous steps between those two points? $\endgroup$ – user3391564 Aug 25 '14 at 11:32
  • $\begingroup$ You mean you are not satisfied with the following? $$g(n)=2g(n-1)=2^2g(n-2)=2^3g(n-3)=\cdots=2^{n-1}g(1)=2^ng(0).$$ $\endgroup$ – mathlove Aug 25 '14 at 11:34
  • 1
    $\begingroup$ Exactly. I know it seems stupid but I'm strangely unsatisfied by "= ... =". It just feels like it's relying too heavily on seeing a pattern in the notation visually, rather than mathematical formalisms. Know what I mean? $\endgroup$ – user3391564 Aug 25 '14 at 11:38
  • 1
    $\begingroup$ @user3391564 Well, this is just a trivial formula for the $n$'th term of a geometric progression with the quotient $2$ (and mathlove said it that $g(n)$ is indeed a geometric progression). $\endgroup$ – user26486 Aug 25 '14 at 18:03

$$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$$


$(*):$ 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$

  • 2
    $\begingroup$ Thanks. This makes sense to me and was much like what I referred to as my informal examination. The part I'm not satisfied with is the "...=". Yes, it's clearly correct intuitively but I'm wondering if it could be a bit more rigorous than "...="? $\endgroup$ – user3391564 Aug 25 '14 at 11:25
  • $\begingroup$ I added some more information at my answer.. $\endgroup$ – Mary Star Aug 25 '14 at 11:31
  • 2
    $\begingroup$ I totally agree with that line of reasoning, but it's just bothering me that "we see that ... is of the form ... " isn't rigorous enough. $\endgroup$ – user3391564 Aug 25 '14 at 11:34

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.


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 $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.