Find $n$th Term of the Sequence $1,2,3,8,13,30,55,\cdots$

Question

Find $n$th Term of the Sequence $1,2,3,8,13,30,55,\dotsc$

Source: Higher Algebra by Bernald and Child

I tried using Successive differences which are $1,1,5,5,17,25,\dotsc$ wherein I do not see any pattern.

Answer 1

The numbers seem to obey the recurence relation $$a_n=3a_{n-2}+2a_{n-3} \qquad \text{with}\qquad a_0=0, \quad a_1=1, \quad a_2=2$$ If this is the case, the characteristic equation is $r^3=2r+3$ the roots of which being $(-1,-1,2)$ making the general solution to be $$a_n=c_1(-1)^n+c_2(-1)^n n+c_3 2^n$$ Using $(a_0,a_1,a_2)$, just compute $(c_1,c_2,c_3)$.

Answer 2

Hint:

The pairwise sums are

$$3,5,11,21,43,85\cdots$$ which are the thirds of

$$9,15,33,63,129,255\cdots=8+1,15-1,32+1,64-1,128+1,256-1,\cdots$$

Hence

$$s_n=\frac{2^{n+2}-(-1)^n}3.$$