How can I learn about rewriting recursive functions into linear ones?

Question

I'm trying to learn about converting recursive functions into linear ones. For instance

$a_n = b a_{n-1} + c$

I converted to

$a_n = (a + \frac{c}{b-1})b^n - \frac{c}{b-1}$

But I have no clue why it works. Is there any place where I can see the operations that can be applied to recursive functions?

Answer 1

If we consider the following sequence defined by recursion : $\left\{ \begin{array}{ll} a_0 & = a\\ a_{n} & = ba_{n-1} + c \end{array} \right.$

Then by running some recursion steps, as did @peterwhy, we obtain: \begin{eqnarray} a_n &=& ba_{n-1} + c \nonumber\\ &=&b(ba_{n-2}+c)+c = b²a_{n-2}+bc+c\nonumber\\ a_n&=&b(b(a_{n-3}+c)+c = b³a_{n-3}+b²c+bc+c\nonumber\\ \end{eqnarray} After $n$ iterations we have : $a_n = b^na_0+b^{n-1}c + ... + bc +c$ (remark the pattern) for $n>0$.

Then \begin{eqnarray} a_n &=& b^na_0 + c(1+b+b²+...+b^{n-1}) \end{eqnarray} Now we have two cases :

1. $b = 1$, then $1+b+b²+...+b^{n-1} = 1+1+...+1 = n$, so $a_n = a_0+nc$ (you recognize an arithmetic sequence).
2. $b \neq 1$, then $1+b+b²+...+b^{n-1} = \frac{1-b^{n}}{1-b}$, so $a_n = b^na_0 + c\frac{1-b^{n}}{1-b} = (a_0 + \frac{c}{b-1})b^n-\frac{c}{b-1}$ as you found.

Note : if you're solving recurrences look at Concrete Mathematics as suggested @MJD.