Strategies for developing explicit formulas for nth term given recurrence relation?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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