1
$\begingroup$

I'm wondering if there's any general strategies to develop an explicit formula for the nth term when you're given a recurrence relation.

For example, I'm given a recurrence relation: $a_{n+1}=2a_n+1$ where $a_0=0$ and I'm asked to find the first 5 terms, then find an explicit formula for the nth term.

So I found the first 5 terms to be $\{0, 1, 3, 7, 15\}$ but I can't figure out how to write the explicit formula where $a_0$ will be $0$.

The book I'm using does not go into detail about this, so I'm wondering if there's any sort of procedure to follow to find the explicit formula. I've done a few of these and sometimes I can figure them out by guessing and checking but it feels like there should be a better way.

$\endgroup$
  • $\begingroup$ There is no general method. Concrete Mathematics by Graham et al discusses some techniques. $\endgroup$ – MJD Mar 30 '14 at 0:34
  • $\begingroup$ I would guess something like $a_n=b2^n-a$, so that $a_{n+1}=2(b2^n-a)+1=b2^{n+1}+(1-2a)$. Then $1-2a=a$, from which we get $a=1/3$. To solve for $b$, we use the initial condition $a_0=0$ to get $0=b-1/3$, so that $b=1/3$. Thus, the solution is $a_n=\frac{2^n-1}{3}$. As MJD points out, there is not general method: guessing is probably the best shot you have in general. However, there are certain kind of recurrence relations that do have a general method for solving (like the 'fibonacci-like' recurrence relations $a_{n+2}=ba_{n+1}+ca_{n}$) $\endgroup$ – Hayden Mar 30 '14 at 0:37
  • $\begingroup$ @sabien There's an algorithm to find the closed formula for homogeneous recurrence relations. $\endgroup$ – Git Gud Mar 30 '14 at 0:38
  • $\begingroup$ @GitGud What's the algorithm? $\endgroup$ – user122283 Mar 30 '14 at 0:40
  • $\begingroup$ @SanathDevalapurkar Page 5 here for an example. $\endgroup$ – Git Gud Mar 30 '14 at 0:43
2
$\begingroup$

Since you have a first order recurrence relation (i.e. only two succesive terms $a_n$ and $a_{n+1}$ are involved) you can solve the recurrence relation by getting from $a_{n+1}$ back to $a_0$ as follows $$\begin{align*}a_{n+1}=2a_n+1&=2^1(2a_{n-1}+1)+1=2^2a_{n-1}+(1+2)=\\\\&=2^2(2a_{n-2}+1)+3=2^3a_{n-2}+(1+2+2^2)=\\\\&=2^3(2a_{n-3}+1)+7=2^4a_{n-3}+(1+2+2^2+2^3)=\\\\&=\ldots (\text{guess the solution, by generalizing the above sequence}) \\\\&=2^{n+1}a_0+\sum_{k=0}^{n}2^k\end{align*}$$ and since $a_0=0$ we have that $$a_{n+1}=2^{n+1}\cdot0+\frac{1-2^{n+1}}{1-2}=2^{n+1}-1$$ where we also used the formula for the finite geometric series. This gives the explicit formula for the given reccurence relation which is $$a_n=2^n-1$$


Note that this method works only in a special cases where the relation is rather simple. For general methods, look at the links provided in the comments.

$\endgroup$
  • $\begingroup$ I'm just a bit confused - is the final explicit formula above just $2^{n+1}-1$? I might be missing something, but it looks like this formula is not the same formula that describes the recurrence relation. If you plug 0 in here for n, you get 1, and when you plug 1 in, you get 3. The original recurrence produced 0, 1, 3, 7, 15 for the first 5 terms, but this formula would produce 1, 3, 7, 15, and 31 for the same n inputs (so it's off by one term). $\endgroup$ – Sabien Mar 30 '14 at 1:31
  • $\begingroup$ @Sabien We both say the same, I just have $n+1$ instead of $n$, that is why the difference. Just write $a_n=2^n-1$ and you will have it. I am editing it anyway $\endgroup$ – Jimmy R. Mar 30 '14 at 1:34
2
$\begingroup$

It depends a lot on the exact form of the recurrence. Some types (linear recurrences with constant coefficients; linear recurrences of the first order; Ricatti recurrences (of the form $w_{n + 1} = (a w_n + b) / (c w_n + d)$ with $c \ne 0$ and $a d - b c \ne 0$) can be solved exactly, and thus there is a formula for the $n$-th term (typically a mess, though).

Most recurrences don't have "decent" solutions. If you are only interested in the first few terms, just use the recurrence to compute them. Often it is possible to extract (sometimes surprisingly accurate) asymptotic formulas, see e.g. Sedgewick and Flajolet "And Introduction to the Analysis of Algorithms" (Addison-Wesley, 2nd edition, 2013). The companion webpage to the book has most of the material.

$\endgroup$
1
$\begingroup$

If I may, let us consider the more general case of the recurrence relation $$a_{n+1}=p \text { }a_n+q$$ where $a_0=r$.

There is a very particular case of less than minor interest corresponding to $p=1$; for such a case, you would very simply show that $a_n=q \text { }n+r$.

For the case where $a_0=0$ just as in your problem, a approach identical to the one proposed by Stefanos will lead to $$a_n=\frac{q \left(p^n-1\right)}{p-1}$$ Now, for the most general case with $p \neq 1$, a similar treatment would lead to $$a_n=\frac{p^n ((p-1) r+q)-q}{p-1}$$

$\endgroup$
  • $\begingroup$ Is there another way to modify this if $a_n$ is raised to a power? Like if you had $a_{n+1}=pa_n^2+q$? $\endgroup$ – Sabien Mar 30 '14 at 5:54
  • $\begingroup$ I have not been able to find anything for this case. $\endgroup$ – Claude Leibovici Mar 30 '14 at 6:06

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.