Binom eng dvi

Sums of binomial coefficients

1. 
   
   0
   
   0
   a) It follows from problem 1.3. If ∆⁰ is a triangle consisting of the first 3 rows of the 3-arithmetical Pascal triangle, then the sum of its central binomial coefficients is divisible by 3. For arbitrary a the sum under consideration contains elements of several central triangles, which are multiples of ∆⁰. So the total
   

sum is divisible by 3, too.

Another solution ([CSTTVZ]) we can derive from the identity

2k

k
k

=

i=0

_{k 2}

i
. Then

3 ^a−1

k

C

=
2k

k=0

3 ^a −1 k

k=0 i=0

_{k 2}

i

. Since 1² = 2² = 1, 0² = 0 (mod 3), the last sum modulo 3 equals the number of nonzero

elements in the first 3^a rows of the Pascal triangle. This number is calculated in the problem 2.1a), it is divisible by 3.

b) Solution of [D]. The sum is a coefficient of x³a⁻¹ in the polynomial

3^a−1

(x + 1)² (x + 1)⁴

_{(x + 1)}2(3^a−1)

(x+1)^2·3a

_x3a ^{− 1}

3
3^a−1

(x + 1)^2·3a − x a

x 1 +

_x + _x2 + _{. . .} +

_x3^a−1

⁼ (x+1)² ₋ <sup>1 · x

=</sup> x^{2 +} x ^{+ 1 =}

x
_x2·3^a ₊ 2^·3^a _{· x}2·3^a−1 ₊ 2^·3^a _{· x}2·3^a−2 _{+ . . . + 1 − x}3^a

₌ 1 2

x³ − 1

· (x − 1) .

−

.

b
In order to find this coefficient we will perform the long division of the numerator by the denominator and then multiply the result by (x 1). We do not need to find the quotient at whole, it is sufficient to perform the division till the moment when the coefficient of x³a⁻² will be found, remind that we are trying to find this coefficient modulo 3^a only. Since for b . 3 all the binomial coefficient ^2·3a are divisible by 3^a

(by Kummer’s theorem), we can collect all these coefficient in a separate sum. When we divide this sum by x³ − 1 all the coefficients of the quotient are divisible by 3^a therefore we can discard this sum. The remaining expression is


3 6
_x2·3^a ₊ 2^·3^a _{· x}2·3^a−3 ₊ 2^·3^a _{· x}2·3^a−6 _{+ . . . + 1 − x}3^a

_{x3 − 1 ·} (x ₋ 1).


−
All the exponents in the numerator are divisible by 3, hence after division by x³ − 1 all the exponents of the quotient are divisible by 3, too, and after the multiplying it by x 1, there will be no exponents of the form 3k + 2. So the coefficient that we seek equals 0 (mod 3^a).

2. 
   This problem was published in Monthly [25]. Since
   

2n + 2

n + 1

2n

— 4 _n

= 2 ·

2n + 1 2n n + 1 n

2n

— 4 _n

= −2C_n ,

then C

2n+2 2n

≡ − (mod 3). Therefore this sum is telescopic modulo 3:

^{n n}+1 ⁿ

_Ln

C_k ≡

k=1

2n + 2 2n n + 1 ⁻ n

2n

+ _n −

2n − 2

n − 1

+ . . .

2n + 2

=

n + 1

+ 1 (mod 3).

So by Kummer’s theorem we have to clarify when we have at least one carry in the addition of the number

(n + 1) with itself in base 3. It it clear that it happens only if n + 1 contains at least one 2 in base 2.

3. 
   
   p
   
   n
   
   n
   This is problem A5 of Putnam Math. Competition, 1998. Since ^{1 p} ≡ ⁽⁻¹⁾n−1 (mod p), we have
   

^Lk 1 p

L _{( 1)}ⁿ⁻¹ L^k

k

−
≡ =

[k/2] k

L

L
1 1 1

— 2 ≡ +

_Lp−1


1
₌∗

_Lp−1

1

≡ 0 (mod p).

p n

n=1

n

n=1

n

n=1

2n

n=1

n

n=1

n


2
n=p−[ ^k ]

n

n=1

The summation in the sum to the left of asterisk really starts from n = k + 1 (it is easy to check: for

2
p = 6r + 1 we have k = 4r and p − [ ^k ] = 4r + 1 = k + 1, similarly for p = 6r + 5).

4. 
   
   — −
   This statement is from [11]. Solution [CSTTVZ]. Induction on n. The base is trivial. Prove the induction step from n = n (p 1) to n. Let q = ⁿ . Since
   

p−1

−
n + p 1


p
=

_Lp−1

_{1 n}


−
,

x(p − 1)

i

i=0

x(p − 1) − i

we can rewrite the sum under consideration in the form

n n n

+ +

_Lq

+ . . . =

_{Lp−1 p n}


1

−
=

p−1

2(p−1)

3(p−1)

i

x=1 i=0

x(p−1) − i

_Lp−1

=

p− ^Lq n

1
. (11)

i=0

i

x=1

x(p−1) − i

By the problem 1.1 a) we have ^p−1 ≡ (−1)ⁱ (mod p); let ^p−1 = ap + (−1)ⁱ. By the problem 1.6 we have

^q _n

i

^{p−1 i}

i

^q _{n i}

x=1

x(p−1)−i ^≡

_i ≡ (−1)

(mod p) for i = 0, 1, . . . , p−2; let

x=1

x(p−1)−i

= bp + (−1) . Then

L
_q

p−1

_{n i}


i
= ap + (−1)

bp + (−1)ⁱ

≡ 1 + (−1) (ap + bp) =

i

x=1

x(p−1) − i

= 1+(−1)ⁱ

_q

p−1 +


L

L

i
n

— 2 · (−1)

= (−1)ⁱ

_q


2
p−1 + n

−1 (mod p ).

i

x=1

x(p−1)−i

i

x=1

x(p−1)−i

Remind that these transformations hold for 0 � i � p − 2. We can continue equality (11), by separating the summand for i = p − 1:

_Lp−1

p− ^Lq n

_Lp−2

≡ (−1)ⁱ

_q


L
p−1 + n

— 1 +

_Lq−1 _n

=

1
i=0

i

x=1

x(p−1)−i

i=0

i

x=1

x(p−1)−i

x=0

x(p−1)

_Lp−2

=

(−1)ⁱ

p−1 +

_Lp−2 _Lq


n
(−1)ⁱ

n

— (p − 1) +

_Lq−1 _n

+ .

i=0

i

i=0

x=1

x(p−1) − i

0

x=1

x(p−1)

The first sum here equals −1, because ^p−1 − ^p−1 + ^p−1 + . . . = 0. By the same reasons the second

(double) sum together with the summand

0 _n 1 2

₀ equals 0. The last sum equals 1 + p(n + 1) by the induction

hypothesis. Therefore the whole expression equals −1 + 0 − p + 1 + 1 + p(n + 1) = 1 + pn . This is exactly what we need because 1 + p(n + 1) = 1 + p(n + p − 1 + 1) ≡ 1 + pn (mod p²).

5. 
   This is result of Fleck, 1913, it is cited in [18]. Solution [CSTTVZ].
   

For p = 2 the sum is not alternating and the result is trivial. Let p be odd. We use the induction on q. The b ase follows from the statement 2.5 a). Prove the induction step from n = n − (p−1) to n. The

expression _x below denotes the summation over x in natural bounds (i.e. in bounds for which all the

binomial coefficients are correctly defined). We have

_{L n}

± (−1)^m =

L

(−1)^x

n + p


−

1
=
L

(−1)^x

_Lp−1

p − 1 n ₌

m

m:m≡j (mod p) x

xp + j

^{x i}=0 ⁱ

xp + j − i

1
_Lp−1 _{p − L}

−
=

i=0

( 1)^x

i

x

n

.

xp + j − i

By the induction hypothesis p^q−1 −1)^{x n p−1} ≡ (−1)ⁱ (mod p). Therefore


−
( _{xp+j i} ; by the problem 1.1 a) _i

x

p − 1
_Lp−1 _L

(−1)^x

<sub>n

L</sub>p−1

≡

(−1)ⁱ

L

(−1)^x

_n
(mod p^q) .

i

i=0 x

xp + j − i

i=0 x

xp + j − i

0

1

2

3
The last (double sum equals ⁿ − ⁿ + ⁿ − ⁿ + . . . = 0.

6. 
   The result of Bhaskaran (1965), it is cited in [18], solution [CSTTVZ]. Induction on n. Let
   

n n n n

f (n, j) =

j

^— j + (p − 1)

+

j + 2(p − 1)

^— j + 3(p − 1)

+ . . .

i
The base n = p + 1 is trivial, but observe that ^p+1 ≡ 1 (mod p) for i = 0, 1, p, p + 1, otherwise this binomial coefficient is divisible by p. Prove the step of induction from n = n − (p + 1) to n. By the observation above we have

n + (p + 1)

_Lp+1 _n

p + 1

L _n

j + (p − 1)k

=

i=0

j + (p − 1)k − i

_i ≡

i∈{0,1,p,p+1}

=

j + (p − 1)k − i

_{n n}

= +

_n

+

_n

+
(mod p) .

j + (p − 1)k

j − 1 + (p − 1)k j − 1 + (p − 1)(k − 1)

j − 2 + (p − 1)(k − 1)

Since f (n, j) =

(−1)^{k n} is an alternating sum, the underlined summands cancel (except the

^{k j}+^k(^p−1)

first and the last, but these summands are equal to 0 due to incorrect binomial coefficietns). So we obtain

the equalities

f (n, j) ≡ f (n , j) − f (n , j − 2) при j > 1 , f (n, 1) ≡ f (n , 1) + f (n , p − 2) .

Now the part “only if” of the problem statement follows from the induction hypothesis, and the part “if”, too: if f (n, j) ≡ 0 (mod p) for j = 1, 3, . . . , p − 2, then

f (n , p − 2) ≡ f (n , p − 4) ≡ . . . ≡ f (n , 1) ≡ −f (n , p − 2) ,


.

n . (p + 1)
from where f (n , j) ≡ 0 (mod p) for all required j, and then n . (p + 1), hence ^. .
References

The authors of many solutions are participants of the conference:

[D] Didin Maxim; [К] Krekov Dmitri;

[J] Jastin Lim Kai Ze;

[T] Teh Zhao Yang Anzo;

[CSTTVZ]

C´evid Domagoj, Stoki´c Maksim, Tanasijevii´c Ivan, Trifunovi´c Petar, Vukorepa Borna, Zˇikeli´c Ðorđe