[seqfan] Re: when does n+1 fail to divide binomial(n^2,n+1) ?

[Max Alekseyev]

It never fails beyond n=1.

Recall that the valuation of m! w.r.t. prime p equals the sum
floor(m/p^i) over i=1,2,3,...
Moreover, if m=a+b where a and b are nonnegative integers, then
floor(m/p^i) - floor(a/p^i) - floor(b/p^i) >= 0.
(Actually, this property implies that the valuation of
binomial(m,a)=m!/a!/b! w.r.t. prime p is always nonnegative, i.e.,
binomial(m,a) is an integer).

Let n>1. To prove that binomial(n^2, n)/(n+1) is an integer, it is
enough to show that its valuation w.r.t. any prime p is nonnegative.
It is clear that troubles may come only from primes dividing n+1.
Let valuation(n+1,p)=k > 0, i.e., n+1=p^k*m where prime p does not
divide m. Then
n = p^k*m - 1
n^2 = p^(2k)*m^2 - 2*p^k*m + 1
and
n^2 - n = p^(2k)*m^2 - 3*p^k*m + 2.

It is easy to check that

floor(n^2/p^i) - floor(n/p^i) - floor((n^2-n)/p^i) = 1

for i=1,2,...,k if p>2 and for i=2,3,...,k+1 if p=2, implying that
valuation(binomial(n^2, n)/(n+1),p) >= 0. QED


Max

On Sat, May 8, 2010 at 3:45 PM, N. J. A. Sloane <njas at research.att.com> wrote:
>
> Dear Seqfans,
> Michel Lagneau has contributed the following sequence.
> After some editing, it reads as follows:
>
> %I A177234
> %S A177234 0,1,2,21,364,8855,278256,10737573,491796152,26088783435,1573664496040,
> %T A177234 106395830418878,7970714909592876,655454164338881388,
> %U A177234 58702034425556612832,5687847988198592380965,592867741295430227919600
> %S A177234 0,-1,2,21,364,8855,278256,10737573,491796152,26088783435,1573664496040,
> %T A177234 106395830418878,7970714909592876,655454164338881388,
> %U A177234 58702034425556612832,5687847988198592380965,592867741295430227919600
> %N A177234 a(n) = binomial(n^2, n)/(n+1) if n+1 divides binomial(n^2, n), otherwise a(n) = -1.
> %C A177234 Binomial(n^2, n)/(n+1) is an integer for 2 <= n <= 4000. When is the next time this divis\
> ion fails (if any)?
> %D A177234 H. Gupta and S. P. Khare, On C(k^2,k) and the product of the first k primes, Publ. Fac. E\
> lectrotechn. Belgrade, Ser. Math. Phys. 25-29 (1977) 577-598.
> %e A177234 a(3) = 21 because binomial(9,3)/(3+1) = 84/4 = 21.
> %p A177234 with(numtheory):n0:=25:T:=array(1..n0-1):for n from 2 to n0 do: T[n-1]:= binomial(n*n,n)/\
> (n+1):od:print(T):
> %Y A177234 Cf. A014062 A123312
> %K A177234 sign,new
> %O A177234 0,3
> %A A177234 Michel Lagneau (mn.lagneau2(AT)orange.fr), May 05 2010, May 08 2010
>
> Can someone find further terms (beyond n=1) where
> the division fails?
>
> Neil
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>