Question

This may be completely unfair to ask you guys to try to solve... but I'm bored. See if you can find a recurrence relation for the following sequence: 4,7,2,20,31,73,155,332,715,... Let me know if you need a hint.

Answer 1

Now that I think of it I think there is a hint in the sequence in itself to see how many terms you will need for the recurrence relation. There is another thing I can mention think constant coefficients only for the terms of the recurrence relation.

Answer 2

yeah im working on it, please don't give more hints :)

Answer 3

k

Answer 4

\[a_n = a_{n-1}+2a_{n-2} + a_{n-3}\]

Answer 5

Awesome!
Now do you think that question would still be solvable if I didn't say constant coefficients?

Answer 6

I have used both your hints... so im not sure if we can solve it w/o knowing that the recurrence relation is lienar

http://www.wolframalpha.com/input/?i=solve+20+%3D+2x+%2B+7y+%2B+4z,+31+%3D+20x%2B2y%2B7z,+73+%3D+31x%2B20y%2B2z

Answer 7

that is just algebra... do you have any other neat methods ?

Answer 8

no I was just bored and wanted to come up with a hard sequence for people to find a recurrence relation or explicit relation
but then I decided I might not be giving enough info because I asked myself how would I solve that without knowing there was constant coefficients... though it does look like the first 3 terms are the initial numbers that generate the sequence because there is only increase after the third term
So the only thing I might be able to come up with is:
\[A(n)f_n=B(n)f_{n-1}+C(n)f_{n-2}+D(n)f_{n-3}\]
and somehow try to figure out A,B,C,D are constants...
But I guess it could also be like this instead:
\[A(n)f_n=B(n)f_{n-1}+C(n)f_{n-2}+D(n)f_{n-3}+E(n)\]

Answer 9

but anyways awesome work @rsadhvika

Answer 10

Ahh right, the sequence is increasing after 2.. so this is a big hint for guessing the order !

wolfram gives this as power series
http://www.wolframalpha.com/input/?i=power+series+(13x%5E2-3x-4)%2F(x%5E3%2B2x%5E2%2Bx-1)

im just gonna find the generating function with the previous recurrence relation and see if it matches with wolfram

Answer 11

i don't have pen and paper nearby... but im pretty sure they both will match..

Answer 12

it does look like those coefficients in that wolfram link or matching the terms of the sequence