Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
'straightforward, formal way to deduce the closed form from the recursive definition in the first place': 1) difference equations, 2) generating functions –  Alex Aug 25 at 11:15
    
3  
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. –  Christian Blatter Aug 25 at 17:59

5 Answers 5

up vote 10 down vote accepted

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 out in the future:

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


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

share|improve this answer
    
actually, both of the last two identities are the generalized binomial theorem. –  robjohn Aug 25 at 20:21

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

share|improve this answer
    
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? –  user3391564 Aug 25 at 11:32
    
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).$$ –  mathlove Aug 25 at 11:34
1  
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? –  user3391564 Aug 25 at 11:38
1  
@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). –  mathh Aug 25 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$$

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$

share|improve this answer
2  
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 "...="? –  user3391564 Aug 25 at 11:25
    
I added some more information at my answer.. –  Mary Star Aug 25 at 11:31
2  
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. –  user3391564 Aug 25 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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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