Answer: No.
Proof:
Lemma 1: 2007 = 223 * 3^2 (trivial)
Lemma 2: x(n) = 2^n * (n^2 + 1) (letting x(0) = 1, x(1) = 4 and x(2) = 20)
Proof: Induction over n.
For n = 3: n(3) = 6 * 20 - 12 * 4 + 8 = 80 = 2^3 * (3^2 + 1)
For n > 3: assume x(n) = 2^n * (n^2 + 1) and similarly for x(n-1) and x(n-2).
then x(n+1) = 6 * 2^n * (n^2 + 1) - 12 / 2 * 2^n * (n^2 - 2n + 2) +
8 / 4 * 2^n * (n^2 - 4n + 5)
= 2^n * ( (6 - 6 + 2) n^2 + (-6*-2 + 2*-4) n + (6 - 6*2 + 2*5) )
= 2^n * 2 * (n^2 + 2n + 1 + 1)
= 2^(n+1) * ( (n+1)^2 + 1)
Thus, formula holds for all n >= 3, q.e.d.
Serious business observation: neither 3 nor 223 (both odd) are going to divide 2^n
(which is always even) given any n, same applies the other way around.
Thus it remains to show that neither 3 not 223 divide n^2+1, the other factor of x(n).
That is equailent to showing that
For all n, n^2 != 2 (mod 3) and n^2 != 222 (mod 223)
or in other words, that 2 and 222 are not quadratic residues modulo 3 and 223 respectively.
Using Euler's criterion (for those _really_ interested in the proof, look it up in Wikipedia) we decide:
2^((3-1)/2) = 2^1 = 2 = -1 (mod 3) meaning that 2 is _not_ a quadratic residue modulo 3
and
222^((223-1)/2) = 222^111 = 222 = -1 (mod 223) meaning that, indeed, 222 is not a quadratic residue modulo 223
concluding the proof. Thank YOU for reading this far. Looks like that makes two of us (not having life...)
Yours, sigs
