The Last Digit of \binom{2n}{n} and ^{∑ ∑ ∑}\binom{n}{i}\binom{2n−2i}{n−i}

Walter Shur 11 Middle Road Port Washington, NY 11050 wshur @ worldnet.att.net

Submitted: June 28, 1996; Accepted: November 11, 1996. AMS subject classification (1991): Primary 05A10; Secondary 11B65.

Abstract

Let f_{n} = ∑_{i=0}^{n} \binom{n}{i}\binom{2n−2i}{n−i}, g_{n} = ∑_{i=1}^{n} \binom{n}{i}\binom{2n−2i}{n−i}. Let \{a_{k}\}_{k=1} be the set of all

positive integers n, in increasing order, for which \binom{2n}{n} is not divisible by 5, and let {b_{k}}_{k=1} be the set of all positive integers n, in increasing order, for which g_{n} is not divisible by 5. This note finds simple formulas for a_{k}, b_{k}, \binom{2n}{n} mod 10, f_{n} mod 10, and g_{n} mod 10.

Definitions

f_{n} = ∑_{i=0}^{n} \binom{n}{i}\binom{2n−2i}{n−i}; g_{n} = ∑_{i=1}^{n} \binom{n}{i}\binom{2n−2i}{n−i}

{a_{k}}_{k=1} is the set of all positive integers n, in increasing order, for which \binom{2n}{n} is not divisible by 5.

{b_{k}}_{k=1} is the set of all positive integers n, in increasing order, for which g_{n} is not divisible by 5.

u_{n} is the number of unit digits in the base 5 representation of n .

the electronic journal of combinatorics 4 (no. 2), #R16 2

Theorem 1. a_{k} is the number in base 5 whose digits represent the number k in base 3. If n ≥ 1,

\binom{2n}{n} mod 10 = \{ \begin{matrix}0 if n ∉ \{a_{k}\} \\ \begin{matrix}2 \\ 4 \\ 6 \\ 8 \end{matrix} \} if n ∈ \{a_{k}\} and u_{n} mod 4 = \{ \begin{matrix}1 \\ 2 \\ 0 \\ 3 \end{matrix} \end{matrix} .

Note that if n ∈ {a_{k}}, u_{n} is odd (even) if and only if n is odd (even).

Proof. From Lucas’ theorem [1], we have

\binom{2n}{n} ≡ \binom{N_{1}}{n_{1}}\binom{N_{2}}{n_{2}} ⋯ \binom{N_{t}}{n_{t}} mod 5,

where 2n = (N_{r} ⋯ N_{3}N_{2}N_{1})_{5}, n = (n_{s} ⋯ n_{3}n_{2}n_{1})_{5}, and t = min(r, s).

Suppose that for each i ≤ t, n_{i} ≤ 2. Then, for each i ≤ t, N_{i} = 2n_{i}. Since n_{i} = 0, 1 or 2, each term of the product\binom{N_{1}}{n_{1}}\binom{N_{2}}{n_{2}} ⋯ \binom{N_{t}}{n_{t}} is 1, 2 or 6. Hence, \binom{2n}{n} is not divisible by 5.

Suppose that for some i, n_{i} > 2. Let i_{m} be the smallest value of i for which that is true. Then, if n_{i_{m}} is 3 or 4, N_{i_{m}} is 1 or 3 (resp.). In either case, \binom{N_{im}}{n_{im}} = 0, and \binom{2n}{n} is divisible by 5.

Thus, {a_{k}} is the set of all positive integers written in base 3, but interpreted as if they were written in base 5. Since {a_{k}} is in increasing order, the first part of the theorem is proved.

Suppose now that \binom{2n}{n} is not divisible by 5. Then each term of the product\binom{N_{1}}{n_{1}}\binom{N_{2}}{n_{2}} ⋯ \binom{N_{t}}{n_{t}} is 1, 2 or 6 (according as n_{i} = 0, 1, or 2). We have, noting that \binom{2n}{n} is even,

\begin{matrix}2^{u_{n}} mod 10 = 6^{†}, 2, 4 or 8, \\ \binom{N_{1}}{n_{1}}\binom{N_{2}}{n_{2}} ⋯ \binom{N_{t}}{n_{t}} mod 10 = 6, 2, 4 or 8, \\ \binom{2n}{n} mod 10 = 6, 2, 4 or 8, \end{matrix} \} according as u_{n} mod 4 = 0, 1, 2 or 3.

Corollary 1.1.

a_{k} = k + 2 ∑_{i=1} ⌊\frac{k}{3^{i}} ⌋ 5^{i−1}.

†Equals 1 if u_{n} = 0; nevertheless, the next line follows since, if u_{n} = 0, at least one n_{i} must equal 2, making \binom{2n_{i}}{n_{i}} = 6.

Proof. Let k = (⋯ d_{3}d_{2}d_{1})_{3}, and consider a_{k} = ∑_{i=1} d_{i}5^{i−1}.

d_{1} = k − 3 ⌊\frac{k}{3} ⌋
d_{2} = ⌊\frac{k}{3} ⌋ − 3 ⌊\frac{k}{3^{2}} ⌋
d_{3} = ⌊\frac{k}{3^{2}} ⌋ − 3 ⌊\frac{k}{3^{3}} ⌋
⋮  ⋮  ⋮

Therefore,

∑_{i=1} d_{i}5^{i−1} = ∑_{i=1} (⌊\frac{k}{3^{i−1}} ⌋ − 3 ⌊\frac{k}{3^{i}} ⌋) 5^{i−1}.

Since ⌊\frac{k}{3^{i}} ⌋ 5^{i} − 3 ⌊\frac{k}{3^{i}} ⌋ 5^{i−1} = 2 ⌊\frac{k}{3^{i}} ⌋ 5^{i−1}, the corollary is proved.

Corollary 1.2. Let μ_{k} be the largest integer t such that k/3^{t} is an integer. Then,

a_{k} − a_{k−1} = \frac{5^{μ_{k}} + 1}{2}, and a_{k} = 1 + ∑_{i=2}^{k} \frac{5^{μ_{i}} + 1}{2}.

μ_{k} = m if and only if k ∈ {j3^{m}}, where j is a positive integer and j mod 3 ≠ 0.

Proof. If μ_{k} > 0, then

k = (⋯ d_{μ_{k}+1}0 ⋯ 0)_{3}; d_{μ_{k}+1} ≥ 1; and k − 1 = (⋯ (d_{μ_{k}+1} − 1)2 ⋯ 2)_{3}.

Hence,

a_{k} − a_{k−1} = 5^{μ_{k}} − 2[5^{μ_{k}−1} + 5^{μ_{k}−2} + ⋯ + 1] = \frac{5^{μ_{k}} + 1}{2}.

If μ_{k} = 0, then

k = (⋯ d_{1})_{3}; d_{1} ≥ 1; and k − 1 = (⋯ (d_{1} − 1))_{3}.

Hence,

a_{k} − a_{k−1} = 1 = \frac{5^{μ_{k}} + 1}{2}.

The remaining parts of the corollary follow immediately.

Corollary 1.3. If k > 1,

a_{k} = \begin{cases}5a_{\frac{k}{3}} & if k mod 3 = 0, \\ a_{k−1} + 1 & if k mod 3 ≠ 0. \end{cases}

Proof. If k mod 3 = 0, then k = (⋯ d_{2}0)_{3} and \frac{k}{3} = (⋯ d_{2})_{3}. Hence, a_{k} = 5a_{\frac{k}{3}} . If k mod 3 ≠ 0, then μ_{k} = 0 and from Corollary 1.2, we have a_{k} − a_{k−1} = 1.

Theorem 2. b_{k} is the number in base 5 whose digits represent the number 2k − 1 in base 3, i.e. b_{k} = a_{2k−1}. Furthermore, g_{n} mod 10 can only take on the values 1,5 or 9, as follows:

g_{n} mod 10 = \{ \begin{matrix}5 if n ∉ \{b_{k}\} \\ \begin{matrix}1 \\ 9 \end{matrix} \} if n ∈ \{b_{k}\} and u_{n} mod 4 = \{ \begin{matrix}1 \\ 3 \end{matrix} \end{matrix} .

Proof. Let F (z) = ∑_{n} f_{n}z^{n} = ∑_{n} z^{n} ∑_{i} \binom{n}{i}\binom{2n − 2i}{n − i}.

Letting t=n-i, we have

F (z) = ∑_{n} z^{n} ∑_{t} \binom{n}{t}\binom{2t}{t}

= ∑_{t} \binom{2t}{t} ∑_{n} \binom{n}{t}z^{n}

= \frac{1}{1 − z} ∑_{t} \binom{2t}{t} (\frac{z}{1 − z} )^{t} (see [2])

= \frac{1}{1 − z} \frac{1}{\sqrt{1 − \frac{4z}{1−z}}} = \frac{1}{\sqrt{1 − z}} \frac{1}{\sqrt{1 − 5z}} (see [2])

= [1 + (\frac{1}{4})\binom{2}{1}z + (\frac{1}{4})^{2}\binom{4}{2}z^{2} + ⋯][1 + (\frac{1}{4})\binom{2}{1}5z + (\frac{1}{4})^{2}\binom{4}{2}5^{2}z^{2} + ⋯].

Hence,

f_{n} = \frac{1}{4^{n}} ∑_{i=0} \binom{2i}{i}\binom{2n − 2i}{n − i}5^{i},

and

g_{n} = \frac{1}{4^{n}} ∑_{i=0} \binom{2i}{i}\binom{2n − 2i}{n − i}5^{i} − \binom{2n}{n},

= \frac{∑_{i=1} \binom{2i}{i}\binom{2n − 2i}{n − i}5^{i} − (4^{n} − 1)\binom{2n}{n}}{4^{n}}.

Thus we see that g_{n} is divisible by 5 if and only if (4^{n} − 1)\binom{2n}{n} is divisible by 5. And since g_{n} is odd, g_{n} mod 10 = 5 if and only if g_{n} is divisible by 5. 4^{n} − 1 is divisible by 5 if and only if n is even. Therefore, g_{n} mod 10 ≠ 5 if and only if n is odd and n ∈ {a_{k}}. Hence, b_{k} = a_{2k−1}, from which it follows that b_{k} is the number in base 5 whose digits represent the number 2k-1 in base 3.

Suppose that g_{n} mod 10 ≠ 5. Then \binom{2n}{n} mod 10 = c, where (since n ∈ \{a_{k}\} and n and u_{n} are odd) c is 2 or 8, according as u_{n} mod 4 = 1 or 3. Thus, for some non-negative integers j and k, 4^{n} − 1 = 10j + 3 and \binom{2n}{n} = 10k + c. Since \binom{2i}{i} is even when i ≥ 1, for some non-negative integer q we have

4^{n}g_{n} = 10q − (10j + 3)(10k + c).

Since g_{n} is odd, and 4^{n} mod 10 = 4, we have

If c=2, g_{n} mod 10 = 1;

if c=8, g_{n} mod 10 = 9.

Corollary 2.1.

b_{k} = 2k − 1 + 2 ∑_{i=1} ⌊\frac{2k−1}{3^{i}}⌋ 5^{i−1}.

Proof. This follows from Corollary 1.1, since b_{k} = a_{2k−1}.

Corollary 2.2. Let ν_{k} be the largest integer t for which \frac{(k−1)(2k−1)}{3^{t}} is an integer. Then,

b_{k} − b_{k−1} = \frac{5^{ν_{k}} + 3}{2}, and b_{k} = 1 + ∑_{i=2}^{k} \frac{5^{ν_{i}} + 3}{2}.

If m ≥ 1, ν_{k} = m if and only if k ∈ \{⌈\frac{j3^{m}+1}{2}⌉\} , where j is a positive

integer and j mod 3 ≠ 0; if m = 0, ν_{k} = m if and only if k ∈ {3j}, where j is a positive integer.

Proof.

b_{k} = a_{2k−1},
b_{k} − b_{k−1} = (a_{2k−1} − a_{2k−2}) + (a_{2k−2} − a_{2k−3}),

b_{k} − b_{k−1} = \frac{5^{μ_{2k−1}} + 1}{2} + \frac{5^{μ_{2k−2}} + 1}{2},

where μ_{k} is the largest integer t such that k/3^{t} is an integer.

Note that ν_{k} is also the largest integer t for which \frac{(2k−1)(2k−2)}{3^{t}} is an integer. Then we must have one of the following cases:

μ_{2k−1} = 0 and μ_{2k−2} = 0, or
μ_{2k−1} = ν_{k} and μ_{2k−2} = 0, or
μ_{2k−1} = 0 and μ_{2k−2} = ν_{k}.

In any of these cases,

b_{k} − b_{k−1} = \frac{5^{ν_{k}} + 3}{2}.

If m ≥ 1, at most one of (k − 1) and (2k − 1) is divisible by 3^{m}. ν_{k} = m if and only if either (k − 1) or (2k − 1) is divisible by 3^{m} but not by 3^{m+1}. Suppose m ≥ 1 and j mod 3 ≠ 0.

If j is odd, ⌈\frac{j3^{m}+1}{2}⌉ = \frac{j3^{m}+1}{2}; if k = \frac{j3^{m}+1}{2}, 2k − 1 = j3^{m}, and ν_{k} = m.

If j is even, ⌈\frac{j3^{m}+1}{2}⌉ = \frac{j3^{m}+2}{2}; if k = \frac{j3^{m}+2}{2}, k − 1 = \frac{j3^{m}}{2} , and ν_{k} = m.

It is straightforward to show the converse, that if ν_{k} = m ≥ 1, k ∈ \{⌈\frac{j3^{m}+1}{2}⌉\}.

If m = 0, ν_{k} = m if and only if neither (k − 1) or (2k − 1) is a multiple of 3. This occurs when 2k (and therefore k) is a multiple of 3.

the electronic journal of combinatorics 4 (no. 2), #R16 7

Corollary 2.3. If k ≥ 1,

b_{3k} = b_{3k−1} + 2,
b_{3k+1} = 5b_{k+1} − 4,  k mod 3 = 0,
= b_{3k} + 4,  k mod 3 ≠ 0,
b_{3k+2} = 5b_{k+1}.

Proof.

b_{3k} = a_{6k−1} = a_{6k−2} + 1 = a_{6k−3} + 2 = b_{3k−1} + 2,
b_{3k+2} = a_{6k+3} = 5a_{2k+1} = 5b_{k+1},
b_{3k+1} = a_{6k+1} = a_{6k} + 1 = 5a_{2k} + 1, and

if k mod 3 = 0,

b_{3k+1} = 5(a_{2k+1} − 1) + 1 = 5b_{k+1} − 4;

if k mod 3 ≠ 0, b_{3k+1} = 5(a_{2k−1} + 1) + 1 = 5b_{k} + 6 = b_{3k−1} + 6 = (b_{3k} − 2) + 6 = b_{3k} + 4.

Theorem 3.

f_{n} mod 10 = \{ \begin{matrix}5 if n ∉ \{a_{k}\} \\ \begin{matrix}1 \\ 3 \\ 7 \\ 9 \end{matrix} \} if n ∈ \{a_{k}\} and u_{n} mod 4 = \{ \begin{matrix}0 \\ 1 \\ 3 \\ 2 \end{matrix} \end{matrix} .

Proof. Since f_{n} = \binom{2n}{n} + g_{n}, the corollary can be proved easily by combining the results of Theorem 1 and Theorem 2.

References

[1] I. Vardi, Computational Recreations in Mathematica, Addison-Welsey, California, 1991, p.70 (4.4).

[2] H.S. Wilf, generatingfunctionology (1st ed.), Academic Press, New York, 1990, p.50 (2.5.7, 2.5.11).