Periodic Weighted Sums of Binomial Coefficients

Greg Dresden Washington & Lee University Lexington, VA 24450 USA

                       dresdeng@wlu.edu

Yike Li Beijing City International School Shuangjing, Chaoyang Beijing, 100022 China

                   redcedariver@hotmail.com

Abstract Using elementary methods, we establish old and new relations between binomial

coefficients, Fibonacci numbers, Catalan numbers, Pell numbers, and more.

1 Introduction

We present a general theorem on linear recurrences and we use it to produce results both old and new about weighted sums of binomial coefficients. One highlight is this first equation, which connects the Fibonacci numbers, the binomial coefficients, and the Legendre symbol:

F_{2n} = ∑_{k=0}^{n} (\frac{k}{5})\binom{2n}{n + k} = \frac{1}{5^{n}} ∑_{k=0}^{2n}(−1)^{k+1}(\frac{k}{5})\binom{4n}{2n + k}.  (1)

The first equality can also be derived from a more complicated expression of Andrews [1] from 1969, but the second equality is new.

Also of interest are the non-negative integer solutions (X_{n}, Y_{n}) to the Pell equation X^{2} − 3Y^{2} = 1. We show that

2X_{n} + 2^{n} = 3 ∑_{j=−n}^{n}(−1)^{j}\binom{2n}{n + 6j}  (2)

and also that

Y_{n} = \binom{2n}{n + 1} − \binom{2n}{n + 5} − \binom{2n}{n + 7} + \binom{2n}{n + 11} + \binom{2n}{n + 13} − ⋯  (3)

and while the formula for X_{n} follows from Merca [10], the formula for Y_{n} is new.

To provide some background, we note that we began this research project by looking at the Binet formula for F_{2n}, which is

F_{2n} = \frac{1}{\sqrt{5}} ((\frac{1 + \sqrt{5}}{2})^{2n} − (\frac{1 − \sqrt{5}}{2})^{2n}) .  (4)

Since (1 + \sqrt{5})/2 = 2 cos π/5 and (1 − \sqrt{5})/2 = 2 cos 3π/5, then the above equation becomes

F_{2n} = \frac{1}{\sqrt{5}}((2 cos π/5)^{2n} − (2 cos 3π/5)^{2n}),  (5)

and we then realized that we could apply a cosine formula to expand the above equation into a more interesting form, which eventually gave us the first part of equation (1). After applying this same technique to other sequences such as (X_{n})_{n≥0} and (Y_{n})_{n≥0} mentioned earlier, we soon recognized that the Binet formula for these sequences was not necessary; in each case we only needed the linear recurrence formula itself.

In what follows, we will establish a general theorem which covers a large class of linear recurrence sequences. To be precise, so long as the coefficients of the linear recurrence satisfy an easily-verified property, then our theorem will give us an identity involving a weighted sum of binomial coefficients as seen in equations (1), (2), and (3) in which the weights, typically 1 and −1, appear in a pattern (hence the title of our paper). Sometimes this periodic pattern of weights matches up with a Legendre or Kronecker symbol as seen in equation (1), but other times as seen in equation (3) the best way to express the pattern is to write it out directly. Furthermore, the values of these periodic weights depend only on the initial values of the linear recurrence sequence. We then use this theorem to derive new identities for the Fibonacci numbers, the Pell numbers, the Catalan numbers, and more. Many of our identities now appear in the On-Line Encyclopedia of Integer Sequences (OEIS) [13].

2 Main result

To motivate some definitions, let us return back to our numbers F_{2n}, which satisfy the equation

F_{2n} = 3F_{2(n−1)} − 1F_{2(n−2)} for n ≥ 2.  (6)

We say that (F_{2n})_{n≥0} is a linear recurrence sequence, and since each term in equation (6) is defined by its two previous terms, we say that the sequence has order 2. The set of coefficients on the right of equation (6), in this case {3, −1}, is called the signature of this linear recurrence. From equation (6) we now define the characteristic polynomial for the sequence (F_{2n})_{n≥0} to be

x^{2} − (3x − 1).

Of course, all these definitions generalize nicely to linear recurrences of arbitrary order.

Now, one of the roots of our characteristic polynomial is ((1 + \sqrt{5})/2)^{2} = (2 cos π/5)^{2}. Another way of expressing this is to say that x^{2} − (3x − 1) is the minimal polynomial for (2 cos π/5)^{2}.

With this in mind, we are ready to present our main theorem.

Theorem 1. Suppose we have a linear recurrence sequence (A_{n})_{n≥0} such that its characteristic polynomial is the minimal polynomial for (2 cos π/q)^{2} for some integer q ≥ 3. Then, we have

A_{n} = A_{0}\binom{2n}{n} + ∑_{k=1}^{n} ω_{k}\binom{2n}{n + k},  (7)

where we define ω_{k} in terms of A_{0}, A_{1}, A_{2}, … as follows: ω_{0} = 2A_{0}, and

ω_{k} = ∑_{j=0}^{k}(−1)^{j}\binom{2k − j}{j}\frac{2k}{2k − j} A_{k−j}  for k ≥ 1.  (8)

Furthermore, we have that ω_{k′} = ω_{k} for k′ ≡ ±k (mod q), and if q is even then ω_{k′} = −ω_{k} for k′ ≡ q/2 − k (mod q).

For the proof, see Section 4 at the end of this article.

We will find it useful to write out the first few values of ω_{k}. We use equation (8), along with our definition of ω_{0} as 2A_{0}, to get the values in Table 1.

ω_{0} = 2A_{0}
ω_{1} = A_{1} − 2A_{0}
ω_{2} = A_{2} − 4A_{1} + 2A_{0}
ω_{3} = A_{3} − 6A_{2} + 9A_{1} − 2A_{0}

Table 1: Initial values of ω_{k} from Theorem 1.

The coefficients of A_{n} in Table 1 appear in reverse order as sequence \underline{A127677} in the OEIS.

Now, Theorem 1 applies to a large class of linear recurrences. One such example that we will see in Section 3.4 is the third-order sequence

A_{n} = 5A_{n−1} − 6A_{n−2} + 1A_{n−3}

with signature {5, −6, 1} and characteristic polynomial x^{3} − (5x^{2} − 6x + 1), because that polynomial is the minimal polynomial for (2 cos π/q)^{2} with q = 7. For convenience, we list in Table 2 all such cases for linear recurrences with order no more than three, indexed by the corresponding values of q.

q Signature  q Signature
5 {3, −1}  10 {5, −5}
7 {5, −6, 1}  12 {4, −1}
8 {4, −2}  14 {7, −14, 7}
9 {6, −9, 1}  18 {6, −9, 3}

Table 2: All signatures of length 2 or 3 for minimal polynomials for (2 cos π/q)^{2}.

Thus, for any entry in the OEIS with one of these signatures, we can write the terms in that sequence as a weighted sum of binomial coefficients as given in equation (7) from Theorem 1. We can do the same for signatures of length 4 or more, but those are not as interesting. Let us now look at some examples.

3 Applications

3.1 The Fibonacci numbers

As mentioned above, the sequence (F_{2n})_{n≥0} has signature {3, −1} which is the first entry in our Table 2. This gives us the following formula for F_{2n} as a weighted sum of binomial coefficients.

Theorem 2. For F_{n} the Fibonacci numbers, we have

F_{2n} = ∑_{k=0}^{n} \binom{2n}{n + k}(\frac{k}{5}),  (9)

where (\frac{k}{5}) represents the Legendre symbol.

Remark 3. As pointed out by our helpful referee, the appearance of the Legendre symbol in Theorem 2 should not come as a complete surprise. If we were to apply the fairly well-known cosine equation (32) directly to our Binet formula (5) for F_{2n}, we would get

F_{2n} = \frac{1}{\sqrt{5}} ∑_{k=1}^{n} \binom{2n}{n + k} (2 cos 2kπ/5 − 2 cos 6kπ/5) .  (10)

For k a multiple of 5, we have the expression (2 cos 2kπ/5 − 2 cos 6kπ/5) equals 0, but otherwise it has the same values as the quadratic Gauss sum

g(k; 5) = ∑_{n=0}^{4} e^{2πikn^{2}/5}.

From a theorem by Berndt, Evans, and Williams [3, Theorem 1.5.2], we learn that this satisfies

g(k; 5) = (\frac{k}{5})\sqrt{5} for k not a multiple of 5,

and so using this in equation (10) would give us a direct proof of our Theorem 2.

Proof of Theorem 2. If we set A_{n} = F_{2n} then A_{n} satisfies the recurrence A_{n} = 3A_{n−1} −A_{n−2}. Thanks to Table 2, we can apply Theorem 1 with q = 5 and with initial values A_{0} = 0 (because F_{2n} = 0 at n = 0) and A_{1} = 1 (because F_{2n} = 1 at n = 1). From Table 1 we have the following values for ω_{k}:

ω_{0} = 2A_{0} = 0,
ω_{1} = A_{1} − 2A_{0} = 1
ω_{2} = A_{2} − 4A_{1} + 2A_{0} = −1

Theorem 1 also tells us that ω_{k} = ω_{5−k} = ω_{5+k}. Using this, along with the three values already given above, we conclude that ω_{k} = 1 for k ≡ 1, 4 (mod 5), and ω_{k} = −1 for k ≡ 2, 3 (mod 5), and ω_{k} = 0 for k ≡ 0 (mod 5). This means that ω_{k} has the same values as the Legendre symbol (\frac{k}{5}), and since we also have A_{0} = 0 then equation (7) of Theorem 1 gives us our desired equation (9) for A_{n} = F_{2n}.

As we mentioned above, our equation (9) for the Fibonacci numbers is not entirely new. Andrews [1] used complex numbers to show that

F_{n} = ∑_{α=−∞}^{∞}(−1)^{α}\binom{n}{⌊(n − 1 − 5α)/2⌋},

where ⌊ ⌋ represents the greatest integer function. From this, we can obtain our equation (9) with a bit of work. However, our method is both more general and more direct.

3.2 Binomial transforms of the Pell and Pell-Lucas numbers

The sequence (F_{2n})_{n≥0} from the previous section has the nice property that it is the binomial transform of the “regular” Fibonacci sequence. In other words,

F_{2n} = ∑_{i=0}^{n} \binom{n}{i}F_{i}.

The following theorem will allow us to consider two other sequences of numbers that are also binomial transforms.

Theorem 4. For A_{n} = 4A_{n−1} − 2A_{n−2} with initial values A_{0} and A_{1}, we have

A_{n} = A_{0}\binom{2n}{n} + ∑_{k=1}^{n} ω_{k}\binom{2n}{n + k},  (11)

with ω_{k} repeating modulo 8 as given below in Table 3, with ω_{0} = 2A_{0} and ω_{1} = A_{1} − 2A_{0}.

\begin{matrix}k (mod 8) & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ ω_{k} & ω_{0} & ω_{1} & 0 & −ω_{1} & −ω_{0} & −ω_{1} & 0 & ω_{1} & ω_{0} \end{matrix}

Table 3: Values of ω_{k} for signature {4, −2}.

Proof. Since the signature {4, −2} appears in Table 2, we can apply Theorem 1 with q = 8. The values for ω_{0} and ω_{1} come to us from Table 1, and the remaining values of ω_{k} follow from the conclusion of Theorem 1 which tells us that ω_{k} = ω_{8±k} and ω_{k} = −ω_{4−k}.

With this theorem in hand, we can now produce two results, one new and one old, about the binomial transforms of the Pell and the Pell-Lucas numbers.

Corollary 5. For P_{n} the Pell numbers 0, 1, 2, 5, 12, 29, … from \underline{A000129}, we have

∑_{i=0}^{n} \binom{n}{i}P_{i} = ∑_{k=0}^{n} (\frac{k}{8}) \binom{2n}{n + k}  (12)

where (\frac{k}{8}) represents the Kronecker symbol.

Proof. If we set A_{n} equal to the binomial transform of P_{n} as seen on the left of equation (12), then the sequence (A_{n})_{n≥0} begins with 0, 1, 4, 14, 48, 164, … and is given by \underline{A007070} where we also learn that it has signature {4, −2}. Hence, we can apply Theorem 4 with ω_{0} = 2A_{0} = 0 and ω_{1} = A_{1} − 2A_{0} = 1. Furthermore, Table 3 from Theorem 4 becomes

\begin{matrix}k (mod 8) & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ ω_{k} & 0 & 1 & 0 & −1 & 0 & −1 & 0 & 1 & 0 \end{matrix}

and from this we see that ω_{k} = (\frac{k}{8}), as desired.

Corollary 6. For Q_{n} the Pell-Lucas numbers 2, 2, 6, 14, 34, 81, … from \underline{A002203}, we have

∑_{i=0}^{n} \binom{n}{i}Q_{i} = 2\binom{2n}{n} + 4 ∑_{j≥1}(−1)^{j}\binom{2n}{n + 4j}.  (13)

Proof. The binomial transform of Q_{n} is 2, 4, 12, 40, 136, …, which is the sequence \underline{A056236} with signature {4, −2}. Hence, if we let A_{n} equal the binomial transform of Q_{n} as seen on the left of equation (13), then we can again apply Theorem 4, this time with ω_{0} = 2A_{0} = 4 and ω_{1} = A_{1} − 2A_{0} = 0. Thus, Table 3 from Theorem 4, starting at k = 1, becomes

\begin{matrix}k (mod 8) & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ ω_{k} & 0 & 0 & 0 & −4 & 0 & 0 & 0 & 4 \end{matrix}

and from this we obtain our desired formula.

We note that Corollary 6 is not a new result. From Merca [10, Corollary 8] we have the formula

(2 + \sqrt{2})^{n} + (2 − \sqrt{2})^{n} = 2\binom{2n}{n} + 4 ∑_{j≥1}(−1)^{j}\binom{2n}{n + 4j},

and as seen in \underline{A056236} the binomial transform of Q_{n} is indeed equal to (2+\sqrt{2})^{n}+(2−\sqrt{2})^{n}.

As a special case of Corollary 6, we have the following relationship between a weighted sum of binomial coefficients (on the left) and a periodic weighted sum of binomial coefficients (on the right).

Corollary 7. For Q_{n} the Pell-Lucas numbers 2, 2, 6, 14, 34, 81, … as given by \underline{A002203}, we have

∑_{i=0}^{4n} \binom{4n}{i}Q_{i} = 2(−1)^{n} ∑_{j=0}^{2n}(−1)^{j}\binom{8n}{4j}.  (14)

Proof. We can split up the right-hand side of equation (14) as follows:

2(−1)^{n} ∑_{j=0}^{n−1}(−1)^{j}\binom{8n}{4j} + 2\binom{8n}{4n} + 2(−1)^{n} ∑_{j=n+1}^{2n}(−1)^{j}\binom{8n}{4j}.

In the first sum we replace j with n − j, and in the second sum we replace j with n + j, giving us

2(−1)^{n} ∑_{j=1}^{n}(−1)^{n−j}\binom{8n}{4n − 4j} + 2\binom{8n}{4n} + 2(−1)^{n} ∑_{j=1}^{n}(−1)^{n+j}\binom{8n}{4n + 4j}.

We now use the symmetry of the binomial coefficients to combine the two sums to obtain

2\binom{8n}{4n} + 4 ∑_{j≥1}(−1)^{j}\binom{8n}{4n + 4j},

and by equation (13) in Corollary 6 this is equal to ∑_{i=0}^{4n} \binom{4n}{i}Q_{i}, as desired.

3.3 Solutions to Pell’s equation

The non-negative integer solutions (X_{n}, Y_{n}) to the Pell equation X^{2} − 3Y^{2} = 1 are given by \underline{A001075} for X_{n}, and \underline{A001353} for Y_{n}, where the first sequence begins 1, 2, 7, 26, 97, …, and the second is 0, 1, 4, 15, 56, . . .. These are well-known linear recurrence sequences, and both of them have signature {4, −1} which corresponds to q = 12 in Table 2. With this in mind, we present the following theorem and then we show how it gives us the equations (2) and (3) for X_{n} and Y_{n} as mentioned in the introduction to this paper.

Theorem 8. For A_{n} = 4A_{n−1} − A_{n−2} with initial values A_{0} and A_{1}, we have

A_{n} = A_{0}\binom{2n}{n} + ∑_{k=1}^{n} ω_{k}\binom{2n}{n + k},  (15)

with ω_{k} repeating modulo 12 as given below in Table 4, with ω_{1} = A_{1} − 2A_{0} and ω_{2} = A_{0}.

\begin{matrix}k (mod 12) & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ ω_{k} & 2ω_{2} & ω_{1} & ω_{2} & 0 & −ω_{2} & −ω_{1} & −2ω_{2} & −ω_{1} & −ω_{2} & 0 & ω_{2} & ω_{1} & 2ω_{2} \end{matrix}

Table 4: Values of ω_{k} for signature {4, −1}.

Proof. Thanks to Table 2, we can apply Theorem 1 with q = 12. The values ω_{0} = 2A_{0} and ω_{1} = A_{1}−2A_{0} are given to us in Table 1. As for ω_{2}, we see in Table 1 that ω_{2} = A_{2}−4A_{1}+2A_{0}, but since A_{2} = 4A_{1}−A_{0} then this becomes just ω_{2} = A_{0}. Hence, we can write ω_{0} = 2ω_{2}. The remaining values of ω_{k} follow from the conclusions of Theorem 1 that ω_{k} = ω_{12±k} = −ω_{6−k}, allowing us to fill in the rest of Table 4.

Thanks to Theorem 8, we have the following corollary.

Corollary 9. For X_{n} and Y_{n} the non-negative solutions to X^{2} − 3Y^{2} = 1, then X_{n} satisfies equation (2) and Y_{n} satisfies equation (3).

As we mentioned in the introduction, equation (2) for X_{n} comes from Merca [10]; to be precise, it follows from his Theorem 3 with n = 6. However, we believe that our equation (3) for Y_{n} is new.

Proof of Corollary 9. We begin with X_{n}, which has X_{0} = 1 and X_{1} = 2. From Theorem 8, we have ω_{1} = 0 and ω_{2} = 1 and so Table 4 gives us the following values:

\begin{matrix}k (mod 12) & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ ω_{k} & 2 & 0 & 1 & 0 & −1 & 0 & −2 & 0 & −1 & 0 & 1 & 0 & 2 \end{matrix}

To reveal a hidden pattern, we write ω_{k} as the sum of two periodic sequences, as shown here. We have dropped some of the 0’s for legibility.

k (mod 12)  0 1 2 3 4 5 6 7 8 9 10 11 12
ω_{k}  2 0 1 0 −1 0 −2 0 −1 0 1 0  2
first sequence −1  1  −1  1  −1  1  −1
second sequence 3  −3  3

Thus, equation (15) tells us that

X_{n} = \binom{2n}{n} − ∑_{i=1}^{n}(−1)^{i}\binom{2n}{n + 2j} + 3 ∑_{j=1}^{n}(−1)^{j}\binom{2n}{n + 6j}.  (16)

From Lewis [9, p. 200], after adjusting for his notation we have the following formula:

2^{2n} sin^{2n} z = \binom{2n}{n} + ∑_{h=1}^{n}(−1)^{h}\binom{2n}{n + h}2 cos 2hz,

and if we let z = π/4, divide by 2, and then renumber the sum, we obtain

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

(We could also obtain this from Merca [10, Corollary 8]). When we substitute this into equation (16) and multiply by two, we get

2X_{n} = 3\binom{2n}{n} − 2^{n} + 3 ∑_{j=1}^{n}(−1)^{j} · 2\binom{2n}{n + 6j}.

Since 2\binom{2n}{n+6j} = \binom{2n}{n−6j} + \binom{2n}{n+6j}, we can re-write that sum on the right to include the terms for j < 0, and as for the j = 0 term we simply bring 3\binom{2n}{n} into the sum. After simplifying, this gives us equation (2) at the beginning of this paper.

As for Y_{n}, we have Y_{0} = 0 and Y_{1} = 1 and so Theorem 8 tells us that in this case we have ω_{1} = 1 and ω_{2} = 0. Thanks to Table 4, we quickly assemble the following chart.

\begin{matrix}k (mod 12) & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ ω_{k} & 0 & 1 & 0 & 0 & 0 & −1 & 0 & −1 & 0 & 0 & 0 & 1 & 0 \end{matrix}

From this we immediately get the expression for Y_{n} in equation (3) from the introduction.

3.4 Catalan numbers and a linear recurrence of order three

For a particular class of linear recurrences, we have the following theorem.

Theorem 10. For A_{n} a sequence satisfying A_{n} = 5A_{n−1} − 6A_{n−2} + A_{n−3} and with initial values A_{0}, A_{1}, and A_{2}, we have

A_{n} = A_{0}\binom{2n}{n} + ∑_{k=1}^{n} ω_{k}\binom{2n}{n + k},  (17)

with

ω_{i} = \begin{cases}2A_{0}, & for k ≡ 0 (mod 7); \\ A_{1} − 2A_{0}, & for k ≡ 1, 6 (mod 7); \\ A_{2} − 4A_{1} + 2A_{0}, & for k ≡ 2, 5 (mod 7); \\ 3A_{1} − A_{0} − A_{2}, & for k ≡ 3, 4 (mod 7). \end{cases}  (18)

Proof. Since the signature {5, −6, 1} appears in Table 2, we can apply Theorem 1, this time with q = 7. The values for ω_{0}, ω_{1}, and ω_{2} are given to us in Table 1, and from that same equation we also have

ω_{3} = A_{3} − 6A_{2} + 9A_{1} − 2A_{0},

but since A_{3} = 5A_{2} − 6A_{1} + A_{0} then this becomes

ω_{3} = −A_{2} + 3A_{1} − A_{0},

as desired. Finally, Theorem 1 also tells us that ω_{k} = ω_{7±k}, thus concluding our proof.

With this in hand, we can present two new results related to Catalan paths.

Corollary 11. For B_{n} the numbers 1, 1, 2, 5, 14, 42, … from \underline{A080937}, we have

B_{n} = \frac{1}{n + 1}\binom{2n}{n} + ∑_{j≥1} 4\binom{2n}{n + 7j} − ∑_{j≥1} \binom{2n + 2}{n + 7j + 1}  (19)

where the first term on the right is also known as the nth Catalan number (\underline{A000108}).

Proof. From \underline{A080937} we learn that the numbers B_{n} have the recurrence B_{n} = 5B_{n−1} − 6B_{n−2} + B_{n−3}, and this signature {5, −6, 1} appears in Table 2 with q = 7. Thus, we can once again apply Theorem 1 (this time with q = 7) and from Table 1 we learn that ω_{0}, ω_{1}, ω_{2}, and ω_{3} are 2, −1, 0, 0 respectively. The remaining values of ω_{k} follow from the fact that ω_{k} = ω_{7±k}. Here are those values for ω_{k}, starting at k = 0.

\begin{matrix}k (mod 7) & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ ω_{k} & 2 & −1 & 0 & 0 & 0 & 0 & −1 & 2 \end{matrix}

Thus, equation (7) from Theorem 1 tells us that

B_{n} = \binom{2n}{n} − \binom{2n}{n + 1} + ∑_{j≥1} (2\binom{2n}{n + 7j} − \binom{2n}{n + 7j − 1} − \binom{2n}{n + 7j + 1}) .

A simple calculation verifies that \binom{2n}{n} − \binom{2n}{n+1} is equal to the Catalan number \frac{1}{n+1} \binom{2n}{n}, and as for the expression inside the sum, we can easily verify that

2\binom{2n}{n + 7j} − \binom{2n}{n + 7j − 1} − \binom{2n}{n + 7j + 1} = 4\binom{2n}{n + 7j} − \binom{2n + 2}{n + 7j + 1}.

This gives us equation (19) for B_{n}, as desired.

From Corollary 11 we can obtain an unexpected equation for a type of Catalan paths. We recall [7, p. 152] that the nth Catalan number (call it C_{n}) counts the total number of non-negative paths of length 2n that start and end at 0, with each step ±1. Our numbers B_{n} from Corollary 11, as described in \underline{A080937}, count the total number of such paths that have maximum height 5 or less. Hence, if we re-write equation (19), recalling again that C_{n} = \frac{1}{n+1} \binom{2n}{n}, we obtain the following.

Corollary 12. The number of Catalan paths of length 2n with maximum height at least 6 is

∑_{j≥1} (\binom{2n + 2}{n + 7j + 1} − 4\binom{2n}{n + 7j}) .  (20)

This formula gives us the (new) sequence \underline{A359311}, which begins 0, 0, 0, 0, 0, 0, 1, 12, 89, . . .. We can only imagine that there is an easy combinatorial proof of our Corollary 12, although we are not clever enough to find it.

3.5 More binomial transforms

As we saw in Section 3.2, the binomial transforms of certain sequences (in that case, the Pell and Pell-Lucas sequences) can be expressed as weighted sums of binomial coefficients. We can do the same for the binomial transform of F_{2n} and L_{2n}. These transforms are given in \underline{A093131} and \underline{A020876} respectively, and both have signature \{5, −5\}. This leads us to the following theorem and its three corollaries.

Theorem 13. For A_{n} = 5A_{n−1} − 5A_{n−2} with initial values A_{0} and A_{1}, we have

A_{n} = A_{0}\binom{2n}{n} + ∑_{k=1}^{n} ω_{k}\binom{2n}{n + k},  (21)

with ω_{k} repeating modulo 10 as given in Table 5, with ω_{0} = 2A_{0}, ω_{1} = A_{1} − 2A_{0}, and ω_{2} = A_{1} − 3A_{0}.

\begin{matrix}k (mod 10) & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ ω_{k} & ω_{0} & ω_{1} & ω_{2} & −ω_{2} & −ω_{1} & −ω_{0} & −ω_{1} & −ω_{2} & ω_{2} & ω_{1} & ω_{0} \end{matrix}

Table 5: Values of ω_{k} for signature {5, −5}.

Proof. Since the signature {5, −5} appears in Table 2, we apply Theorem 1 with q = 10. The values for ω_{0} and ω_{1} are given to us in Table 1. As for ω_{2}, we learn from Table 1 that ω_{2} = A_{2} − 4A_{1} + 2A_{0}, but since A_{2} = 5A_{1} − 5A_{0} then this becomes ω_{2} = A_{1} − 3A_{0}. The other values follow from the conclusion of Theorem 1 which tells us that ω_{k} = ω_{10±k} and that ω_{k} = −ω_{5−k}.

We can now prove two nice identities for the binomial transforms of F_{2n} and of L_{2n}, respectively. Both of these next two corollaries feature an equality between a weighted sum of binomial coefficients (on the left) and a periodic weighted sum of binomial coefficients (on the right).

Corollary 14. For F_{n} the Fibonacci numbers, we have

∑_{i=0}^{n} \binom{n}{i}F_{2i} = ∑_{k=0}^{n}(−1)^{k+1} (\frac{k}{5}) \binom{2n}{n + k}  (22)

and also

5^{n}F_{2n} = ∑_{k=0}^{2n}(−1)^{k+1} (\frac{k}{5}) \binom{4n}{2n + k},  (23)

where (\frac{k}{5}) represents the Legendre symbol.

We note that both of the formulas in Corollary 14 are new, and equation (23) gives us the second part of equation (1) from the opening paragraph of this paper.

Proof. The binomial transform of F_{2n} on the left of equation (22) is 0, 1, 5, 20, 75, …, as seen in \underline{A093131} where we also learn that it has signature \{5, −5\}. If we let A_{n} equal that binomial transform, then we can apply Theorem 13, and since A_{0} = 0 and A_{1} = 1 we will get ω_{0} = 0 and ω_{1} = ω_{2} = 1. Thus, Table 5 from Theorem 13 becomes

\begin{matrix}k (mod 10) & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ ω_{k} & 0 & 1 & 1 & −1 & −1 & 0 & −1 & −1 & 1 & 1 & 0 \end{matrix}

and from this we see that ω_{k} = (−1)^{k+1}(\frac{k}{5}), giving us equation (22).

As for equation (23), we replace n with 2n in equation (22) and we note from \underline{A093131} that ∑_{i=0}^{2n} \binom{2n}{i}F_{2i} is equal to 5^{n}F_{2n}.

Corollary 15. For L_{n} the Lucas numbers, we have

∑_{i=0}^{n} \binom{n}{i}L_{2i} = 5 ∑_{j≥0}(−1)^{j}\binom{2n}{n + 5j} − 5\binom{2n − 1}{n}  for n ≥ 1,  (24)

and also

5^{n}L_{2n} = 5 ∑_{j≥0}(−1)^{j}\binom{4n}{2n + 5j} − 5\binom{4n − 1}{2n}  for n ≥ 1.  (25)

We note that these two identities are not new; equation (24) follows from Merca [10, Corollary 8], and equation (25) is just a special case of (24). However, our approach is rather different from the one in Merca’s article.

Proof. If we let A_{n} equal the binomial transform of L_{2n} then the sequence (A_{n})_{n≥0} begins with 2, 5, 15, 50, 175, … and is given by \underline{A020876} where we learn that it has signature \{5, −5\}. Hence, we can once again apply Theorem 13, and since A_{0} = 2 and A_{1} = 5 in this case, we get ω_{0} = 4, ω_{1} = 1, and ω_{2} = −1. Thus, Table 5 from Theorem 13 gives us the following table, where we have written ω_{k} as a sum of two periodic sequences in order to reveal a hidden pattern.

k (mod 10)  1 2 3 4 5 6 7 8 9 10
ω_{k}  1 −1 1 −1 −4 −1 1 −1 1 4
first sequence 1 −1 1 −1 1 −1 1 −1 1 −1
second sequence  −5  5

As a result, Theorem 13 gives us

∑_{i=0}^{n} \binom{n}{i}L_{2i} = 2\binom{2n}{n} − ∑_{k=1}^{n}(−1)^{k}\binom{2n}{n + k} + 5 ∑_{j≥1}(−1)^{j}\binom{2n}{n + 5j}.  (26)

If we adjust the right-hand side so that the two sums each start at 0 instead of 1, then this becomes

∑_{i=0}^{n} \binom{n}{i}L_{2i} = −2\binom{2n}{n} − ∑_{k=0}^{n}(−1)^{k}\binom{2n}{n + k} + 5 ∑_{j≥0}(−1)^{j}\binom{2n}{n + 5j},  (27)

and we do this because that middle sum is easily converted to a well-known identity. To be precise, if we replace \binom{2n}{n+k} with \binom{2n}{n−k}, and then replace k with n − k, then the middle sum in equation (27) satisfies

∑_{k=0}^{n}(−1)^{k}\binom{2n}{n + k} = ∑_{k=0}^{n}(−1)^{k}\binom{2n}{n − k} = ∑_{k=0}^{n}(−1)^{n−k}\binom{2n}{k},

and this can be simplified further to

(−1)^{n} ∑_{k=0}^{n}(−1)^{k}\binom{2n}{k}.

From Benjamin and Quinn [2, Identity 168] we learn that the above sum is equal to \binom{2n−1}{n}, and so we can now write equation (26) as

∑_{i=0}^{n} \binom{n}{i}L_{2i} = −2\binom{2n}{n} − \binom{2n − 1}{n} + 5 ∑_{j≥0}(−1)^{j}\binom{2n}{n + 5j}.  (28)

It is relatively easy to show that −2\binom{2n}{n} − \binom{2n−1}{n} is equal to −5\binom{2n−1}{n} so long as n ≥ 1, and thus we obtain our desired equation (24).

As for equation (25), we replace n with 2n in equation (24) and we note from \underline{A020875} that ∑_{i=0}^{2n} \binom{2n}{i}L_{2i} is equal to 5^{n}L_{2n}. From this we can obtain equation (25), as desired.

As a result of Corollary 15, we can produce the following nice result about sums of every tenth binomial coefficient. As far as we can tell, this is a new formula.

Corollary 16. For L_{n} the Lucas numbers and for n ≥ 1, we have

∑_{j=−n}^{n} \binom{4n}{2n + 10j} = (2^{4n−1} + L_{4n} + 5^{n}L_{2n})/5.  (29)

Proof. We begin with a result from Shibukawa [12, equation (1.15)] with r = 2, giving us

L_{4n} = −2^{4n−1} + \frac{5}{2} ∑_{j=−n}^{n} \binom{4n}{2n + 5j}.

We now re-write our equation (25) from Corollary 15 by using the identity −5\binom{4n−1}{2n} = −\frac{5}{2} \binom{4n}{2n}; this gives us

5^{n}L_{2n} = −\frac{5}{2}\binom{4n}{2n} + 5 ∑_{j=0}^{n}(−1)^{j}\binom{4n}{2n + 5j} for n ≥ 1,

and since each \binom{4n}{2n+5j} is equal to \binom{4n}{2n−5j}, then we can re-write this again as

5^{n}L_{2n} = \frac{5}{2} ∑_{j=−n}^{n}(−1)^{j}\binom{4n}{2n + 5j} for n ≥ 1.

When we add this to Shibukawa’s equation we get, after re-indexing our sum,

L_{4n} + 5^{n}L_{2n} = −2^{4n−1} + 5 ∑_{j=−n}^{n} \binom{4n}{2n + 10j},

and this gives us our desired equation (29).

4 Proof of Theorem 1

We now give the rather technical proof of our main result.

Proof of Theorem 1. For (A_{n})_{n≥0} a linear recurrence as given, we let f(x) represent its characteristic polynomial and we let M be its order (equivalently, M is the degree of f(x)). We are given that this f(x) is the minimal polynomial for (2 cos π/q)^{2} for some integer q ≥ 3, and since (2 cos π/q)^{2} = 2 cos 2π/q+2, then f(2x+2) is the minimal polynomial for x = cos 2π/q. It is well known [5, 8] that f(2x + 2) has degree M = ϕ(q)/2.

Furthermore, borrowing notation from Gürtaş [5], if we set

S(q) = {p_{i} | gcd(p_{i}, q) = 1 and 1 ≤ p_{i} < q/2}

then the complete and distinct set of roots [14] for f(2x + 2) are {cos 2πp_{i}/q | p_{i} ∈ S(q)} and so likewise for f(x) the roots are {(2 cos πp_{i}/q)^{2} | p_{i} ∈ S(q)}. Now that we have the M distinct roots of the characteristic polynomial f(x), we know from Dubeau et. al. [4, Theorem 1] or Kelly and Peterson [6, Theorem 3.7] that the Binet formula for A_{n} is

A_{n} = α_{1}(2 cos πp_{1}/q)^{2n} + ⋯ + α_{M}(2 cos πp_{M}/q)^{2n} = ∑_{i=1}^{M} α_{i}(2 cos πp_{i}/q)^{2n},  (30)

with p_{1}, … p_{M} the distinct elements in the set S(q) and with α_{1}, …, α_{M} determined by the initial values A_{0}, A_{1}, A_{2}, … A_{M−1}.

We now call upon the well-known trigonometric power formula [15] for cosine,

cos^{2n} θ = \frac{1}{2^{2n}} \binom{2n}{n} + \frac{1}{2^{2n−1}} ∑_{k=0}^{n−1} \binom{2n}{k} cos 2(n − k)θ.  (31)

We simplify the above sum by replacing k with n − k and noting that \binom{2n}{n−k} = \binom{2n}{n+k}. After doing so, and then multiplying through by 2^{2n}, we obtain

(2 cos θ)^{2n} = \binom{2n}{n} + ∑_{k=1}^{n} \binom{2n}{n + k}2 cos 2kθ.  (32)

Next, we apply equation (32) to each cosine in equation (30) to obtain

A_{n} = ∑_{i=1}^{M} α_{i} (\binom{2n}{n} + ∑_{k=1}^{n} \binom{2n}{n + k}2 cos 2kπp_{i}/q) .

We pull out the first term, and switch the order of summation on the rest, to get

A_{n} = \binom{2n}{n} ∑_{i=1}^{M} α_{i} + ∑_{k=1}^{n} ω_{k}\binom{2n}{n + k},  (33)

where ω_{k} is defined as

ω_{k} = ∑_{i=1}^{M} α_{i} 2 cos 2kπp_{i}/q.  (34)

For the first term in equation (33), we note that if we take n = 0 in equation (30), we obtain

A_{0} = ∑_{i=1}^{M} α_{i},

and so equation (33) becomes

A_{n} = A_{0}\binom{2n}{n} + ∑_{k=1}^{n} ω_{k}\binom{2n}{n + k},  (35)

as desired.

We now turn our attention to establishing equation (8) for ω_{k}. For this, we will use the Chebyshev polynomials T_{k}(x) which have the useful property that T_{k}(cos θ) = cos kθ. We can write them as

T_{k}(x) = ∑_{j=0}^{⌊k/2⌋} t_{k,j}x^{k−2j}  (36)

such that our Chebyshev coefficients t_{k,j}, as seen in the CRC handbook [16, § 6.10.6], satisfy

t_{k,j} = (−1)^{j}\binom{k − j}{j}2^{k−2j−1} \frac{k}{k − j}  (37)

so long as k − j ≠ 0. From our summation in equation (36), we see that 0 ≤ j ≤ ⌊k/2⌋, so the only case when k − j = 0 is when both j and k are zero, and for that we define t_{0,0} = 1.

Next, we define S_{k}(x) as

S_{k}(x) = 2T_{2k}(x/2),  (38)

which from equation (36) gives us that

S_{k}(x) = 2 ∑_{j=0}^{k} t_{2k,j} \frac{x^{2k−2j}}{2^{2k−2j}}  (39)

and furthermore we have that S_{k}(2 cos θ) = 2T_{2k}(cos θ) and thanks to the property of the Chebyshev polynomials, this equals 2 cos 2kθ. This means

S_{k}(2 cos πp_{i}/q) = 2 cos 2kπp_{i}/q,

and so our formula for ω_{k} in equation (34) becomes

ω_{k} = ∑_{i=1}^{M} α_{i} · S_{k}(2 cos πp_{i}/q).

Thanks to equation (39) this becomes

ω_{k} = ∑_{i=1}^{M} α_{i} · 2 ∑_{j=0}^{k} \frac{t_{2k,j}}{2^{2k−2j}} (2 cos πp_{i}/q)^{2k−2j}.

We switch the order of summation to get

ω_{k} = 2 ∑_{j=0}^{k} \frac{t_{2k,j}}{2^{2k−2j}} ∑_{i=1}^{M} α_{i}(2 cos πp_{i}/q)^{2k−2j},

and thanks to our formula for A_{n} in equation (30), this becomes

ω_{k} = 2 ∑_{j=0}^{k} \frac{t_{2k,j}}{2^{2k−2j}} A_{k−j}.

We recall from our discussion above that t_{0,0} = 1 so this tells us that ω_{0} = 2A_{0}. For k ≥ 1, we can use equation (37) to replace the coefficients t_{2k,j}, and so the above equation becomes

ω_{k} = ∑_{j=0}^{k}(−1)^{j}\binom{2k − j}{j}\frac{2k}{2k − j} A_{k−j} for k ≥ 1,

as desired.

Next, since

cos 2(q ± k)πp_{i}/q = cos(2πp_{i} ± 2kπp_{i}/q) = cos 2kπp_{i}/q,

then from our definition of ω_{k} in equation (34) we have that ω_{k′} = ω_{k} for k′ ≡ ±k (mod q), as desired.

Finally, if q is even, then for k′ ≡ q/2 − k (mod q) we have

cos 2k′πp_{i}/q = cos 2(q/2 − k)πp_{i}/q = cos(πp_{i} + 2kπp_{i}/q) = − cos 2kπp_{i}/q,

where the last equality holds because since q is even, then p_{i} ∈ S(q) must be odd.

5 Conclusion

We are rather surprised by how many different identities with weighted sums of binomial coefficients we could obtain from our Theorem 1, all thanks to the cosine formula in equation (32) for (2 cos θ)^{2n}. There is a similar formula for (2 cos θ)^{2n+1}, and we encourage the reader to explore the additional identities that this could provide.

We might want to think about reversing the problem. Given a periodic sequence (ω_{k})_{k≥0}, what can we say about the periodic weighted sum

A_{n} = ∑_{k=1}^{n} ω_{k}\binom{2n}{n + k},

and under what conditions on ω_{k} will (A_{n})_{n≥1} be a linear recurrence sequence?

Also, while Table 2 only covers signatures of length 2 or 3, our Theorem 1 applies to all signatures corresponding to minimal polynomials for (2 cos π/q)^{2} for all q ≥ 3. For q = 11, the signature {9, −28, 35, −15, 1} has eight entries in the OEIS and it might be worthwhile to explore them. Another interesting example appears at q = 60. The coefficients of the minimal polynomial for (2 cos π/60)^{2} match up perfectly with the signature for the sequence \underline{A126569} (which is related to the Cartan matrix for the Lie group E_{8}) and so we could establish a new identity for those terms as well.

Finally, we mention in closing another result on periodic binomial sums and the Fibonacci numbers. Moser [11] gives this identity (adapted slightly to match our notation) for F_{2n}, which is a nice counterpoint to our equation (1) at the beginning of the paper:

F_{2n} = \binom{2n − 1}{n} − 2\binom{2n − 1}{n + 2} + \binom{2n − 1}{n + 4} − 2\binom{2n − 1}{n + 6} + · · · .

6 Acknowledgments

Our thanks to the editor and the referee for many helpful comments, and to Pioneer Academics for helping us to establish this research collaboration.

References

[1] George H. Andrews, Some formulae for the Fibonacci sequence with generalizations, Fibonacci Quart. 7 (1969), 113–130.

[2] Arthur T. Benjamin and Jennifer Quinn, Proofs that Really Count, Mathematical Association of America, 2003.

[3] Bruce C. Berndt, Ronald J. Evans, and Kenneth S. Williams, Gauss and Jacobi Sums, John Wiley & Sons, 1998.

[4] François Dubeau, Walter Motta, Mustapha Rachidi, and Osamu Saeki, On weighted r-generalized Fibonacci sequences, Fibonacci Quart. 35 (1997), 102–110.

[5] Yusuf Z. Gürtaş, Chebyshev polynomials and the minimal polynomial of cos(2π/n), Amer. Math. Monthly 124 (2017), 74–78.

[6] Walter Kelley and Allan Peterson, Difference Equations: An Introduction with Applications, Academic Press, 1991.

[7] Thomas Koshy, Catalan Numbers with Applications, Oxford University Press, 2008.

[8] D. H. Lehmer, A note on trigonometric algebraic numbers, Amer. Math. Monthly 40 (1933), 165–166.

[9] B. Lewis, Fibonacci numbers and trigonometry, Math. Gazette 88 (2004), 194–204.

[10] Mircea Merca, A note on cosine power sums, J. Integer Seq. 15 (2012), Article 12.5.3.

[11] Bernhard A. Moser, A novel Fibonacci pattern in Pascal’s triangle, preprint, 2018.

    Available at https://arxiv.org/abs/1811.02085.

[12] Genki Shibukawa, New identities for some symmetric polynomials, and a higher order analogue of the Fibonacci and Lucas numbers, Fibonacci Quart. 58 (2020), 200–221.

[13] N. J. A. Sloane et. al., The On-Line Encyclopedia of Integer Sequences, 2023. Published

    electronically at https://oeis.org/.

[14] William Watkins and Joel Zeitlin, The minimal polynomial of cos(2π/n), Amer. Math. Monthly 100 (1993), 471–474.

[15] Eric W. Weisstein, Trigonometric power formulas. From MathWorld—A Wolfram Web Resource, 2022. Published electronically at https://mathworld.wolfram.com/

    TrigonometricPowerFormulas.html.

[16] Daniel Zwillinger, CRC Standard Mathematical Tables and Formulae, CRC Press, 2012.

2020 Mathematics Subject Classification: Primary 11B39; Secondary 05A15, 05B45. Keywords: Fibonacci number, cosine, Catalan number, Pell number, binomial coefficient.

(Concerned with sequences \underline{A000108}, \underline{A000129}, \underline{A001075}, \underline{A001353}, \underline{A002203}, \underline{A007070}, \underline{A020875}, \underline{A020876}, \underline{A056236}, \underline{A080937}, \underline{A093131}, \underline{A126569}, \underline{A127677}, and \underline{A359311}.)

Received October 10 2022; revised versions received March 11 2023; September 7 2023; October 5 2023. Published in Journal of Integer Sequences, October 15 2023.

Return to Journal of Integer Sequences home page.