|
|
|
Who knew there was so much to say about the product of consecutive integers? This page answers the following questions:
The formula for finding the product of any odd number of consecutive integers follows the pattern of coefficients in Sloane's A008955.
If the number of numbers is 2k+1, where k=0,1,2,..., then we can define a function Podd(k,n) as the product of 2k+1 numbers in which the "middle" number is n. That is Podd(k,n)=(n-k)(n-k+1)...(n+k)
Notice that Podd(k+1,n) = (n2-k2) Podd(k,n), which gives us a recurrence relation that lets us find the coefficients of each polynomial:
Podd(0,n) = (n) = n
Podd(1,n) =
(n-1)(n)(n+1) = n3 -n
Podd(2,n) =
(n-2)(n-1)...(n+2) = n5 -5n3 +4n
Podd(3,n) =
(n-3)(n-2)...(n+3) = n7 -14n5 +49n3
-36n
Podd(4,n) =
(n-4)(n-3)...(n+4) = n9 -30n7 +273n5
-820n3 +576n
Podd(5,n) =
(n-5)(n-4)...(n+5) = n11 -55n9 +1023n7
-7645n5 +21076n3 -14400n
Podd(6,n) =
(n-6)(n-5)...(n+6) = n13 -91n11 +3003n9
-44473n7 +296296n5 -773136n3 +518400n
Podd(7,n) =
(n-7)(n-6)...(n+7) = n15-... well, you get the idea!
The formula for finding the product of any even number of consecutive integers follows the pattern of coefficients in Sloane's A008956.
If the number of numbers is 2k, where k=0,1,2,..., then we can define a function Peven(k,n) as the product of 2k numbers in which the sum of the two "middle" numbers is n. Notice that this sum is always odd. Each of the consecutive numbers can be represented as (n+m)/2, where m is an odd number that ranges from -2k+1 to 2k-1. That is,
Peven(k,n)=(n-2k+1)/2 (n-2k+3)/2 ...
(n+2k-1)/2, or
Peven(k,n)=(n-2k+1) (n-2k+3) ... (n+2k-1)/22k
Notice that Peven(k+1,n) = (n2-(2k-1)2) Peven(k,n), which gives us a recurrence relation that lets us find the coefficients of each polynomial:
Peven(0,n) = (1)/20 = 1
Peven(1,n) =
(n-1)(n+1)/22 = (n2 -1)/4
Peven(2,n) =
(n-3)(n-1)(n+1)(n+3)/24 = (n4 -10n2
+9)/16
Peven(3,n) =
(n-5)(n-3)...(n+5)/26 = (n6 -35n4
+259n2 -225)/64
Peven(4,n) =
(n-7)(n-5)...(n+7)/28 = (n8 -84n6
+1974n4 -12916n2 +11025)/256
Peven(5,n) =
(n-9)(n-7)...(n+9)/210 = (n10 -165n8
+8778n6 -172810n4 +1057221n2 -893025)/1024
Peven(6,n) =
(n-11)(n-9)...(n+11)/212 = (n12 -286n10
+28743n8 -1234948n6 +21967231n4
-128816766n2 +108056025)/4096
Peven(7,n) =
(n-13)(n-11)...(n+13)/214 = (n14 -455n12
+77077n10 -6092515n8 +230673443n6
-3841278805n4 +21878089479n2 -18261468225)/16384
Of course, the product of integers from k+1 to n is n!/k!. Toward the end of Mathworld's article in Stirling's Approximation to n!, this statement appears:
Gosper has noted that a better approximation to n! (i.e., one which approximates the terms in Stirling's series instead of truncating them) is given by
n! ≈ sqrt((2n+1/3)π) nn e-n
Using this approximation, n!/k! is given by
n!/k! ≈ (n/e)n-k (n/k)k sqrt(6n+1) / sqrt(6k+1)
This form is useful for computation, especially when k is almost as large as n, because it avoids very large or very small numbers in intermediate results.
Proof 1: Consider the number of n-element sets of an (n+m) element
set. This is C(n+m,n), which is an integer, and
C(n+m,n) = (m+1)(m+2)(m+3)...(m+n) / n!. The numerator is the product of n
consecutive integers, and the denominator is n!, proving that the product of n
consecutive integers is divisible by n!.
Proof 2: Consider the largest power of each prime factor of the product of consecutive integers. Let P be the product,
P = (m+1)(m+2)...(m+n) = (m+n)!/m!
For any given positive integer n and prime p, define the function E(n,p) = e such that pe is the largest power of p that divides n!. This is the number of numbers from 1 to n divisible by p plus the number of numbers divisible by p2 plus the number of numbers divisible by p3, etc.
E(n,p) = floor[n/p] + floor[n/p2] + floor[n/p3] + ...
Using this definition with the product, P=(m+n)!/m!, we see that
E(m+n,p)-E(m,p) = floor[(m+n)/p] - floor[m/p] + floor[(m+n)/p2] - floor[m/p2] + floor[(m+n)/p3] - floor[m/p3] + ...
which is at least as large as E(n,p) for any given m, n and p, because for any real numbers, a and b, floor[a+b] ≥ floor[a] + floor[b]
A note about products of negative numbers
The two proofs, above work for products of n positive integers, but the statement is also true when the product includes negative integers or zero. There are two cases that need to be considered:
Case 1: the product of negative numbers. This is equal to plus or minus the product of the corresponding positive numbers, and so it is divisible by n!.
Case 2: the product of numbers, some of which are negative, and some of which are not negative. In this case, one of the numbers must be zero, so the product is zero, and zero is divisible by all n!
Proof that floor[a+b] ≥ floor[a] + floor[b]
It may seem obvious, but it's a little tricky, so I've included this little proof:
a ≥ floor[a], and b ≥ floor[b], so
a+b ≥ floor[a]+floor[b].
floor is a nondecreasing function, which means if x ≥ y, then floor[x] ≥ floor[y], so we can take the "floor" of both sides of this inequality:
floor[a+b] ≥ floor[floor[a]+floor[b]] = floor[a]+floor[b]
Puzzle: A Two-Player Game proves some interesting facts about complementary Beatty sequences using the floor function.
The webmaster and author of this Math Help site is Graeme McRae.