Conference rusure::math

281.0. "Integer-Producing Polynomials" by R2ME2::GILBERT () Wed May 08 1985 22:30

Theorem:
Any integer-producing polynomial P(x) of degree <= d can be expressed
in the form:

	       d
               --      x
	P(x) = \  a  (   ), for some integers a .
               /   j   j                       j
               --
	      j=0

Proof.
Trivially true for d=0.  Assume true for d-1.  Now, P'(x) = P(x+1) - P(x)
is an integer-producing polynomial of degree <= d-1.  So P'(x) satifies the
theorem.  But,

	              x-1               x-1 d-1
                      --                --  --      i
	P(x) = P(0) + \  P'(i) = P(0) + \   \  a  (   )
                      /                 /   /   j   j
                      --                --  --
	             i=0                i=0 j=0

                      d-1 x-1                  d-1
                      --   --      i            --      x
 	     = P(0) + \    \  a  (   ) = P(0) + \  a  (   )
                      /    /   j   j            /   j  j+1
                      --   --                   --
                     j=0  i=0                  j=0

                d
                --        x
 	     =  \   a   (   ) , with a  = P(0).
                /    i-1  i           -1
                --
               i=0

	Which completes the induction.

For this, and other neat results, see
Polya und Szego, Problems and Theorems in Analysis, volume II,
part 8, chapter 2 - Polynomials with Integral Coefficients
and Integral-Valued Functions.