For a positive integer $n \ge 2$, define a sequence $a_1, a_2, \cdots ,a_n$ as the following. $$ a_1 = \frac{n(2n-1)(2n+1)}{3}$$$$a_k = \frac{(n+k-1)(n-k+1)}{2(k-1)(2k+1)}a_{k-1}, \text{ } (k=2,3, \cdots n)$$ (a) Show that $a_1, a_2, \cdots a_n$ are all integers. (b) Prove that there are exactly one number out of $a_1, a_2, \cdots a_n$ which is not a multiple of $2n-1$ and exactly one number out of $a_1, a_2, \cdots a_n$ which is not a multiple of $2n+1$ if and only if $2n-1$ and $2n+1$ are all primes.
Problem
Source: 2017 FKMO Day 2 Problem 4
Tags: number theory, combination
26.03.2017 08:05
Thanks @Dukejukem, your $v_p$ to indicator variable method in this problem helped me
26.03.2017 14:31
See that , $\prod_{i=2}^k \frac{a_i}{a_{i-1}} = \prod_{i=2}^k\frac{(n+i-1)(n-i+1)}{2(i-1)(2i+1)} =>a_k = \frac{n(2n-1)(2n+1)}{3}\prod_{i=2}^k\frac{(n+i-1)(n-i+1)}{2(i-1)(2i+1)} = \frac{(n+k-1)!(2n-1)(2n+1)}{2^{k-1}(k-1)!(n-k)!(2k+1)!!}$ $=>a_k = \frac{(n+k-1)!(2n-1)(2n+1)}{(2k+1)(n-k)!(2k-1)!} = \frac{4n^2-1}{2k+1}C_{2k-1}^{n+k-1} \forall (k=2,3, \cdots n) $ Lemma 1: $\frac{2k+1}{gcd(2k+1,4n^2-1)} | C_{2k-1}^{n+k-1}$ Proof: $C_{2k+1}^{n+k+1} = \frac{(n+k)(n+k+1)}{(2k+1)(2k)}.C_{2k-1}^{n+k-1}$ ,as the LHS is an integer, we must have $2k+1 | (n+k)(n+k+1).C_{2k-1}^{n+k-1}=>\frac{2k+1}{gcd(2k+1,(n+k+1)(n+k))} | C_{2k-1}^{n+k-1}$ But,$gcd((n+k+1)(n+k),2k+1) = gcd(4n^2 - 1 + (2k+1)^2,2k+1) = gcd(4n^2-1,2k+1)$. Hence proved.(Part(a) follows from Lemma 1) Lemma 2: If $p$ is a prime then $v_p(C_{p}^{kp+r}) = v_p(kp) -1$ , $\forall k \in \mathbb{N}$ , where $0 \le r \le p-1$ Proof: The result trivially follows from $C_{p}^{kp+r} = \frac{(kp+r) \cdots k \cdots (kp-p+1)}{(p+r) \cdots(p+1)(p-1)(p-2) \cdots(2)}$ Lemma 3:If $2k+1$ is a prime and $2k+1 | (n+k)(n+k+1)$, then $2k+1 \nmid C_{2k-1}^{n+k-1}$ Proof: From the identity , $C_{2k+1}^{n+k+1} = \frac{(n+k)(n+k+1)}{(2k+1)(2k)}.C_{2k-1}^{n+k-1}$,it's clear that $v_{2k+1}(C_{2k+1}^{n+k+1}) + 1 = v_{2k+1}(C_{2k-1}^{n+k-1})+v_{2k+1}((n+k)(n+k+1))$ By Lemma 2 , $=>v_{2k+1}(C_{2k-1}^{n+k-1}) = 0$ Hence proved(Part (b) follows from Lemma 3)
12.04.2017 11:37
The above are not true because we do not know that $4n^2-1$ always has at least $3$ different prime divisors: take, for instance, $n=13$. In general, your proofs are false if $n$ is such that $2n-1$ and $2n+1$ are different powers of primes.(I am reffering to b), of course) So, am I right or not ?! I think I am. Else, I have not understood their solutions.
12.04.2017 12:34
I am guessing you are talking about part(b). For part (b), Lemma 3: states that $gcd(C_{2k-1}^{n+k-1}, 4n^2-1) =1$.So for any number(not necessarily a prime) that divides $4n^2-1$ , say $k$, we have $a_k$ not divisible by $4n^2-1$.So the number of divisors of $4n^2-1$ ($\le 2n+1$) must be $2$. (eg: For $n=13$ we have $4n^2-1 = 5^2.3^3$ , now $a_3,a_5$ and $a_{9}$ are all that is not divisible by $4n^2-1$)
12.04.2017 12:42
Heey, how dumb I am... well, we obviously have that $a_n, a_{n-1}$ are not multiples of $2n+1,2n-1$, respectively, so now everything goes smoothly, fortunately! @above. you forgot the condition that $2k+1$ is prime, NOT $k$. Anyway, does not matter anymore. Congrats for the solutions!
03.10.2020 14:31
(a)We have $a_k=\frac{(n-k+1)(n-k+2)...(n+k-2)(n+k-1)(2n-1)(2n+1)}{2^{k-1}(k-1)!k!!}=\binom{n+k-1}{2k-1}\frac{(2n-1)(2n+1)}{2k+1}$ Notice that it is equvialent to $$\binom{n+k-1}{2k-1}\frac{(n-k)(n+k)2k}{2k(2k+1)}=\binom{n+k-1}{2k+1}2k$$mod $2k+1$, this shows that it is an integer. (b)If $2n-1$ and $2n+1$ are both primes, then $(\binom{n+k-1}{2k-1},2n-1)=(\binom{n+k-1}{2k-1},2n+1)$, so each of the numbers $a_1,...,a_{n-2}$ are multiples of $2n-1$ and $2n+1$. By easy checking, $2n-1\nmid a_{n-1}$ and $2n+1=a_n$. If $2n-1$ is not a prime, let $p|2n-1$ then take $2k+1=p$, then it suffices to show that $p\nmid\binom{n+k-1}{2k-1}$. Indeed, $2k-1=p-2$ and $n+k-1\frac{2n+2k-1}{2}\equiv -1\pmod p$. We complete the proof by Lucas theorem.
12.08.2022 14:54
(a) We can easily see that $a_k = \binom{n+k-1}{2k-1} \frac{(2n-1)(2n+1)}{2k+1}$ Since $gcd(2k+1,k)=1$, by$\pmod {2k+1}$, it is sufficient to show that $\binom{n+k-1}{2k-1} \frac{(n-k)(n+k)}{2k+1}$ is integer. $\binom{n+k-1}{2k-1} \frac{(n-k)(n+k)}{2k+1}=\binom{n+k}{2k+1} 2k$, so $a_k$ is integer. (b) $a_{n-1}=(2n-2)(2n+1)$ and $a_n=2n-1$, so $2n-1$ doesn't divide $a_{n-1}$, and $2n+1$ doesn't divide $a_n$. Suppose that $2n-1$ and $2n+1$ are both primes. If $k\neq n-1$, $gcd(2k+1,2n-1)=1$ so $2k+1\mid \binom{n+k+1}{2k-1} (2n+1)$. Let $z=\binom{n+k+1}{2k-1} \frac{2n+1}{2k+1}$, which is an integer when $k\neq n-1$. Then $a_k=z(2n-1)$, so $a_k$ is a multiple of $2n-1$ for $k=1,2,\cdots,n-2,n$. Similarly, $a_k$ is a multiple of $2n+1$ for $k=1,2,\cdots,n-1$. Suppose that only one out of $a_1,a_2,\cdots a_n$ does not divide $2n-1$ and only one out of them does not divide $2n+1$. Assume that $2n-1$ is not prime. Let $p=2k+1$ be a prime factor of $2n-1$. Then $p\mid (2n-1)+(2k+1)$, so $p\mid n+k$. Since $n-k-1$ and $n+k$ are multiple of $p$, it is clear that $v_p((n+k-1)!)=v_p((n-k)!)$. Therefore, $v_p(\binom{n+k-1}{2k-1})=v_p((n+k-1)!)-v_p((n-k)!)-v_p((2k-1)!)=0$ $2n-1$ and $2n+1$ are relatively prime, so $p$ does not divide $2n+1$. So $\binom{n+k-1}{2k-1} \frac{2n+1}{2k+1}$ is not an integer. It means that $a_k$ is not a multiple of $2n-1$, which is a contradiction since $k\neq n-1$. Therefore, $2n-1$ is a prime. Similarly, we can show that $2n+1$ is a prime, and that ends the proof.