12
$\begingroup$

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.

$\endgroup$
3
  • 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, 2014 at 11:15
  • $\begingroup$ en.wikipedia.org/wiki/Arithmetico-geometric_sequence $\endgroup$
    – user5402
    Aug 25, 2014 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$ Aug 25, 2014 at 17:59

5 Answers 5

11
$\begingroup$

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.

$\endgroup$
1
5
$\begingroup$

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

$\endgroup$
4
  • $\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$ Aug 25, 2014 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, 2014 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$ Aug 25, 2014 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, 2014 at 18:03
4
$\begingroup$

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

$\endgroup$
3
  • 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$ Aug 25, 2014 at 11:25
  • $\begingroup$ I added some more information at my answer.. $\endgroup$
    – Mary Star
    Aug 25, 2014 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$ Aug 25, 2014 at 11:34
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .