[seqfan] Re: Divisibility and Binomial Coefficients

[Max Alekseyev]

All integer values of a rational function can be computed as follows.

Suppose we have a rational function R(x) = F(x) / G(x) where F(x) and
G(x) are polynomials with integer coefficients.
Without loss of generality we can assume that these polynomials are
coprime (as canceling their common factors does not affect R(x)).

Therefore, there exist polynomials u(x) and v(x) (that can be found by
extended Euclidean algorithm) with rational coefficients such that

u(x) * F(x) + v(x) * G(x) = 1

Multiplying this identity by a suitable non-zero integer m, we obtain
the identity:

U(x) * F(x) + V(x) * G(x) = m

where U(x)=m*u(x) and V(x)=m*v(x) are polynomials with integer coefficients.

Now, if integer n is such that R(n) is integer, then from the above
identity it follows that G(n) divides m.
Hence, the problem is reduced to finding all integers n such that G(n)
divides m.
Clearly, the number of such integers does not exceed 2 times (number
of divisors of m) times (degree of G).

Straightforward approach to finding them is to let d go over positive
and negative divisors of m, find all integer zeros of the polynomial
G(x)-d, for for each such zero z check whether G(z) divides F(z). That
will find all the required values of n, since each such n is a zero of
G(x)-d (i.e., G(n)=d) for some divisor d of m.

However, in practice this approach may be time consuming since the
value of m (and the number of its divisors) may be rather large.

Applying the described approach to Stefan's problem (which is now
given in A140601), I've got that for a<b<=13, only the following pairs
give non-trivial values of n such that C(n,a)+C(n,b) divides C(n,a+b)
(moreover, listed values of n are complete for each pair):

[3, 4]: 104
[3, 5]: 19
[5, 6]: 359, 2309
[5, 7]: 41
[6, 7]: 34
[7, 8]: 89
[7, 9]: 527
[11, 12]: 4619

Similarly, for b=a+1, only the following a<=24 yield non-trivial
values of n (each line is complete):

3: 104
5: 359, 2309
6: 34
7: 89
11: 4619
18: 8644
19: 2729
20: 398

And for b=a+2, only the following a<=20 yield non-trivial values of n
(each line is complete):

3: 19
5: 41
7: 527
12: 495
15: 1845

b=a+3 yields no values of n for a<=14.

Regards,
Max

On Mon, May 5, 2008 at 5:03 PM,  <franktaw at netscape.net> wrote:
> I tried looking at this with Legendre's theorem, and got
> nowhere with it.
>
> Here's one idea: if we fix a and b, the expression
> C(n,a+b) / (C(n,a) + C(n,b))
> is a rational function in n.  From this, one can prove that certain
> combinations of a and b are not possible.  1,2 is one such.
>
> I suspect from this that any given a and b will have solutions for
> only finitely many n.  Perhaps at most one.  I don't see how to
> get a start at proving this, however.
>
> I also suspect that there are solutions with differences of more
> than 2 between a and b.  Perhaps someone could do an
> intensive search for differences of 3.
>
> Franklin T. Adams-Watters
>
> -----Original Message-----
> From: Stefan Steinerberger <stefan.steinerberger at gmail.com>
>
> First, thanks for all your interest and thoughts.
> The computed numbers lead me to conjecture that
> both problems
>
> C(n,a)+C(n,a+1) | C(n,2a+1)
> C(n,a)+C(n,a+2) | C(n,2a+2)
>
> have infinitely many solutions and that Drew's observation
> about the fact that the two variables never differ by more than
> 2 is correct. Sadly, no idea for a proof (I don't suppose one
> could prove the "differ by 2" statement by using Legendre's
> theorem to count the multiplicity of prime factors of both terms?)
>
> In any case, thanks for all your interest/time/computing power,
> Stefan
>