How to write recursive formula as explicit (specifically, exponential)?

Question

I recall learning in school how to convert arithmetic and geometric sequence formulas between recursive and explicit, but I don't remember learning a systematic method to approach it. For example, let $a_n=2a_{n-1}+2$ where $a_0=5$. How would I convert this to an explicit form defined in terms of $n$? Beyond this specific example, is there a generalized method to do so?

Answer 1

There is a systematic way of solving something like $a_n=2a_{n-1}+2a_{n-2}$, which is called a linear recurrence relation. For example this pdf shows you how to do it.

But for your specific example you have a constant $2$, so it's not a linear recurrence. However you can rewrite it as $a_n+2=2(a_{n-1}+2),a_0+2=7$ where it's obvious that $a_n+2=7\cdot 2^n$ so $a_n=7\cdot 2^n-2$.

For a completely general recurrence there isn't really a systematic way to convert it to a formula, but you can always try tricks like the above (linear recurrence, substitution) to see if they work.

Answer 2

It's equivalent to $\left(~\mbox{with}\ a_{0} = 5~\right)$: \begin{align} a_{n} + 2 & = 2\left(a_{n - 1} + 2\right) = 2^{2}\left(a_{n - 2} + 2\right) = 2^{3}\left(a_{n - 3} + 2\right) = \cdots = 2^{n}\left(a_{0} + 2\right) = 7 \times 2^{n} \\[5mm] \implies & \bbox[15px,border:1px solid navy]{a_{n} = 7 \times 2^{n} - 2} \end{align}

Answer 3

Leu us consider the general case of $$a_n=\alpha\, a_{n-1}+\beta$$ Let first $a_n=b_n+\gamma$ which makes $$b_n+\gamma=\alpha\,(b_{n-1}+\gamma)+\beta\implies b_n=\alpha\,b_{n-1}+(\alpha\gamma+\beta-\gamma)$$ To come back to something simple, let (assuming $\alpha\neq 1$) $$\alpha\gamma+\beta-\gamma=0 \implies \gamma=\frac \beta {1-\alpha}$$ So, we are left with $$ b_n=\alpha\,b_{n-1} \implies b_n=c \,\alpha^{n-1}\implies a_n=c\, \alpha^{n-1}+\frac \beta {1-\alpha}$$