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.
Best Answer
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.