Prove that if P is a polynomial of degree k, and P(n) assumes integral values for k+1 consecutive integers...

In article <1993Sep3.162412.3242@msc7.comlab.ox.ac.uk> imc@comlab.ox.ac.uk
(Ian Collier) writes:
>No-one has posted an answer to that exercise, and I'd quite like to see
>one.  :-)

I would use mathematical induction, but it would have to be used
k times, k-1 times to show that the kth power of integer (n+1) is
integer, and the last time to show the above.

ie...

    for ( if (int n)^2 is an int, then so (n+1)^2.. for all n => 1

    I)  1^2 = 1*1 = 1 = int
    II) for j+1....(j+1)^2  = (j+1)(j+1) = j*j + 2*j + 1*1
            = j*j + (j + j) + 1

    and if  (int + int == int) is assumed, then the above must be an
    int, and therefore QED.

    Repeat ad nauseam :)

-- Mike Neylon <smneylon@lerc.nasa.gov>

[ Editor: this shows that powers of integers are integers; it does not
use the hypothesis, since a polynomial with non-integer coefficients,
such as n(n+1)/2, also takes integer values. ]

Ian Collier had also written:
>My guess is that if you tried to solve for a0, a1, ..., ak in
>
> /  1     1       1    ...\  |a0|   | 1 |
>|   x   (x+1)   (x+2)  ... | |a1| = | y |
>|  x^2 (x+1)^2 (x+2)^2 ... | |a2|   |y^2|
> \  :     :       :    `. /  |: |   | : |
>
>for any x, y and k you would get integers, and that would lead to an
>easy proof of the above.  However, this seems hard to prove (and
>there's no real guarantee that it's true).

The easiest way I can see to prove the stated problem is by forming the
difference table:

P(n)
        Q(n) = P(n+1) - P(n)
P(n+1)          R(n) = Q(n+1) - Q(n)
        Q(n) = P(n+2) - P(n+1)          S(n) = R(n+1) - R(n)
P(n+2)          R(n+1) = Q(n+2) - Q(n+1)
        Q(n) = P(n+3) - P(n+2)
P(n+3)

etc.

It will be composed only of integers.  By realizing that the k+1st
difference is zero, the difference table can be extended forward or
backward to any desired integer, and will still be filled only with
integers, including the first column.  QED.

-- Dave Dodson <dodson@convex.COM>

[ Editor: in the table, the second and third "Q(n)" stand for Q(n+1)
and Q(n+2), as their right-hand sides show. ]

Induction to k: take a polynomial of degree k-1, which takes the right
value in the first k integers.  Suppose the error in the k+1 th integer
is m.  Than add m times the polynomial that assumes the values
0,0,0,...,1 in the consecutive integers.

So you only need to prove it for polynomials:
(x+n)*(x+n+1)*..*(x+n+k)/(1*2*..*(k+1)).  The values these polynomials
take are binomials x+n+k over k+1, hence integers.  QED

-- Mark van Hoeij <hoeij@sci.kun.nl>