Is it solvable to ask to find a recurrence relation for the following sequence 4,7,2,20,31,73,155,332,715,... ? Is it solvable to ask to find a recurrence relation for the following sequence 4,7,2,20,31,73,155,332,715,...  without any other information? If not, what would be the very least amount of information for me to give someone for them to arrive at $f_n=f_{n-1}+2f_{n-2}+f_{n-3}$?
 A: If you tell them the numbers satisfy a third order linear homogeneous recurrence that is certainly enough.  They can then write $f_n=af_{n-1}+bf_{n-2}+cf_{n-3}$ and solve three simultaneous equations to find $a,b,c$.  You have given three more values than required for that, so you could tell them it is a sixth order recurrence and expect them to find that the top three terms are zero.
A: This is a mechanical technique for detecting linear recurrences without knowing the degree ahead of time. It is about pages 86,87 of The Book of Numbers by Conway and Guy. I do not have the book, so I got it from a book review. They call the technique the Number Wall. The nice part is that, if the sequence is integers, the entries remain integers. For a wall made up of bricks, for each little cross of five bricks, 
$$
\begin{array}{rrr}
  & N & \\
  W & C & E \\
  & S & \\
\end{array}
$$
we calculate the new $S$ value by the requirement
$$ NS + WE = C^2.  $$ We start at the top with a row of ones, the next row is the unknown sequence. We continue top down. The rule says
$$ S = (C^2 - WE)/ N $$
$$
\begin{array}{rrrrrrrrr}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
4 & 7 & 2 & 20 & 31 & 73 & 155 & 332 & 715 \\
 & 41 & -136 & 338 & -499 & 524 & -211 & -601 &  \\
 &  & 2319 & 2319 & 2319 & 2319 & 2319 &  &  \\
 &  &  & 0 & 0 & 0 &  &  &  \\
\end{array}
$$
The rule says that the number of rows to get from the unknown sequence to a row of $0'$s is the degree of the recurrence. If that happens, you should recover the constant coefficients (linear algebra) and try to prove that it works, or maybe prove that it was a coincidence and there is no nice recurrence. You have degree three. Evidently there is also detail in A Handbook of Integer Sequences by Neil Sloane. In particular, extra rules are needed when the wall contains a little  square of zeroes, which they call a "window." 

A: How about setting up the problen like this?
$$f_{n-3}=\frac{1}{2}(f_{n}-f_{n-1}-f_{n-2})$$
Where you replace the $f_{n}$'s with variables. 
I think it's enough of a hint and shows the key inductive step needed to solve the problem but still requires you to see the relationship of the recurrance for yourself?
