Difference Equations and Divisibility Properties of Sequences

TAMÁS LENGYEL

Mathematics Department, Occidental College, 1600 Campus Road, Los Angeles, CA 90041, USA

There are many different ways of defining a sequence in terms of solutions to difference equations. In fact, if a sequence satisfies one recurrence then it satisfies an infinite number of recurrences. Arithmetic properties of an integral sequence are often studied by direct methods based on the combinatorial or algebraic definition of the numbers or using their generating function. The rational generating function is the main tool in obtaining various difference equations with coefficients and initial values exhibiting divisibility patterns that can imply particular arithmetic properties of the solutions. In this process we face the challenging task of finding difference equations that are relevant to the divisibility properties by transforming the original rational generating function. As a matter of fact, it is not necessarily the simple difference equation which helps the most in proving the properties. We illustrate this process on several examples and a sequence involving a p-sected binomial sum of the form y_{n} = y_{n}(p, a) = ∑_{k=0}^{∞} \binom{n}{kp}a^{k} where p is an arbitrary prime. Let ρ_{p}(m) denote the exponent of the highest power of a prime p which divides m. Recently, the author obtained lower bounds for ρ_{p}(y_{n}) based on recurrence relations of order p and p − 1. The cases with tight bounds have also been characterized.

In this paper we prove that ρ_{p}(y_{np}(p, a)) = n for ρ_{p}(a + 1) = 1, p ≥ 3. We obtain alternative difference equations of order p^{2} for y_{n} and order p for the p-sected sequence y_{np} by a generating function based method. We also extend general divisibility results relying on the arithmetic properties of the coefficients and initial values.

AMS No. 11B37, 39A10, 11B65, 11B50 KEYWORDS: difference equations, divisibility, binomial sums, p-section (received: October 2001)

1. INTRODUCTION

We view a recurrent sequence as a solution to a linear difference equation with constant coefficients. The study of the various properties of recurrent sequences including arithmetic properties such as periodicity, congruences, and divisibility is often based on their generating functions. We illustrate this approach on different sequences and a specific integral sequence defined as a p-sected sum. A rather different aspect of p-secting a power series is that it may provide an important technical tool in focusing on particular arithmetic details of the original sequence. In addition, the p-section turns the original difference equation into another one without increasing its order. We focus on results related to the p-sected sum y_{n}(p, a) = ∑_{k=0}^{∞} \binom{n}{kp}a^{k} involving binomial coefficients. This sum is of independent interest. We note that it is not immediately obvious that y_{n}(p, a) should satisfy a recurrence with constant coefficients. Basic and alternative difference equations will be derived in Section 5 that will make this fact clear. Section 2 is devoted to examples to highlight the inherent differences of recurrent sequences from the point of view of divisibility. The generating function method is illustrated and applied to congruences and periodicity in Section 3. In Section 4 we develop and discuss fairly general tools for proving divisibility properties. Section 5 contains the main and some related results. Their derivation is based on the development of basic and alternative difference equations for y_{n}(p, a).

2. BASIC NOTATIONS AND EXAMPLES

Let the integral sequence y_{n} satisfy the recurrence relation of order d with integer coefficients c_{i}

y_{n} = ∑_{i=1}^{d} c_{i}y_{n−i}, n ≥ d + 1.  (1)

Let ρ_{p}(m) denote the exponent of the highest power of a prime p which divides m. We set ρ_{p}(0) = ∞ and ρ_{p}(u/v) = ρ_{p}(u) − ρ_{p}(v) if both u and v are integers. Let ν_{p}(k) be the sum of the digits in the base p representation of k. As it often turns out ρ_{p}(y_{d}) and ρ_{p}(c_{d}) play an important role in the analysis of ρ_{p}(y_{n}). We illustrate the basic differences in results and treatments of difference equations by presenting some examples. These examples are similar in appearance but rather different in nature. They aim at divisibility by 3. In Examples 1 and 2 this choice is arbitrary. The other two examples can be easily modified to discuss divisibility by other primes.

Example 1 Consider the following difference equation y_{n} = −y_{n−1}+y_{n−2}+y_{n−3}, n ≥ 3, with the initial conditions y_{0} = 0, y_{1} = 1, y_{2} = −1. Our goal is to calculate ρ_{3}(y_{720}).

Example 2 We shall determine ρ_{3}(y_{n}) and y_{n} for the solution to the difference equation y_{n} = y_{n−1} + y_{n−2}, n ≥ 2, with the initial conditions y_{0} = 0, y_{1} = 1.

Example 3 Consider the following difference equation y_{n} = 3y_{n−1} − 3y_{n−2}, n ≥ 3, with the initial conditions y_{0} = y_{1} = y_{2} = 1. Determine or at least give some bounds on the values of ρ_{3}(y_{n}) and ρ_{3}(y_{3n}), and calculate y_{n}.

Example 4 We ask the same questions as in Example 3 for the difference equation y_{n} = 3y_{n−1} − 3y_{n−2} + 3y_{n−3}, n ≥ 3, with the initial conditions y_{0} = y_{1} = y_{2} = 1.

To answer these questions we consider the generating function f(x) = ∑_{k=0}^{∞} y_{k}x^{k} of the sequence and try to derive the solution in a “closed form.” We explore the properties of the generating function to study arithmetic properties. The generating function f(x) can be written as a rational function P (x)/Q(x). The denominator Q(x) represents the difference equation while the numerator P (x) carries information on the initial values. For a recurrent sequence defined by identity (1) the usual initial choice for Q(x) is the characteristic polynomial 1 − c_{1}x − c_{2}x^{2} − … − c_{d}x^{d}. We note that if the roots of Q(x) are integers then this approach might offer a complete direct treatment of the questions. The generating function method provides the following answers to the examples.

Example 1: We use the partial fraction expansion of the generating function

f(x) = \frac{x}{(1 − x)(1 + x)^{2}} = \frac{1/4}{1 − x} + \frac{1/4}{1 + x} − \frac{1/2}{(1 + x)^{2}} .

This implies y_{n} = 1/4 + 1/4 · (−1)^{n} + 1/2 · (−1)^{n−1}(n + 1) = 1/4{(−1)^{n−1}(2n + 1) + 1}. We get y_{720} = −360, ρ_{3}(y_{720}) = 2, and in general,

ρ_{p}(y_{n}) = \{ \begin{matrix}ρ_{p}(n/2), & if n is even, \\ ρ_{p}((n + 1)/2), & if n is odd. \end{matrix}

This also follows by observing that the sequence runs through the positive and negative integers in a simple pattern: 0, 1, −1, 2, −2, 3, −3, ….

Example 2: The generating function is f(x) = \frac{x}{1−x−x^{2}} and y_{n} is the familiar Fibonacci number, F_{n}. For any prime p ≠ 2 and 5, we have (cf. [4], [7])

ρ_{p}(y_{n}) = \{ \begin{matrix}ρ_{p}(n) + ρ_{p}(F_{n(p)}), & if n ≡ 0 (mod n(p)), \\ 0, & if n ≢ 0 (mod n(p)) \end{matrix}

where n(p) is the rank of apparition or Fibonacci entry-point of p, i.e., the smallest positive index n such that p divides F_{n}. For example, n(3) = 4 and ρ_{3}(F_{4}) = 1. Also note that ρ_{5}(F_{n}) = ρ_{5}(n).

Example 3: The generating function is f(x) = \frac{(1−x)^{2}}{1−3x+3x^{2}} and y_{n} = 2 · 3^{\frac{n}{2} −1} cos \frac{nπ}{6} for n ≥ 1 (cf. [13]); therefore, y_{6n+3} = 0 and ρ_{3}(y_{n}) = ⌊\frac{n−1}{2}⌋, n ≢ 3 mod 6.

Example 4: In this case f(x) = \frac{(1−x)^{2}}{1−3x+3x^{2}−3x^{3}} which implies that ρ_{3}(y_{n}) ≥ ⌊\frac{n+1}{3}⌋ − 1, and equality holds if and only if n + 1 is a multiple of 3 (by Theorem C in Section 5). It follows that ρ_{3}(y_{3n}) ≥ n. In Section 5 we prove that equality holds here.

We will see that the sequences in the last three examples are related to the sum y_{n}(p, a).

3. CONGRUENCES AND PERIODICITY VIA GENERATING FUNC-TIONS

The generating function carries lots of information on the sequence. However, it is far from being obvious how to recover information relevant to arithmetic properties. Sometimes the fine details of the integer sequence defined by formula (1) are obscured by the usual rational function representation. There are relatively prime polynomials P (x) and Q(x) with integer coefficients and deg Q(x) ≤ d such that f(x) = P (x)/Q(x). In fact, there are infinitely many pairs (P (x), Q(x)) of numerators and denominators yielding f(x) = P (x)/Q(x). It might be beneficial to choose the pair with the minimal polynomial, Q(x), i.e., the uniquely determined polynomial of least degree. The advantage is that we have to deal with the least number of roots after the rational fraction expansion. The potential drawback of this approach is that the arithmetic properties might get deemphasized. From a historical point of view, the various arithmetic properties of factorials and binomial coefficients were studied by Legendre, Kummer, Lucas, and Anton. They found some remarkable results concerning divisibility and congruential properties. New and related techniques were developed to study other combinatorial quantities and to include periodic properties. A generating function based method was popularized by Fine’s proof of Lucas’ Theorem on expanding the congruence \binom{n}{k} (mod p) in 1947. A similar application (cf. [13]) shows that the Stirling number of the second kind, S(n, k), satisfies the congruence S(n, k) ≡ \binom{⌈k/2⌉+n−k−1}{n−k} mod 2. The modulo p periodicity of a sequence is also often studied via its generating function. The sequence {y_{n}}_{n≥0} is said to be periodic modulo M with period π if there exists an n_{0} ≥ 0 such that y_{n+π} ≡ y_{n} (mod M) for n ≥ n_{0}. The smallest such π is called the minimum period modulo M. If n_{0} = 0 then the sequence is said to be purely periodic. The following theorem describes an important situation.

Theorem A Let f(x) = 1/Q(x) be the generating function of the integer sequence y_{n} such that Q(x) is a polynomial with integer coefficients. The minimum period modulo M is the smallest integer π such that (1 − x^{π})f(x) is a polynomial modulo M. If Q(0) = 1 and its leading coefficient is relatively prime to M > 1 then the sequence y_{n} is purely periodic modulo M.

For example, the sequence \{\binom{n}{k}\}_{n≥k} is purely periodic for its generating function is 1/(1 − x)^{k+1}. The sequence in Example 2 and {y_{n+1}}_{n≥0} of Example 1 are also purely periodic modulo any integer. Zabek [14] obtained the minimum period of the binomial coefficients modulo p^{N} in 1956, while Trench [12] extended this result for integer-valued polynomials in 1960. In 1987 Nijenhuis and Wilf [10] determined the modulo p periodicity of S(n, k) in n, while Kwong [5] determined the period modulo p^{N}, N > 1, in 1989. Note that if P (x) and Q(x) are relatively prime modulo p then the modulo p^{N} period length of the sequence y_{n} depends on the denominator Q(x) only (cf. [4]).

4. DIVISIBILITY VIA GENERATING FUNCTIONS

Let the integral sequence y_{n} satisfy the recurrence (1) of order d. There are no general methods known to calculate ρ_{p}(y_{n}) but ad hoc calculations based on the closed form of the sequence (cf. Examples 1 and 3) or modulo p^{N} periodicity. For example, the periodic property obtained by Kwong [5] lead to the divisibility properties described in

Theorem B [6, Theorem 2] Let c be an odd and n be a non-negative integer. If 1 ≤ k ≤ n + 2 then ρ_{2}(k! S(c · 2^{n}, k)) = k − 1, i.e., ρ_{2}(S(c · 2^{n}, k)) =ν_{2}(k) − 1.

We discuss three different sets of conditions on the divisibility of the coefficients and initial values that help in the systematic study of ρ_{p}(y_{n}).

(a) Assume that the initial value condition ρ_{p}(c_{d}) = 0 holds. A basis of sequences is defined as a collection of d sequences for which any sequence can be described uniquely as a linear combination of the basis sequences. For any prime p such that ρ_{p}(c_{d}) = 0, there exist infinitely many integers k in a full arithmetic sequence with the property that a block of d consecutive terms of each basis sequence, starting with the kth term, has d−1 of these terms divisible by p while the remaining term is congruent to 1 mod p (cf. [9]).

(b) Assume that for some nonnegative integer m and positive integer r, the initial values and coefficients satisfy the conditions

min_{1≤i≤d−1} ρ_{p}(y_{i}) ≥ ρ_{p}(y_{d}) = m ≥ 0

and

min_{1≤i≤d−1} ρ_{p}(c_{i}) ≥ ρ_{p}(c_{d}) = r ≥ 1,

respectively. The lower bound ρ_{p}(y_{n}) ≥ (⌊\frac{n}{d}⌋ − 1)r + m is obtained in [2], and the cases where the bound is tight are also characterized. (Theorem C below is a special case of this with y_{n} = y_{n}(p, a).)

(c) If the initial values and coefficients satisfy the conditions

ρ_{p}(y_{i}) = i, 1 ≤ i ≤ d,

and

ρ_{p}(c_{i}) ≥ i + 1, 1 ≤ i ≤ d − 1, and ρ_{p}(c_{d}) = d,

respectively, then ρ_{p}(y_{n}) = n for n ≥ 1. The proof follows by induction on n. We have not found any previous reference to this result. Case (c) is illustrated on the sum y_{n}(p, a) in the Theorem provided p ≥ 3 and ρ_{p}(a + 1) = 1.

What is remarkable about these relations is that there is no need for calculating the coefficients c_{i}s and initial values y_{i}s explicitly but a proof of their divisibility properties. Conditions (b) and (c) imply that ρ_{p}(y_{n}) increases as n → ∞ while condition (a) shows that this is not always the case.

5. RESULTS: DIVISIBILITY PROPERTIES OF y_{n}(p, a)

The divisibility properties of y_{n}(p, a) eventually depend on the divisibility by p of a + 1 for any prime p ≥ 3 and of a − 1 for p = 2. The author recently proved

Theorem C [8] Let p be an arbitrary prime and a be an integer such that ρ_{p}(a+1) = 1 if p ≥ 3, or a ≡ 3 (mod 4) if p = 2. Then ρ_{p} (∑_{k=0}^{⌊n/p⌋} \binom{n}{k p}a^{k}) ≥ ⌊\frac{n+1}{p}⌋ − 1, and equality holds if and only if p divides n + 1. If p ≥ 3 and ρ_{p}(a + 1) ≥ 2 then for n ≥ 1: ρ_{p} (∑_{k=0}^{⌊n/p⌋} \binom{n}{k p}a^{k}) ≥ ⌊\frac{n}{p−1}⌋ − 1, and equality holds if and only if p − 1 divides n. If p = 2 and ρ_{2}(a − 1) = 2 then ρ_{2} (∑_{k=0}^{⌊n/p⌋} \binom{n}{k p}a^{k}) = n − 1 for n ≡ 1, 2 mod 3, and it is at least as large as n if n is a multiple of 3. If p = 2 and ρ_{2}(a − 1) ≥ 3 then ρ_{2} (∑_{k=0}^{⌊n/p⌋} \binom{n}{k p}a^{k}) = n − 1.

If a ≢ −1 mod p then ∑_{k=0}^{⌊n/p⌋} \binom{n}{k p}a^{k} ≡ (a + 1)^{⌊n/p⌋} mod p, hence ρ_{p} (∑_{k=0}^{⌊n/p⌋} \binom{n}{k p}a^{k}) = 0.

Remark The last case easily follows from Lucas’ Theorem. Actually, if p|n then the congruence \binom{n}{k p} ≡ \binom{n/p}{k} mod p can be improved [3] to \binom{n}{k p} ≡ \binom{n/p}{k} mod p^{3} for p ≥ 5. Therefore, if a ≢ −1 mod p and n is a multiple of p then the stronger statement y_{n}(p, a) ≡ (a + 1)^{n/p} mod p^{3} holds true for p ≥ 5. The divisibility structures described in Theorem C are extended in the main result of this paper.

Theorem Let p be an odd prime and a be an integer such that ρ_{p}(a + 1) = 1. Then ρ_{p}(y_{np}(p, a)) = n for n ≥ 0. In particular,

y_{(n+p)p} ≡ (a + 1)^{p}y_{np} (mod p^{n+p+1}).  (2)

For any prime p ≥ 3 and a = −1 we have

y_{(n+p)(p−1)} ≡ −p^{p}y_{n(p−1)} (mod p^{n+p}), n ≥ 1.  (3)

Some special cases with a = −1, 1, and 5 are of considerable interest. The case with a = −1 has been studied in [2], and it is related to the divisibility properties of S(n, k). If a = −1 and p = 3 as in Example 3, then the study of y_{n}(3, −1) can be carried out by using the trigonometric formula y_{n}(3, −1) = 2 · 3^{\frac{n}{2} −1} cos \frac{nπ}{6}, n ≥ 1 [13, Example 4, in Section 2.4]. For a = 1 direct summation yields y_{n}(2, 1) = 2^{n−1} while for any odd prime p we get y_{n}(p, 1) ≡ 2^{⌊n/p⌋} modp. The Fibonacci numbers F_{n} = F_{n−1} + F_{n−2}, n ≥ 2, F_{0} = 0, F_{1} = 1, are related to y_{n} = y_{n}(2, 5) by the celebrated identity 2^{n−1}F_{n} = ∑_{k=0}^{∞} \binom{n}{2k+1}5^{k}. It follows that F_{n} = 2^{1−n}5^{−1}(y_{n+1} − y_{n}). (For references on ρ_{p}(F_{n}) see [4] or [7].) Theorem C also implies that ρ_{2}(y_{n}(2, 3)) = \frac{n−1}{2} for n odd, and it is at least \frac{n}{2} for n even. This identity appeared in [1].

Proof of the Theorem From now on p denotes an odd prime. We obtain (cf. [2, 8]) a rational generating function for y_{k}(p, a) with a numerator and denominator of the same degree

∑_{k=1}^{∞} y_{k}(p, a)x^{k} = \frac{x\{(1 − x)^{p−1} + ax^{p−1}\}}{(1 − x)^{p} − ax^{p}} = \frac{N_{a}(x)}{D_{a}(x)}.  (4)

Note that Theorem C can be proven by using this rational generating function. In fact,

∑_{k=1}^{∞} y_{k}(3, 2)x^{k} = \frac{x − 2x^{2} + 3x^{3}}{1 − 3x + 3x^{2} − 3x^{3}}  (5)

yields the third order difference equation of Example 4: y_{n+3} = 3y_{n+2}−3y_{n+1}+3y_{n}, n ≥ 0. To prove the Theorem we form alternative recurrence relations for the original sequence y_{n} with properties that are more helpful in analyzing its p-sected subsequence y_{np}. For instance, we can switch from the original difference equation to y_{n+4} = 2y_{n+3} + 3y_{n}. This alternative difference equation can be obtained by substitutions or by realizing that D_{2}(x) = 1−3x+3x^{2} −3x^{3} multiplied by 1+x becomes 1−2x−3x^{4}. The newly obtained difference equation of order 4 suggests an order 12 linear recurrence relation involving only terms with indices whose differences are multiples of 3. Unfortunately, this difference equation

y_{n+12} = 8y_{n+9} + 36y_{n+6} + 54y_{n+3} + 27y_{n}

is of little help in proving the particular divisibility properties as its coefficients did not follow any nice divisibility patterns.

However, there is a general method providing us with a recurrence relation of order p^{2} (for ρ_{p}(a + 1) = 1 and p ≥ 3) such that all index differences are divisible by p, and the coefficients exhibit some divisibility patterns. We follow Gessel’s idea [2] and multiply both N_{a}(x) and D_{a}(x) of (4) by D_{a}(ωx)D_{a}(ω^{2}x) … D_{a}(ω^{p−1}x), where ω is a primitive pth root of unity. Since D_{a}^{∗}(x) = D_{a}(x)D_{a}(ωx) … D_{a}(ω^{p−1}x) is invariant under substituting ωx for x, it must be a polynomial in x^{p}. This allows us to p-sect the coefficients of the sequence y_{k} by multiplying its generating function by D_{a}^{∗}(x). We are able to write

∑_{k=1}^{∞} y_{k}(p, a)x^{k} = \frac{N_{a}^{∗}(x)}{D_{a}^{∗}(x)},  (6)

where

N_{a}^{∗}(x) = x{(1 − x)^{p−1} + ax^{p−1}} ∏_{j=1}^{p−1} ((1 − ω^{j}x)^{p} − a(ω^{j}x)^{p}) = b_{1}x + b_{2}x^{2} + …,

with b_{1} = 1 and

D_{a}^{∗}(x) = ∏_{j=0}^{p−1} ((1 − ω^{j}x)^{p} − a(ω^{j}x)^{p}) = 1 + c_{p}x^{p} + c_{2p}x^{2p} + …  (7)

are polynomials of degree p^{2} if ρ_{p}(a + 1) = 1 and p(p − 1) if a = −1, respectively. For example, we find an equivalent form of identity (5)

∑_{k=1}^{∞} y_{k}(3, 2)x^{k} = \frac{x + x^{2} + 3x^{3} + 12x^{5} + 18x^{6} − 9x^{7} + 9x^{8} + 27x^{9}}{1 − 9x^{3} − 27x^{6} − 27x^{9}} .  (8)

If ρ_{p}(a + 1) = 1 then by identities (6) and (7), and after determining y_{p}, y_{2p}, … y_{p^{2}}, we can derive the recurrence relation (n ≥ 1)

y_{(n+p)p} = −c_{p}y_{(n+p−1)p} − c_{2p}y_{(n+p−2)p} − … − c_{p^{2}}y_{np},  (9)

and that’s all we need to evaluate y_{kp}, for k > p. For a = −1 and n ≥ 1 we use

y_{(n+p)(p−1)} = −c_{p}y_{(n+p−1)(p−1)−1} − c_{2p}y_{(n+p−2)(p−1)−2} − … − c_{(p−1)p}y_{n(p−1)} (10)

to evaluate y_{k(p−1)}, for k > p. The degree of the denominator in identity (6) is the order of the difference equations in (9) and (10). However, the order can be reduced by a factor of p as we do p-section. To apply case (c) of Section 4 we need

Lemma 1 If ρ_{p}(a + 1) = 1 then ρ_{p}(c_{kp}) ≥ k + 1 for k = 1, 2, …, p − 1 and ρ_{p}(c_{p^{2}}) = p. If a = −1 then ρ_{p}(c_{kp}) ≥ k + 1 for k = 1, 2, …, p − 2 and ρ_{p}(c_{(p−1)p}) = p.

This lemma is crucial in proving the Theorem both for small and large values of n. In the former case, for the initial values k = 1, 2, …, p, we shall also need

Lemma 2 For ρ_{p}(a + 1) = 1 we have ρ_{p}(b_{kp}) = k for k = 1, 2, …, p.

For example, multiplying both sides of (8) by D_{2}^{∗}(x) and equating the coefficients yields ρ_{3}(b_{3k}) = k, 1 ≤ k ≤ 3, by Lemma 2, and therefore, ρ_{3}(y_{3k}) = k, 1 ≤ k ≤ 3.

Proof of Lemma 1 Binomial expansion yields D_{a}(x) = ( ∑_{j=0}^{p−1} \binom{p}{j}(−1)^{j}x^{j}) − (a + 1)x^{p}. We expand the denominator D_{a}^{∗}(x) symbolically by counting the ways its factors contribute to x^{kp}, k = 0, 1, …, p. We observed that D_{a}^{∗}(x) is actually a polynomial in x^{p}; therefore, we need only these terms. Any combination of p factors contributing x^{kp} to the expansion can be characterized by the number, i_{j}, of polynomial factors in (7) in which the term with x^{j} is selected. For ρ_{p}(a + 1) = 1 we get ∑_{j=0}^{p} ji_{j} = kp and ∑_{j=0}^{p} i_{j} = p since each of the p factors has exactly one contributing term. By binomial expansion and ignoring the factors of ω, the contribution of any term with the characterization (i_{0}, i_{1}, …, i_{p}) is a multiple of

\binom{p}{0}^{i_{0}} \binom{p}{1}^{i_{1}} ⋯ \binom{p}{p − 1}^{i_{p−1}}(−a − 1)^{i_{p}}.  (11)

We determine the exponent in the power of p which divides this quantity in terms of (i_{0}, i_{1}, …, i_{p}). The exponent is at least p − i_{0} ≥ k and equality holds if and only if 8 T. Lengyel

(i_{0}, i_{1}, … i_{p}) = (p − k, 0, 0, …, 0, k). In this latter case there are \binom{p}{k} ways of choosing the k factors with x^{p}. It follows that ρ_{p}(c_{kp}) ≥ k + 1 for 1 ≤ k ≤ p − 1 and ρ_{p}(c_{p^{2}}) = p. In fact, c_{p^{2}} = −(a + 1)^{p}.

If a = −1 then none of the p factors in (7) have a term involving x^{p}; therefore, we can remove the last factor of (11). In this case p − i_{0} ≥ k + 1 holds yielding ρ_{p}(c_{kp}) ≥ k + 1 for 1 ≤ k ≤ p − 2, while c_{(p−1)p} = p^{p}. Note that c_{kp} = 0 is also true for k odd [2].

Proof of Lemma 2 We leave out the details but note that although N_{a}^{∗}(x) looks less structured than D_{a}^{∗}(x) it is easier to describe the relevant coefficients b_{kp}, 1 ≤ k ≤ p. Actually, we are able to determine b_{kp} (mod p^{k+1}) as calculations similar to those in the proof of Lemma 1 lead to b_{kp} ≡ (−1)^{k−1}\binom{p−1}{k−1}((a + 1)^{k} + \binom{p}{k}^{p−1}(−1)^{k}) (mod p^{k+1}) for 1 ≤ k ≤ p−1 and b_{p^{2}} = (a+1)^{p}. The condition ρ_{p}(a+1) = 1 guarantees that ρ_{p}(b_{kp}) = k.

The proof of the Theorem is now complete by the p-sections y′_{n} = y_{np} and c′_{i} = c_{ip}, and transforming identity (9) to identity (1) with d = p. In fact, Lemmas 1 and 2 guarantee the conditions in part (c) of Section 4. By the lemmas, identities (9) and (10) also imply (2) and (3).

Note that the p-secting steps of the proof can be easily extended to polynomial denominators different from D_{a}^{∗}(x) with the original orders preserved.

References

[1] D. M. Bloom, Solution to Problem 428, College Math. Journal 22(1991), 257–259.

[2] I. M. Gessel and T. Lengyel, On the order of Stirling numbers and alternating binomial coefficient sums, Fibonacci Quarterly 39(2001), 444–454.

[3] A. Granville, Binomial coefficients modulo prime powers, in preparation at http:

//www.math.uga.edu:80/˜ andrew in Binomial/index.html or Postscript/binomial.ps

[4] D. E. Knuth, The Art of Computer Programming, vol. 2., Seminumerical Algorithms, Second Edition, Addison-Wesley, Reading, 1981.

[5] Y. H. Kwong, Minimum periods of S(n, k) modulo M, Fibonacci Quarterly 27(1989), 217–221.

[6] T. Lengyel, On the divisibility by 2 of the Stirling numbers of the second kind, Fibonacci Quarterly 32(1994), 194–201.

[7] T. Lengyel, The order of the Fibonacci and Lucas numbers, Fibonacci Quarterly 33(1995), 234– 239.

[8] T. Lengyel, Divisibility properties by recurrence relations, in: Advances in Difference Equations, Proceedings of the Second International Conference on Difference Equations and Its Applications, (S. Elaydi, I. Győri, and G. Ladas, Eds.), Gordon and Breach Science Publishers, London, 1997, pp. 391–397.

[9] N. S. Mendelsohn, Congruence relationships for integral recurrences, Can. Math. Bull. 5(1962), 281–284.

[10] A. Nijenhuis and H. S. Wilf, Periodicities of partition functions and Stirling numbers modulo p, J. Number Theory 25(1987), 308–312.

[11] D. W. Robinson, A note on linear recurrent sequences modulo m, Amer. Math. Monthly 73(1966), 619–621.

DIFFERENCE EQUATIONS AND DIVISIBILITY PROPERTIES 9

[12] W. F. Trench, On periodicities of certain sequences of residues, Amer. Math. Monthly 67(1960), 652–656.

[13] H. S. Wilf, generatingfunctionology, Academic Press, Boston, 1990.

[14] S. Zabek, Sur la periodicite modulo m des suites de nombres \binom{n}{k}, Ann. Univ. Mariae Curie-Sklodowska, Sect. A 10(1956), 37–47.