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.

Can anyone tell me how do we establish a formula from a given recurrence relation? Take the example of $f(n) = 2f(n-1) + 1$, $n \in \mathbb{Z^+}$, $f(1) = 1$

When I write out the first few values, it turns out the formula for $n$th term is $2^n-1$, but how do we get at this? I suppose that this method of observation won't work for harder ones, like $f(n) = -4f(n-1) + 3$, $n \in \mathbb{Z^+}$, $f(1) = 1$

I know methods of Lagrange interpolation and finite differences, but they won't work here, since the formula is exponential (finite difference table looks very interesting though).

share|improve this question
    
This will help. –  Git Gud Mar 17 '13 at 13:57
    
A related problem. –  Mhenni Benghorbal Mar 17 '13 at 14:00

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
With the help of your excellent response, I managed to write a general form of $f(n)$, ie $f(n) = (y + \frac{b}{a-1}) \cdot a^{n-x} - \frac{b}{a-1}$ given $f(x) = y$ (base condition) and $f(n) = a\cdot f(n-1) + b$. In the case of the given problem, $f(n) = (1 + \frac{3}{-4-1}) \cdot (-4)^{n-1} - \frac{3}{-4-1}$ which simplifies to $f(n) = \frac{2}{5} \cdot (-4)^{n-1} + \frac{3}{5}$. Thanks a lot for your help. –  xylon97 Mar 18 '13 at 12:37
    
@hkapur97: You’re very welcome. –  Brian M. Scott Mar 18 '13 at 14:53

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.