Summations and Recurrences

Consider the sum

                          N       (2N+k)!
            S(N)  =     SUM   ----------------
                         k=0  (2N-2k)! (1+3k)!

For example, we have

       S(1) = 5/4         S(2) = 51/14        S(3) = 277/20

and so on.  Is S(n) ever an integer for any positive integer n?
The answer is yes, but the first occurrence of an integer in this 
sequence is S(2755452), which is an integer having just over 2 
million digits.  This is related to the fact that n=6*2755452+2
is the smallest pseudoprime of the form 6N+2 relative to the
cubic polynomial x^3 - x - 1.

For any integers m,n with m greater than or equal to n, define 

             F(m,n) = 2C(m,n) + C(m-1,n-1)

where C(m,n) = m!/(n!(m-n)!) is the binomial coefficient.  We
also define F(m,n)=0 if m < n or n < 0.  Since the F coefficients 
are just a linear function of the binomial coefficients they clearly 
satisfy the same recurrence, i.e.,

          F(m,n)  =  F(m-1,n)  +  F(m-1,n-1)              (1)

Now, for any non-negative integer N, define

  S(2N) = SUM  F(N-k,2k)       S(2N+1) = SUM   F(N-k,2k+1)
         k > =0                         k > =0

It follows that for any integer q > 2 we have the recurrence

              S(q) = S(q-2) + S(q-3)

To prove this, first consider the case where q is odd.  In
that case we can put q=2N+1 and the recurrence can be written
as
           S(2N+1) = S(2(N-1)+1) + S(2(N-2))

By the definitions of S(2N) and S(2N+1) this relation is

 SUM  F(N-k,2k+1)  =  SUM  F(N-1-k,2k+1)  +  SUM  F(N-1-k,2k)
k > =0               k > =0                 k > =0

which follows immediately from (1) for each k.  On the other hand,
if q is even, we can put q=2N and the recurrence can be written
as
           S(2N) = S(2(N-1)) + S(2(N-2)+1)

which by definition is

 SUM  F(N-k,2k)  =  SUM  F(N-1-k,2k)  +  SUM  F(N-2-k,2k+1)
k > =0             k > =0               k > =0

By a shift of index the last sum can be written as

       SUM  F(N-2-k,2k+1)  =  SUM  F(N-1-k,2k-1)
      k > =0                 k > =1

and since F(N-1,-1)=0 the summation can be carried over k > = 0,
so again we can apply relation (1) for each k to give the result.

We now consider the values of S(6N+2) for any positive integer
N.  By definition we have

                                N
      S(6N+2) = S(2(3N+1)) =  SUM  F(3N+1-k,2k)
                               k=0

Also, from the definition of F(m,n) we have

                 2 (m!)          (m-1)!
      F(m,n) =  ---------  +  -------------
                n! (m-n)!     (n-1)! (m-n)!


                 2 (m!)       n     m!
             =  ---------  +  -  ----------
                n! (m-n)!     m   n! (m-n)!


                                               (m-1)!
             =  (2 + n/m) C(m,n)   =   (2m+n) --------
                                              n!(m-n)!

Therefore we have

               N                       [(3N+1-k)-1]!
  S(6N+2) =  SUM  [2(3N+1-k)+(2k)] ---------------------
              k=0                  (2k)![(3N+1-k)-(2k)]!


                          N       (3N-k)!
              =  (6N+2) SUM  ------------------
                         k=0  (2k)! (3N-3k+1)!

If we evaluate the terms in the summation in reverse order by
substituting N-k for each k, we have the equivalent expression

                             N       (2N+k)!
        S(6N+2)  =  (6N+2) SUM   ----------------
                            k=0  (2N-2k)! (3k+1)!

Consequently, the summation in question is an integer if and only
if S(6N+2) is divisible by (6N+2).  Now, recall that

                S(n) = S(n-2) + S(n-3)

for all n > 2, and we have the initial values S(3)=3, S(4)=2, 
and S(5)=5.  These happen to be the values that would result from
the initial values S(0)=3, S(1)=0, and S(2)=2, so the entire
sequence consists of Newtons sums for the roots of the cubic

                 x^3 - x - 1  =  0                      (2)

and by Fermat's theorem we immediately know S(p)=S(1)=0 (mod p)
and so S(p) is divisible by p for every prime p.  However, 
composite integers n such that S(n) is divisible by n are quite 
rare.  These are called pseudoprimes relative to the cubic (2).  
We are seeking a pseudoprime of the form n = 6N+2.  To prove that
N=2755452 gives such a number, we need only show that S(n) = 0 
(mod n) for n = 6*2755452+2 = 16532714.  The nth term of any
linear recurring sequence (mod n) can be evaluated in log(n)
steps (using binary exponentiation), so it's not hard to verify
that s(16532714)=0 (mod 16532714).  This is in fact the smallest
even pseudoprime relative to (2).