How to find this recurrence relation,

Question

The problem statement is:

Consider the following two infinite sequences:

1,2,4,...

and

1,3,9,...

Given that the sequences satisfy the same linear three-term recurrence relation, find that relation. Write the general term in the sequence generated by this same recurrence relation, whose first two terms are 1,1,....

Any tips or solutions are welcome -- I'm not sure how to even get started on this problem. This is an old exam question on advanced calculus, not homework.

Thanks,

Answer 1

Suppose $a_{n+1}=xa_n+ya_{n-1}$

Then $4=2x+y$ and $9=3x+y$ $\implies$ $x=5,y=-6$

Hence $a_{n+1}=5a_n-6a_{n-1}$, whose general term is $a_n=p2^n+q3^n$

When $a_1=a_2=1$, $2p+3q=1$ and $4p+9q=1$, Hence $p=1 ,q=-{1\over 3}$