Dickfore said:
To justify my solution with more than just "looking at the stars", I will offer this reasoning.
A linear homogeneous recursion of order p:
<br />
x_{n + p} + c_{1} \, x_{n + p -1} + \ldots + c_{p - 1} \, x_{n + 1} + c_{p} \, x_{n} = 0<br />
has a particular solution of the form: ...
Good solution dickfore. You can also get that result from simple linear algebra.
First let's check if there are any recurrence solutions length 2. (using MATLAB syntax)
1. Set up the matrix M = [3,8,18; 8,18,30; 18,30,70];
2. Row reduce. R = rref(M).
Which in this case returns R = [1 0 0 ; 0 1 0 ; 0 0 1].
This is three equations in two unknowns, so unless R has a full zero row there will be no solutions. In this case R is the identity matrix so there is no solution.
Now let's check for length three solutions
1. Set up the matrix M = [3,8,18,30; 8,18,30,70];
2. Row reduce. R = rref(M).
Which in this case returns R = [1 0 -8.4 2; 0 1 5.4 3].
This time we have two eqns in three unknowns, so there will either be zero solutions or an infinite number of solutions. In this particular case it does have solutions as follows,
(a_0, a_1, a_2) = (2 + \frac{42t}{5}, \, 3 - \frac{27t}{5}, \, t)
So there are an infinite number of length three recurrence relations (one for each value of "t") of the form :
x_{k+3} = a_0 \, x_k + a_1 \, x_{k+1} + a_2 \, x_{k+2}