Example $2\mathrm{.}4\mathrm{.}1$

Find a recurrence relation and initial conditions for $1,5,17,53,161,485$dots.

Solution. Finding the recurrence relation would be easier if we had some context for the problem $($like the Tower of Hanoi, for example$).$ Alas, we have only the sequence. Remember, the recurrence relation tells you how to get from previous terms to future terms. What is going on here? We could look at the differences between terms: $4,12,36,108,$dots. Notice that these are growing by a factor of $3.$ Is the original sequence as well? $1*3=3,5*3=15,17*3=51$ and so on$.$ It appears that we always end up with $2$ less than the next term. Aha!

So $a_n=3a_{n-1}+2$ is our recurrence relation and the initial condition is $a_0=1.$