Proof that Dana Scott Recurrance gives integers. Define the sequence {b} recursivly: b(n) := 10 * b(n-3) - 10 * b(n-6) + b(n-9). Prove, by induction that for all n, b(n) * b(n-4) - b(n-1) * b(n-3) - b(n-2) = 0 In other words, {b} is the Dana Scott recurrrance. For convienence, let phi(n) := b(n) * b(n-4) - b(n-1) * b(n-3) - b(n-2) Assume that phi(k) is 0 for k < n. Show that pni(n) = 0. This gives: phi(n-1) = b(n-1) b(n-5) - b(n-2) b(n-4) - b(n-3) = 0 phi(n-2) = b(n-2) b(n-6) - b(n-3) b(n-5) - b(n-4) = 0 phi(n-3) = b(n-3) b(n-7) - b(n-4) b(n-6) - b(n-5) = 0 phi(n-4) = b(n-4) b(n-8) - b(n-5) b(n-7) - b(n-6) = 0 phi(n-5) = b(n-5) b(n-9) - b(n-6) b(n-8) - b(n-7) = 0 phi(n-6) = b(n-6) b(n-10) - b(n-7) b(n-9) - b(n-8) = 0 phi(n-7) = b(n-7) b(n-11) - b(n-8) b(n-10) - b(n-9) = 0 phi(n-8) = b(n-8) b(n-12) - b(n-9) b(n-11) - b(n-10) = 0 phi(n-9) = b(n-9) b(n-13) - b(n-10) b(n-12) - b(n-11) = 0 phi(n-10) = b(n-10) b(n-14) - b(n-11) b(n-13) - b(n-12) = 0 ... Now, compute phi(n). phi(n) = b(n) * b(n-4) - b(n-1) * b(n-3) - b(n-2) Substitute for b(n) and b(n-1) from the definition of {b}. b(n) = 10 * b(n-3) - 10 * b(n-6) + b(n-9) b(n-1) = 10 * b(n-4) - 10 * b(n-7) + b(n-10) phi(n) = ( 10 * b(n-3) - 10 * b(n-6) + b(n-9) ) * b(n-4) - ( 10 * b(n-4) - 10 * b(n-7) + b(n-10) ) * b(n-3) - ( 10 * b(n-5) - 10 * b(n-8) + b(n-11) ) Simplify: phi(n) = 10 b(n - 3) b(n - 7) - 10 b(n - 4) b(n - 6) - 10 b(n - 5) + b(n - 4) b(n - 9) - b(n - 3) b(n - 10) + 10 b(n - 8) - b(n - 11) Since phi(n-3)=0, phi(n) = b(n - 4) b(n - 9) - b(n - 3) b(n - 10) + 10 b(n - 8) - b(n - 11) Substitute for b(n-3) and b(n-4) from the definition of {b}. b(n-3) = 10 * b(n-6) - 10 * b(n-9) + b(n-12) b(n-4) = 10 * b(n-7) - 10 * b(n-10) + b(n-13) phi(n) = (10 * b(n-7) - 10 * b(n-10) + b(n-13) ) * b(n - 9) - (10 * b(n-6) - 10 * b(n-9) + b(n-12) ) *b(n - 10) + 10 * b(n - 8) - b(n - 11) ; Simplify: phi(n) = - 10 b(n - 10) * b(n - 6) + 10 b(n - 9) * b(n - 7) + 10 b(n - 8) + b(n - 9) * b(n - 13) - b(n - 10) * b(n - 12) - b(n - 11) phi(n) = - 10 * ( + b(n - 10) * b(n - 6) - b(n - 9) * b(n - 7) - b(n - 8) ) + b(n - 9) * b(n - 13) - b(n - 10) * b(n - 12) - b(n - 11) Since phi(n-6) = phi(n-9) = 0 b(n-6) b(n-10) - b(n-7) b(n-9) - b(n-8) = 0 b(n-9) b(n-13) - b(n-10) b(n-12) - b(n-11) = 0 phi(n) = 0 QED. ###################################################################### By the way, this also proves Laurentness. The above proof implicitly relies on the fact that for {a} and {b} defined as a(n) = ( a(n-1) * a(n-3) + a(n-2) ) / a(n-4) b(n) = 10 * b(n-3) - 10 * b(n-6) + b(n-9) the first 9 terms of the sequences are equal. In the proof of integrality, we choose the first nine terms of {b} to be (1, 1, 1, 1, 2, 3, 5, 13, 22). If we instead choose the first nine terms of {b} to correspond to the Laurent version of a, a := proc(n) if n = 1 then w elif n = 2 then x elif n = 3 then y elif n = 4 then z else simplify((a(n - 1)*a(n - 3) + a(n - 2))/a(n - 4)) end if end proc: interface(prettyprint=false); seq(a(n),n=1..9); (w, x, y, z, (z*x+y)/w, (y*z*x+y^2+z*w)/w/x, (y*z^2*x+z*y^2+z^2*w+z*x^2+x*y)/w/x/y, (y*z^3*x^2+2*y^2*z^2*x+z*y^3+z^3*w*x+z^2*w*y+z^2*x^3+2*z*x^2*y+x*y^2 +w*y^2*z*x+w*y^3+w^2*y*z)/w^2/x/y/z, (y*z^2*x^3+x^2*y^2*z^3+x^2*z^2*w+2*x^2*z*y^2+x^2*z*w^2+2*x*w*y*z^3 +2*x*z^2*y^3+x*z^2*w^2*y+x*z*w*y^3+x*z*w*y+x*y^3+w^2*z^3+z^2*w^3 +2*z^2*y^2*w+z*y^4+2*z*w^2*y^2+w*y^4)/x^2/y/z/w^2), then it is clear from the linear nature of {b} that all b(n) will be a Laurent polynomial.