How would you find the $n$th term of a sequence like this?
$1, 2, 5, 10, 13, 26, 29, …$
I see the sequence has a group of three terms it repeats: Double first term to get second term, add three to get third term, repeat.
What about: $2, 3, 6, 7, 14, 15, 30,… $?
Again the sequence has a group of three terms it repeats: Add one to first term to get second term, then double second term to get third term.
How do you compute the $n$th term of such sequences directly, without iterating through all preceding terms?
Best Answer
For example, consider the 1st sequence. One can write two recurrence relations, $$F_{2k}=2F_{2k-1},\qquad F_{2k+1}=F_{2k}+3,$$ and use them to deduce a relation involving only odd terms: $$F_{2k+1}=2F_{2k-1}+3.$$ The general solution of this is $$F_{2k+1}=\alpha\cdot 2^k-3,$$ and the value of the constant $\alpha=2$ is fixed by $F_1=1$. Hence $$F_{2k+1}=2^{k+2}-3,\qquad F_{2k}=2^{k+2}-6.$$