Why can any polynomial and exponential be represented as a recurrence?
The general form for a polynomial is $a_n = \sum_{i=0}^k c_i n^i$. Thus, for $n&gt;0$, we have
$$a_n - a_{n-1} = \sum_{i=0}^k c_i n^i - \sum_{i=0}^k c_i (n-1)^i,$$
which can be transformed into the recurrence
$$a_n = a_{n-1} + \sum_{i=0}^k c_i n^i - \sum_{i=0}^k c_i (n-1)^i,~~~ a_0 = c_0.$$

For exponentials, the general form is $a_n = c\cdot b^n$. In complete analogy to the example in the book, this is generated by the recurrence
$$a_n = b\cdot a_{n-1},~~~ a_0 = c.$$