# How to find this recurrence relation,

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,

• Why delete what you said you were going to try? – Mike Oct 9 '15 at 5:11
• Hi @Mike, my sketch on paper looked so silly that I didn't think it was even close to being on the right track... – User001 Oct 9 '15 at 5:13
• Hi @Mike, I'm working off of the first line of the below answer (I did not read any more of it), and now I think I will continue with the matrix equation idea. It may actually work, I think... – User001 Oct 9 '15 at 5:42
• Hi @Mike - it worked :-). I had given up too soon, thinking perhaps I needed a calculus approach when in fact linear algebra was perfectly fine to solve for the coefficients. However, I'm not sure how to derive the general term in the sequence that starts with 1,1, ... although I can of course compute the terms explicitly now. But I see no obvious patterns to the numbers being generated... – User001 Oct 9 '15 at 6:08

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}$
• Hi @cr001, I was able to arrive at x = 5, y=-6, too. Can you please elaborate on how you wrote the general term as $p2^n + q3^n$? I don't see how to derive that. Thanks, – User001 Oct 9 '15 at 6:06
• The general formula comes from solving the quadratic equation $x^2=5x-6$. For why this is the case see my explanation here math.stackexchange.com/questions/1469960/… . – cr001 Oct 9 '15 at 6:09