Author |
Topic: Products of powers of consecutive integers (Read 635 times) |
|
NickH
Senior Riddler
Gender: 
Posts: 341
|
 |
Products of powers of consecutive integers
« on: Apr 16th, 2005, 7:28pm » |
 Quote  Modify
|
Is it true that for each k > 0, for every integer n, the product
f(n, k) = (n - k)(n - k + 1)2(n - k + 2)3...nk+1...(n + k - 2)3(n + k - 1)2(n + k)
is divisible by f(k+1, k)?
For example, this is true for k = 2:
(n - 2)(n - 1)2n3(n + 1)2(n + 2)
is indeed divisible by 1.22.33.42.5 = 8640, for every integer n.
|
|
 IP Logged |
Nick's Mathematical Puzzles
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Products of powers of consecutive integers
« Reply #1 on: Apr 17th, 2005, 4:35am » |
Quote Modify
|
The following was more compact in my head than when I actually wrote it out. 
| hidden: |
The problem is equivalent to showing that for any prime p, the maximal power of p that divides f(n, k) is at least that which divides f(k+1, k). Since the maximal power of p that divides a product Prod(ai) is
[sum]k (# of terms that pk divides),
it suffices to show that every number m divides at least as many terms in f(n, k) as in f(k+1, k). (Count each n [pm] i term individually.) Let P(n, k) = n(n-1)...(n-k+1); we have f(n,k) = Prodi=0k P(n+i, k+1). But the number of terms that m divides in P(x, y) is either Ceiling[y/m] or Floor[y/m], and depends on the modulus class of m that x falls in; some initial classes 1,2,...,z yield Floor[y/m], and the remaining classes yield Ceiling[y/m]. The terms in f(k+1, k) = Prodi=0k P(k+i+1, k+1) start from k+2 = 1 mod (k+1), and this clearly leads to the maximum number of terms with value Floor[y/m], and therefore f(k+1,k) has the minimum value for the number of terms that m divides. So m divides at least as many terms of f(n, k) as terms of f(k+1, k), which is what we wanted to prove.
|
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print