Scaled Fibonacci- and Lucas-Producing Rational Polynomials

Brian Hopkins Department of Mathematics and Statistics Saint Peter’s University Jersey City, NJ 07306 USA

               bhopkins@saintpeters.edu

Aram Tangboonduangjit Mahidol University International College Mahidol University Salaya, Nakhon Pathom 73170 Thailand

                 aram.tan@mahidol.edu

Abstract

We study families of interpolating rational polynomials that produce scaled Fibonacci or Lucas numbers on certain integer values. We use the expansions of these families in binomial polynomials and other formats to establish several identities involving harmonic numbers, binomial coefficients, and various recursively defined sequences.

1 Introduction

In a previous paper [3], we considered certain interpolating polynomials defined from points involving Fibonacci numbers which led to several identities involving Fibonacci numbers, harmonic numbers, and binomial coefficients. A key part of the analysis used the polynomial

F_{k}(x) = F_{1}x^{k−1} + F_{2}x^{k−2} + ⋯ + F_{k−1}x + F_{k}  (1)

and its derivatives evaluated at x = 1. Here we consider interpolating polynomials defined from points involving scaled Fibonacci and Lucas numbers whose study makes use of (1) at x = −1, 2, −2, 3. Our investigation of other integer values of x suggests that the corresponding polynomials use defining points whose expressions are more complicated than those here. Section 2 gives the statements of our main results along with a summary of the corresponding results of the previous work [3], followed by proofs in Section 3 where (1) is prominent. In Section 4, we express the various polynomial families in terms of binomial polynomials, which informs several of the many identities given in Section 5.

The Fibonacci numbers are given by F_{0} = 0, F_{1} = 1, and F_{n} = F_{n−1} + F_{n−2} for n ≥ 2. In addition, we use their extension to negative indices, F_{−n} = (−1)^{n+1}F_{n} for n > 0. We will make frequent use of the related Lucas numbers L_{0} = 2, L_{1} = 1, L_{n} = L_{n−1} + L_{n−2} for n ≥ 2, and L_{−n} = (−1)^{n}L_{n} for n > 0. Also, we will need the following alternating sequences of Fibonacci and Lucas numbers. For n ≥ 0, let

b_{n} = \begin{cases}L_{n}, & if n is even; \\ F_{n}, & if n is odd. \end{cases}  (2)

Similarly, for n ≥ 0, let

c_{n} = \begin{cases}F_{n}, & if n is even; \\ L_{n}, & if n is odd. \end{cases}  (3)

These appear in the OEIS [4] as \underline{A005247} and \underline{A005013}, respectively.

The harmonic numbers

H_{n} = 1 + \frac{1}{2} + ⋯ + \frac{1}{n}

for n ≥ 1 with H_{0} = 0 arise in several of the identities. The polynomial results use the binomial polynomials defined by \binom{x}{0} = 1, \binom{x}{n} = 0 for integers n < 0, and \binom{x}{n} = (x)_{n}/n! for integers n > 0, where (x)_{n} denotes the falling factorial x(x − 1) ⋯ (x − n + 1). Finally, ⌊·⌋ denotes the integer floor.

2 Main results

We begin by citing the primary result of our previous work [3]. Four related results follow, each with a table of examples of the polynomial families.

Theorem 1. Given a nonnegative integer n, let P_{n}(x) be the interpolating polynomial determined by the points (i, F_{n+2+i}) for 0 ≤ i ≤ n. Then P_{n}(x) has degree n with leading coefficient 1/n!. For each integer k > n,

P_{n}(k) = F_{k+n+2} − ∑_{i=1}^{k−n} F_{i}\binom{k − i}{n}

\begin{matrix}n & P_{n}(x) \\ 0 & 1 \\ 1 & x + 2 \\ 2 & (x^{2} + 3x + 6)/2 \\ 3 & (x^{3} + 3x^{2} + 14x + 30)/6 \\ 4 & (x^{4} + 2x^{3} + 23x^{2} + 94x + 192)/24 \\ 5 & (x^{5} + 35x^{3} + 180x^{2} + 744x + 1560)/120 \\ 6 & (x^{6} − 3x^{5} + 55x^{4} + 255x^{3} + 1744x^{2} + 7308x + 15120)/720 \end{matrix}

Table 1: P_{n}(x) for small values of n.

and, for each integer k < 0,

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

Also, the polynomials P_{n}(x) satisfy and, with initial values P_{0}(x) = 1 and P_{1}(x) = x + 2, are uniquely determined by each of the following recurrence relations. For all n ≥ 1, we have

P_{n+1}(x) − P_{n}(x) − P_{n−1}(x) = \binom{x + 1}{n + 1},  (4)
P_{n+1}(x) − 3P_{n}(x − 1) + P_{n−1}(x − 2) = \binom{x − 1}{n + 1}.  (5)

This combines parts of Theorem 2.1, its proof, and Propositions 2.3 and 2.4 of the earlier paper [3]. Examples of P_{n}(x) are given in Table 1. Notice that the constant terms of these polynomials (before division by n!) are given by \underline{A078700} in the OEIS [4], which follows from the definition of P_{n}(x).

While the P_{n}(x) of Theorem 1 use a particular increasing sequence of Fibonacci numbers, the polynomials of the next theorem are determined by a particular decreasing sequence of Fibonacci numbers.

Theorem 2. Given a nonnegative integer n, let Q_{n}(x) be the interpolating polynomial determined by the points (i, F_{2n+1−i}) for 0 ≤ i ≤ n. Then Q_{n}(x) has degree n and leading coefficient (−1)^{n}/n!. For each integer k > n,

Q_{n}(k) = F_{2n−k+1} + (−1)^{n} ∑_{i=1}^{k−n} F_{−i}\binom{k − i}{n}

and, for each integer k < 0,

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

\begin{matrix}n & Q_{n}(x) \\ 0 & 1 \\ 1 & −x + 2 \\ 2 & (x^{2} − 5x + 10)/2 \\ 3 & (−x^{3} + 9x^{2} − 38x + 78)/6 \\ 4 & (x^{4} − 14x^{3} + 95x^{2} − 394x + 816)/24 \\ 5 & (−x^{5} + 20x^{4} − 195x^{3} + 1240x^{2} − 5144x + 10680)/120 \\ 6 & (x^{6} − 27x^{5} + 355x^{4} − 3105x^{3} + 19444x^{2} − 80748x + 167760)/720 \end{matrix}

Table 2: Q_{n}(x) for small values of n.

Also, the polynomials Q_{n}(x) satisfy and, with initial values Q_{0}(x) = 1 and Q_{1}(x) = −x + 2, are uniquely determined by each of the following recurrence relations. For all n ≥ 1,

Q_{n+1}(x) − 3Q_{n}(x) + Q_{n−1}(x) = (−1)^{n+1}\binom{x + 1}{n + 1},

Q_{n+1}(x) − Q_{n}(x − 1) − Q_{n−1}(x − 2) = (−1)^{n+1}\binom{x − 1}{n + 1}.  (6)

See the next section for notes on the proof. Examples of Q_{n}(x) are given in Table 2. Notice that the constant terms of these polynomials (before division by n!) are given by \underline{A052568} in the OEIS [4], which follows from the definition of Q_{n}(x).

The polynomials of the next theorem are determined by a particular increasing sequence of Fibonacci numbers scaled by certain decreasing powers of two.

Theorem 3. Given a nonnegative integer n, let R_{n}(x) be the interpolating polynomial determined by the points (i, 2^{n−1−i}F_{2n+3+i}) for 0 ≤ i ≤ n. Then R_{n}(x) has degree n and leading coefficient (−1)^{n}/n!. For each integer k > n,

R_{n}(k) = 2^{n−k−1}F_{k+2n+3} + (−1)^{n} ∑_{i=1}^{k−n} \frac{F_{i}}{2^{i+1}} \binom{k − i}{n}

and, for each integer k < 0,

R_{n}(k) = 2^{n−k−1}F_{k+2n+3} + (−1)^{n+1} ∑_{i=1}^{−k−1} 2^{i−1}F_{−i}\binom{k + i}{n}.  (7)

Also, the polynomials R_{n}(x) satisfy and, with initial values R_{0}(x) = 1 and R_{1}(x) = −x + 5,

\begin{matrix}n & R_{n}(x) \\ 0 & 1 \\ 1 & −x + 5 \\ 2 & (x^{2} − 11x + 52)/2 \\ 3 & (−x^{3} + 18x^{2} − 173x + 816)/6 \\ 4 & (x^{4} − 26x^{3} + 383x^{2} − 3622x + 17088)/24 \\ 5 & (−x^{5} + 35x^{4} − 705x^{3} + 10045x^{2} − 94814x + 447360)/120 \\ 6 & (x^{6} − 45x^{5} + 1165x^{4} − 22275x^{3} + 315634x^{2} − 2978640x + 14054400)/720 \end{matrix}

Table 3: R_{n}(x) for small values of n.

are uniquely determined by each of the following recurrence relations. For all n ≥ 1,

R_{n+1}(x) − 6R_{n}(x) + 4R_{n−1}(x) = (−1)^{n+1}\binom{x + 1}{n + 1},  (8)
R_{n+1}(x) − 4R_{n}(x − 1) − R_{n−1}(x − 2) = (−1)^{n+1}\binom{x − 1}{n + 1}.  (9)

See the next section for the proof. Examples of R_{n}(x) are given in Table 3.

The even and odd degree polynomials of the next theorem are determined separately, by Lucas and Fibonacci numbers scaled by powers of negative two, respectively. Nonetheless, they enjoy some recurrence relations independent of parity.

Theorem 4. Let n be a nonnegative integer. If n is even, let S_{n}(x) be the interpolating polynomial determined by the points (i, (−2)^{n−1−i}L_{n−i}) for 0 ≤ i ≤ n. Then S_{n}(x) has degree n and leading coefficient −5^{n/2}/n!. For each integer k > n,

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

and, for each integer k < 0,

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

If n is odd, let the points (i, (−2)^{n−1−i}F_{i−n}) for 0 ≤ i ≤ n determine the interpolating polynomial S_{n}(x). Then S_{n}(x) has degree n and leading coefficient −5^{(n−1)/2}/n!. For each integer k > n,

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

\begin{matrix}n & S_{n}(x) \\ 0 & −1 \\ 1 & −x + 1 \\ 2 & (−5x^{2} + 15x − 12)/2 \\ 3 & (−5x^{3} + 30x^{2} − 61x + 48)/6 \\ 4 & (−25x^{4} + 250x^{3} − 935x^{2} + 1670x − 1344)/24 \\ 5 & (−25x^{5} + 375x^{4} − 2225x^{3} + 6825x^{2} − 11670x + 9600)/120 \\ 6 & (−125x^{6} + 2625x^{5} − 22625x^{4} + 105375x^{3} − 294050x^{2} + 496800x − 414720)/720 \end{matrix}

Table 4: S_{n}(x) for small values of n.

and, for each integer k < 0,

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

Also, the polynomials S_{n}(x) satisfy and, with initial values S_{0}(x) = −1 and S_{1}(x) = −x + 1, are uniquely determined by each of the following recurrence relations. For all n ≥ 1,

S_{n+1}(x) + 2 · 5^{\frac{1−(−1)^{n}}{2}} S_{n}(x) + 4S_{n−1}(x) = −5^{⌊ \frac{n+1}{2} ⌋}\binom{x + 1}{n + 1},  (11)
S_{n+1}(x) − S_{n−1}(x − 2) = −5^{⌊ \frac{n+1}{2} ⌋}\binom{x − 1}{n + 1}.  (12)

See the next section for the proof. Examples of S_{n}(x) are given in Table 4.

The polynomials of the last theorem have a structure similar to those of Theorem 4 with the scaling here by powers of three.

Theorem 5. Let n be a nonnegative integer. If n is even, let T_{n}(x) be the interpolating polynomial determined by the points (i, 3^{n−1−i}L_{n+2+i}) for 0 ≤ i ≤ n. Then T_{n}(x) has degree n and leading coefficient 5^{n/2}/n!. For each integer k > n,

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

and, for each integer k < 0,

T_{n}(k) = 3^{n−k−1}L_{k+n+2} − 5^{\frac{n+2}{2}} ∑_{i=1}^{−k−1} 3^{i−1}F_{−i}\binom{k + i}{n}.

\begin{matrix}n & T_{n}(x) \\ 0 & 1 \\ 1 & −x + 2 \\ 2 & (5x^{2} − 25x + 42)/2 \\ 3 & (−5x^{3} + 45x^{2} − 166x + 270)/6 \\ 4 & (25x^{4} − 350x^{3} + 2135x^{2} − 7210x + 11664)/24 \\ 5 & (−25x^{5} + 500x^{4} − 4475x^{3} + 23800x^{2} − 78120x + 126360)/120 \\ 6 & (125x^{6} − 3375x^{5} + 41375x^{4} − 310125x^{3} + 1562300x^{2} − 5081100x + 8223120)/720 \end{matrix}

Table 5: T_{n}(x) for small values of n.

If n is odd, let the points (i, 3^{n−1−i}F_{n+2+i}) for 0 ≤ i ≤ n determine the interpolating polynomial T_{n}(x). Then T_{n}(x) has degree n and leading coefficient −5^{(n−1)/2}/n!. For each integer k > n,

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

and, for each integer k < 0,

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

Also, the polynomials T_{n}(x) satisfy and, with initial values T_{0}(x) = 1 and T_{1}(x) = −x+2, are uniquely determined by each of the following recurrence relations.

For all n ≥ 1,

T_{n+1}(x) − 3 · 5^{\frac{1−(−1)^{n}}{2}} T_{n}(x) + 9T_{n−1}(x) = (−1)^{n+1}5^{⌊ \frac{n+1}{2} ⌋}\binom{x + 1}{n + 1},  (13)
T_{n+1}(x) − 5^{\frac{1−(−1)^{n}}{2}} T_{n}(x − 1) − T_{n−1}(x − 2) = (−1)^{n+1}5^{⌊ \frac{n+1}{2} ⌋}\binom{x − 1}{n + 1}.  (14)

See the next section for notes on the proof. Examples of T_{n}(x) are given in Table 5.

3 Proofs of main results

Of the four new theorems above, we present two full proofs. The other two theorems have analogous proofs.

First, we collect various Fibonacci and Lucas number results that we will use. Proofs are available in many standard sources such as Vajda [5].

Lemma 6. Let α = (1 + \sqrt{5})/2 and β = (1 − \sqrt{5})/2. For all integers m and n,

F_{m}F_{n+1} − F_{n}F_{m+1} = (−1)^{n}F_{m−n},  (15)
F_{n} = 3F_{n−2} + F_{n−4},  (16)
F_{n} = 4F_{n−3} + F_{n−6},  (17)
F_{n} = \frac{α^{n} − β^{n}}{\sqrt{5}} ,  (18)
5F_{n} = L_{n+1} + L_{n−1},  (19)
L_{n} = α^{n} + β^{n}.  (20)

Also, we will need Lemma 2.2 from the previous work [3] concerning (1).

Lemma 7. Let F_{k}(x) = F_{1}x^{k−1} + F_{2}x^{k−2} + ⋯ + F_{k−1}x + F_{k}. The nth derivative of F_{k}(x) is

F_{k}^{(n)}(x) = \begin{cases}∑_{i=1}^{k−n} x^{k−n−i}F_{i}(k − i)_{n}, & if n ≤ k − 1; \\ 0, & if n ≥ k. \end{cases}  (21)

The product of F_{k}(x) and x^{2} −x−1, the characteristic polynomial of the Fibonacci sequence, is

(x^{2} − x − 1)F_{k}(x) = x^{k+1} − F_{k+1}x − F_{k}.  (22)

The derivatives of the product of F_{k}(x) and x^{2} − x − 1 are

(x^{2} − x − 1)F′_{k}(x) + (2x − 1)F_{k}(x) = (k + 1)x^{k} − F_{k+1}  (23)

and

(x^{2} − x − 1)F_{k}^{(n)}(x) + n(2x − 1)F_{k}^{(n−1)}(x) + n(n − 1)F_{k}^{(n−2)}(x)
= \begin{cases}x^{k−n+1}(k + 1)_{n}, & if 2 ≤ n ≤ k + 1; \\ 0, & if n ≥ k + 2. \end{cases}  (24)

The proofs of Theorems 1, 2, and 3 follow the same format. We present the proof of Theorem 3 which includes scalar factors (powers of 2).

Proof of Theorem 2. The proof is very similar to those of Theorem 2.1, Proposition 2.3, and Proposition 2.4 of our previous article [3].

Proof of Theorem 3. Lagrange’s interpolation formula yields

R_{n}(x) = ∑_{i=0}^{n} 2^{n−1−i}F_{2n+i+3} ∏_{\begin{matrix}j=0 \\ j≠i \end{matrix}}^{n} \frac{x − j}{i − j}

= (−1)^{n}2^{n−1}(n + 1)\binom{x}{n + 1} ∑_{i=0}^{n} \frac{(−1)^{i}}{2^{i}} \binom{n}{i}\frac{F_{2n+i+3}}{x − i} ,  (25)

where we set the empty product to 1.

We proceed by induction on n. As we will see, two base cases are necessary. First, R_{0}(x) is a constant polynomial satisfying R_{0}(0) = F_{3}/2 = 1, so R_{0}(x) = 1 with leading coefficient 1 = (−1)^{0}/0! as claimed. We want to show that, for integers k > 0,

R_{0}(k) = 1 = \frac{F_{k+3}}{2^{k+1}} + ∑_{i=1}^{k} \frac{F_{i}}{2^{i+1}}

and, for integers k < 0,

R_{0}(k) = 1 = \frac{F_{k+3}}{2^{k+1}} − ∑_{i=1}^{−k−1} \frac{F_{−i}}{2^{−i+1}} .

These follow from substituting x = 2 and x = −1/2, respectively, into (22).

For n = 1, the polynomial R_{1}(x) satisfies R_{1}(0) = F_{5} = 5 and R_{1}(1) = F_{6}/2 = 4, so R_{1}(x) = −x + 5, a linear polynomial with leading coefficient −1 = (−1)^{1}/1! as claimed. We want to show that, for integers k > 1,

R_{1}(k) = −k + 5 = \frac{F_{k+5}}{2^{k}} − ∑_{i=1}^{k−1} \frac{F_{i}}{2^{i+1}} (k − i)  (26)

and, for integers k < 0,

R_{1}(k) = −k + 5 = \frac{F_{k+5}}{2^{k}} + ∑_{i=1}^{−k−1} \frac{F_{−i}}{2^{−i+1}} (k + i).  (27)

Given k > 1, use x = 2 in (23) to see

∑_{i=1}^{k−1} \frac{F_{i}}{2^{i+1}} (k − i) = \frac{1}{2^{k}} F′_{k}(2)

= \frac{1}{2^{k}} ((k + 1)2^{k} − 3F_{k}(2) − F_{k+1})

= \frac{1}{2^{k}} ((k + 1)2^{k} − 3(2^{k+1} − F_{k+3}) − F_{k+1})

= k − 5 + \frac{1}{2^{k}} F_{k+5},

where we apply (15) in the last equality. Rearranging gives (26).

For (27), assume k < 0 and let m = −k. Using x = −1/2 in (23) gives

∑_{i=1}^{−k−1} \frac{F_{−i}}{2^{−i+1}} (k + i)

= (−1)^{m+1}2^{m−2}F′_{m} (−\frac{1}{2})

= (−1)^{m}2^{m}(2F_{m} (−\frac{1}{2}) + (−\frac{1}{2})^{m} (m + 1) − F_{m+1})

= (−1)^{m}2^{m} ((−8) ((−\frac{1}{2})^{m+1} + \frac{1}{2}F_{m+1} − F_{m}) + (−\frac{1}{2})^{m} (m + 1) − F_{m+1})

= (−1)^{m}2^{m} (−F_{m−5} + (−\frac{1}{2})^{m} (m + 5)) ,

again using (15). Putting the expression back in terms of k establishes (27), which completes the base cases of the induction.

Let n > 1 and assume that the theorem holds for all nonnegative integers no greater than n. We prove that R_{n+1}(x) has degree n + 1 and leading coefficient (−1)^{n+1}/(n + 1)!, more specifically, that

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

for each integer k > n + 1 and

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

for each integer k < 0.

We begin with (28); let k > n + 1. Using x = 2 in (24) leads to

F_{k}^{(n+1)}(2) + 3(n + 1)F_{k}^{(n)}(2) + n(n + 1)F_{k}^{(n−1)}(2) = 2^{k−n}(k + 1)_{n+1}.  (30)

The induction hypothesis and (7) with x = 2 give

R_{n}(k) = 2^{n−k−1} (F_{k+2n+3} + \frac{(−1)^{n}}{n!} F_{k}^{(n)}(2)) ,

R_{n−1}(k) = 2^{n−k−2} (F_{k+2n+1} + \frac{(−1)^{n−1}}{(n − 1)!} F_{k}^{(n−1)}(2)) .

Substituting these into (30), we have

( ∑_{i=1}^{k−n−1} 2^{k−n−1−i}F_{i}(k − i)_{n+1}) + 3(n + 1)2^{1+k−n}n!(−1)^{n} (R_{n}(k) − 2^{n−k−1}F_{k+2n+3})

+ n(n + 1)2^{2+k−n}(n − 1)!(−1)^{n−1} (R_{n−1}(k) − 2^{n−k−2}F_{k+2n+1}) = (k + 1)_{n+1}.

Rearranging and using the identity (16) gives

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

Now define the polynomial g(x) as

g(x) = (−1)^{n+1}\binom{x + 1}{n + 1} + 6R_{n}(x) − 4R_{n−1}(x).

To complete the verification of (28), it suffices to show g(x) = R_{n+1}(x). This will also establish (8).

Notice that g(x) is a degree n + 1 polynomial with leading coefficient (−1)^{n+1}/(n + 1)!. It is then enough to verify that g(k) = 2^{n−k}F_{k+2n+5} for k = 0, …, n + 1. We do this in three cases, each using (16).

• For 0 ≤ k ≤ n − 1, we have R_{n}(k) = 2^{n−k−1}F_{k+2n+3} and R_{n−1}(k) = 2^{n−k−2}F_{k+2n+1}. Since \binom{k+1}{n+1} = 0,

g(k) = 6·2^{n−k−1}F_{k+2n+3}−4·2^{n−k−2}F_{k+2n+1} = 2^{n−k}(3F_{k+2n+3}−F_{k+2n+1}) = 2^{n−k}F_{k+2n+5}.

• For k = n, we have R_{n}(n) = F_{3n+3}/2 and

R_{n−1}(n) = \frac{F_{3n+1}}{2^{2}} + (−1)^{n−1} \frac{F_{1}}{2^{2}} \binom{n − 1}{n − 1} = \frac{F_{3n+1}}{4} + \frac{(−1)^{n−1}}{4} .

Hence we have

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

• For k = n + 1, we have

R_{n}(n + 1) = \frac{F_{3n+4}}{4} + \frac{(−1)^{n}}{4} ,

R_{n−1}(n + 1) = \frac{F_{3n+2}}{8} + \frac{(−1)^{n−1}}{4} n + \frac{(−1)^{n−1}}{8}

so that

g(n + 1) = (−1)^{n+1}(n + 2) + 6 (\frac{F_{3n+4}}{4} + \frac{(−1)^{n}}{4} ) − 4 (\frac{F_{3n+2}}{8} + \frac{(−1)^{n−1}}{4} n + \frac{(−1)^{n−1}}{8} )

= \frac{F_{3n+6}}{2} .

It remains to establish (29). Assume k < 0 and let m = −k. Also, let m′ = m + n. Recall the identity

\binom{a}{b} = (−1)^{b}\binom{b − a − 1}{b}  (31)

for integers a and b with b ≥ 0. This allows us to write the sum in (29) as

∑_{i=1}^{−k−1} \frac{F_{−i}}{2^{−i+1}} \binom{k + i}{n + 1} = ∑_{i=1}^{m−1} \frac{F_{−i}}{2^{−i+1}} \binom{−m + i}{n + 1}

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

= \frac{(−1)^{n+1}}{(n + 1)!} ∑_{i=1}^{m−1} \frac{(−1)^{i−1}}{2^{−i+1}} F_{i}(m + n − i)_{n+1}

= \frac{(−1)^{n+1}}{(n + 1)!} ∑_{i=1}^{m′−(n+1)} (−\frac{1}{2})^{−i+1} F_{i}(m′ − i)_{n+1}

= \frac{(−1)^{n+1}}{(n + 1)!} (−\frac{1}{2})^{(n+2)−m′} ∑_{i=1}^{m′−(n+1)} (−\frac{1}{2})^{m′−(n+1)−i} F_{i}(m′ − i)_{n+1}

= \frac{(−1)^{m+n+1}}{2^{2−m}(n + 1)!}F_{m+n}^{(n+1)}(−\frac{1}{2}) .

Using (24) with x = −1/2, we write the last expression as

\frac{(−1)^{m+n+1}}{2^{2−m}(n + 1)!}

× (−8(n + 1)F_{m+n}^{(n)} (−\frac{1}{2}) + 4n(n + 1)F_{m+n}^{(n−1)} (−\frac{1}{2}) − 4 (−\frac{1}{2})^{m} (m + n + 1)_{n+1}) . (32)

Next, we determine F_{m+n}^{(n)}(−1/2) and F_{m+n}^{(n−1)}(−1/2). Using (21) with x = −1/2, identity (31), and the induction hypothesis gives

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

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

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

= \frac{(−1)^{m}n!}{2^{m−1}} (R_{n}(−m − 1) − 2^{m+n}F_{2n−m+2}) .

Similarly,

F_{m+n}^{(n−1)} (−\frac{1}{2}) = \frac{(−1)^{m+1}(n − 1)!}{2^{m}} (R_{n−1}(−m − 2) − 2^{m+n}F_{2n−m−1}) .

Substituting these expressions into (32) gives

\frac{(−1)^{m+n+1}}{2^{2−m}(n + 1)!} (−8(n + 1)\frac{(−1)^{m}n!}{2^{m−1}} (R_{n}(−m − 1) − 2^{m+n}F_{2n−m+2})

+ 4n(n + 1)\frac{(−1)^{m+1}(n − 1)!}{2^{m}} (R_{n−1}(−m − 2) − 2^{m+n}F_{2n−m−1})

− 4 (−\frac{1}{2})^{m} (m + n + 1)_{n+1})

= (−1)^{n+1}2^{m+n}F_{2n−m+5} + (−1)^{n} (4R_{n}(−m − 1) + R_{n−1}(−m − 2)) − \binom{−m − 1}{n + 1},

using (17). Now define j(x) as

j(x) = (−1)^{n+1}\binom{x − 1}{n + 1} + 4R_{n}(x − 1) + R_{n−1}(x − 2).

Establishing j(x) = R_{n+1}(x) will verify (29) and also show (9). As with g(x) above, it suffices to show j(k) = 2^{n−k}F_{k+2n+5} for k = 0, …, n + 1. The three cases here, presented in less detail, all use (17).

• For k = 0,

j(0) = (−1)^{n+1}\binom{−1}{n + 1} + 4R_{n}(−1) + R_{n−1}(−2) = 2^{n}(4F_{2n+2} + F_{2n−1}) = 2^{n}F_{2n+5}.

• For k = 1,

j(1) = (−1)^{n+1}\binom{0}{n + 1} + 4R_{n}(0) + R_{n−1}(−1) = 2^{n−1}(4F_{2n+3} + F_{2n}) = 2^{n−1}F_{2n+6}.

• For 2 ≤ k ≤ n + 1,

j(k) = (−1)^{n+1}\binom{k − 1}{n + 1} + 4R_{n}(k − 1) + R_{n−1}(k − 2) = 2^{k−n}(4F_{k+2n+2} + F_{k+2n−1})

= 2^{k−n}F_{k+2n+5}.

Finally, we show that each of the recurrences (8) and (9) with some initial conditions determines the polynomials R_{n}(x) completely. That is, the polynomial sequences given by

U_{0}(x) = 1, U_{1}(x) = −x + 5, and

U_{n+1}(x) = 6R_{n}(x) − 4R_{n−1}(x) + (−1)^{n+1}\binom{x + 1}{n + 1} for n ≥ 1,

V_{0}(x) = 1, V_{1}(x) = −x + 5, and

V_{n+1}(x) = 4V_{n}(x − 1) + V_{n−1}(x − 2) + (−1)^{n+1}\binom{x − 1}{n + 1} for n ≥ 1

satisfy U_{n}(x) = V_{n}(x) = R_{n}(x) for all n. We prove this for V_{n}(x); the proof for U_{n}(x) is similar.

By inspection, V_{0}(x) = R_{0}(x) and V_{1}(x) = R_{1}(x). Assume that V_{n}(x) = R_{n}(x) and V_{n−1}(x) = R_{n−1}(x) for some n ≥ 1. By its defining recurrence, V_{n+1}(x) has degree n + 1 and leading coefficient (−1)^{n+1}/(n + 1), as does R_{n+1}(x), so it is enough to show V_{n+1}(j) = R_{n+1}(j) for 0 ≤ j ≤ n. The following verification makes frequent use of (17).

• For j = 0, from (7) we have

V_{n+1}(0) = 4V_{n}(−1) + V_{n−1}(−2) + (−1)^{n+1}\binom{−1}{n + 1}

= 4R_{n}(−1) + R_{n−1}(−2) + (−1)^{n+1}(−1)^{n+1}

= 4 · 2^{n}F_{2n+2} + (2^{n}F_{2n−1} + (−1)^{n}F_{−1}\binom{−1}{n − 1}) + 1

= 2^{n}F_{2n+5},

which matches R_{n+1}(0).

• For j = 1, from the definition of R_{n}(x) and (7) we have

V_{n+1}(1) = 4V_{n}(0) + V_{n−1}(−1) + (−1)^{n+1}\binom{0}{n + 1}
= 4R_{n}(0) + R_{n−1}(−1)
= 4 · 2^{n−1}F_{2n+3} + 2^{n−1}F_{2n}
= 2^{n−1}F_{2n+6},

which matches R_{n+1}(1).

• For 2 ≤ j ≤ n, from the definition of R_{n}(x) we have

V_{n+1}(j) = 4V_{n}(j − 1) + V_{n−1}(j − 2) + (−1)^{n+1}\binom{j − 1}{n + 1}
= 4R_{n}(j − 1) + R_{n−1}(j − 2)
= 4 · 2^{n−j}F_{2n+j+2} + 2^{n−j}F_{2n+j−1}
= 2^{n−j}F_{2n+j+5},

which matches R_{n+1}(j) for 2 ≤ j ≤ n.

It is apparent from the statements of Theorems 4 and 5 that these are more complicated results, with different interpolation points depending on the parity of the degree n. Nonetheless, the S_{n}(x) polynomials are connected between even and odd values of n by relations including (11). The T_{n}(x) polynomials have more connections between parities, e.g.,

(13) and (14). We detail the first of these two similar proofs.

Proof of Theorem 4. We proceed by induction on n with two base cases. First, S_{0}(x) is a constant polynomial satisfying S_{0}(0) = −L_{0}/2 = −2/2 = −1, i.e., S_{0}(x) = −1 with leading coefficient −1 = −5^{0/2}/0! as claimed. We want to show that, for integers k > 0,

S_{0}(k) = −1 = \frac{L_{k}}{(−2)^{1+k}} + \frac{5}{2} ∑_{i=1}^{k} \frac{F_{i}}{(−2)^{i}}

and, for integers k < 0,

S_{0}(k) = −1 = \frac{L_{k}}{(−2)^{1+k}} + 5 ∑_{i=1}^{−k−1}(−2)^{i−1}F_{−i}.

These follow from substituting x = −2 and x = 1/2, respectively, into (22).

For n = 1, the polynomial S_{1} satisfies S_{1}(0) = 2^{0}F_{1} = 1 and S_{1}(1) = 2^{−1}F_{0} = 0, so S_{1}(x) = −x + 1, a linear polynomial with leading coefficient −1 = −5^{(1−1)/2}/1! as claimed. We want to establish that, for integers k > 1,

S_{1}(k) = −k + 1 = \frac{F_{k−1}}{(−2)^{k}} − 5 ∑_{i=1}^{k−1} \frac{F_{i}}{(−2)^{i+1}} (k − i)  (33)

and, for integers k < 0,

S_{1}(k) = −k + 1 = \frac{F_{k−1}}{(−2)^{k}} + 5 ∑_{i=1}^{−k−1}(−2)^{i−1}F_{−i}(k + i).  (34)

Given k > 1, using x = −2 in the equations of Lemma 7 yields

F′_{k}(−2) = ∑_{i=1}^{k−1}(−2)^{k−1−i}F_{i}(k − i),

5F_{k}(−2) = (−2)^{k+1} + 2F_{k+1} − F_{k},

5F′_{k}(−2) = (k + 1)(−2)^{k} + 5F_{k}(−2) − F_{k+1}.

Hence we have

∑_{i=1}^{k−1} \frac{F_{i}}{(−2)^{i+1}} (k − i) = \frac{1}{(−2)^{k}} F′_{k}(−2)

= \frac{1}{(−2)^{k}} (\frac{1}{5}(k + 1)(−2)^{k} + F_{k}(−2) − \frac{1}{5}F_{k+1})

= \frac{1}{5(−2)^{k}} ((k + 1)(−2)^{k} + (−2)^{k+1} + 2F_{k+1} − F_{k} − F_{k+1})

= \frac{1}{5} (k − 1 + \frac{F_{k−1}}{(−2)^{k}} ) .

Rearranging gives (33).

For (34), assume k < 0 and write k = −m. Substituting x = 1/2 into (21) and (23) gives

F′_{m}(\frac{1}{2}) = ∑_{i=1}^{m−1} (\frac{1}{2})^{m−1−i} F_{i}(m − i),

−\frac{5}{4}F′_{m}(\frac{1}{2}) = (\frac{1}{2})^{m} (m + 1) − F_{m+1}.

Hence

∑_{i=1}^{−k−1}(−2)^{i−1}F_{−i}(k + i) = − ∑_{i=1}^{m−1}(−2)^{i−1}F_{−i}(m − i) = −2^{m−2}F′_{m} (\frac{1}{2})

= \frac{1}{5}(m + 1 − 2^{m}F_{m+1}) = \frac{1}{5} (−k + 1 − \frac{F_{k−1}}{(−2)^{k}} ) .

This establishes (34), completing the base cases.

Let n > 1 and assume that the theorem holds for all nonnegative integers no greater than n. We want to prove that, if n + 1 is even, then S_{n+1}(x) has degree n + 1 and leading coefficient −5^{(n+1)/2}/(n + 1)! and, for each integer k > n + 1,

S_{n+1}(k) = \frac{L_{k−n−1}}{(−2)^{k−n}} − 5^{\frac{n+3}{2}} ∑_{i=1}^{k−n−1} \frac{F_{i}}{(−2)^{i+1}} \binom{k − i}{n + 1}  (35)

and, for each integer k < 0,

S_{n+1}(k) = \frac{L_{k−n−1}}{(−2)^{k−n}} + 5^{\frac{n+3}{2}} ∑_{i=1}^{−k−1}(−2)^{i−1}F_{−i}\binom{k + i}{n + 1}.  (36)

If n + 1 is odd, then S_{n+1}(x) has degree n + 1 and leading coefficient −5^{n/2}/(n + 1)! and, for each integer k > n + 1,

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

and, for each integer k < 0,

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

We begin with odd n, thus (35) and (36). Let k > n + 1. Using x = −2 in (24) gives

5F_{k}^{(n+1)}(−2) − 5(n + 1)F_{k}^{(n)}(−2) + n(n + 1)F_{k}^{(n−1)}(−2) = (−2)^{k−n}(k + 1)_{n+1}.  (39)

By the induction hypothesis, S_{n}(x) has degree n and leading coefficient −5^{(n−1)/2}/n! while S_{n−1}(x), since n−1 is even, has degree n−1 and leading coefficient −5^{(n−1)/2}/(n−1)!. Also,

S_{n}(k) = \frac{F_{k−n}}{(−2)^{1+k−n}} − \frac{5^{\frac{n+1}{2}}}{(−2)^{1+k−n}n!}F_{k}^{(n)}(−2),

S_{n−1}(k) = \frac{L_{k−n+1}}{(−2)^{2+k−n}} − \frac{5^{\frac{n+1}{2}}}{(−2)^{2+k−n}(n − 1)!}F_{k}^{(n−1)}(−2).

By (21) with x = −2 and (39),

5 ∑_{i=1}^{k−n−1}(−2)^{k−n−1−i}F_{i}(k − i)_{n+1} − 5(n + 1)(−2)^{1+k−n}n!5^{− \frac{n+1}{2}} (\frac{F_{k−n}}{(−2)^{1+k−n}} − S_{n}(k))

+ n(n + 1)(−2)^{2+k−n}(n − 1)!5^{− \frac{n+1}{2}} (\frac{L_{k−n+1}}{(−2)^{2+k−n}} − S_{n−1}(k)) = (−2)^{k−n}(k + 1)_{n+1}.

Rearranging and (19) give

−4S_{n−1}(k) − 10S_{n}(k) − 5^{\frac{n+1}{2}} \binom{k + 1}{n + 1} = \frac{L_{k−n−1}}{(−2)^{k−n}} − 5^{\frac{n+3}{2}} ∑_{i=1}^{k−n−1} \frac{F_{i}}{(−2)^{i+1}} \binom{k − i}{n + 1}.

To prove (35), let

g(x) = −4S_{n−1}(x) − 10S_{n}(x) − 5^{\frac{n+1}{2}} \binom{x + 1}{n + 1}.

We show that g(x) = S_{n+1}(x). Notice that −5^{(n+1)/2}/(n + 1)! is the leading coefficient of g(x). Thus it suffices to verify that g(k) = L_{k−n−1}/(−2)^{k−n} for k = 0, …, n + 1. We do this in three cases.

• For 0 ≤ k ≤ n−1, we have S_{n}(k) = F_{k−n}/(−2)^{1+k−n} and S_{n−1}(k) = L_{k−n+1}/(−2)^{2+k−n} from the definition. Also, \binom{k+1}{n+1} = 0, so

g(k) = −4\frac{L_{k−n+1}}{(−2)^{2+k−n}} − 10\frac{F_{k−n}}{(−2)^{1+k−n}} − 5^{\frac{n+1}{2}} \binom{k + 1}{n + 1}

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

• For k = n, we have S_{n}(n) = −F_{0}/2 = 0 and, by the induction hypothesis,

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

Also, \binom{k+1}{n+1} = \binom{n+1}{n+1} = 1, so g(k) = −1 + 5^{\frac{n+1}{2}} − 5^{\frac{n+1}{2}} = −1 = L_{−1}.

• For k = n + 1, by the induction hypothesis,

S_{n}(n + 1) = \frac{F_{1}}{(−2)^{2}} − 5^{\frac{n+1}{2}} \frac{F_{1}}{(−2)^{2}} \binom{n}{n}

= \frac{1}{4} (1 − 5^{\frac{n+1}{2}} ) ,

S_{n−1}(n + 1) = \frac{L_{2}}{(−2)^{3}} − 5^{\frac{n+1}{2}} (\frac{F_{1}}{(−2)^{2}} \binom{n}{n − 1} + \frac{F_{2}}{(−2)^{3}} \binom{n − 1}{n − 1})

= −\frac{1}{8} (3 + 5^{\frac{n+1}{2}} (2n − 1)) .

Also, \binom{k+1}{n+1} = \binom{n+2}{n+1} = n + 2. Altogether,

g(k) = \frac{3}{2} + 5^{\frac{n+1}{2}} (n − \frac{1}{2}) − \frac{5}{2} (1 − 5^{\frac{n+1}{2}} ) − 5^{\frac{n+1}{2}} (n + 2) = −1 = −\frac{L_{1}}{2} .

Thus we have established (35) and the polynomial recurrence, for n odd,

S_{n+1}(x) + 10S_{n}(x) + 4S_{n−1}(x) = −5^{\frac{n+1}{2}} \binom{x + 1}{n + 1}.  (40)

For (36), let k < 0 and write k = −m. Also, let m′ = m + n. Using (31), we can write the sum in (36) as

∑_{i=1}^{−k−1}(−2)^{i−1}F_{−i}\binom{k + i}{n + 1} = ∑_{i=1}^{m−1}(−2)^{i−1}F_{−i}\binom{−m + i}{n + 1}

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

= \frac{(−1)^{n+1}}{(n + 1)!} ∑_{i=1}^{m−1}(−1)^{i−1}(−2)^{i−1}F_{i}(m + n − i)_{n+1}

= \frac{(−1)^{n+1}}{(n + 1)!} ∑_{i=1}^{m′−(n+1)} (\frac{1}{2})^{−i+1} F_{i}(m′ − i)_{n+1}

= \frac{(−1)^{n+1}}{(n + 1)!} (\frac{1}{2})^{(n+2)−m′} ∑_{i=1}^{m′−(n+1)} (\frac{1}{2})^{m′−(n+1)−i} F_{i}(m′ − i)_{n+1}

= \frac{(−1)^{n+1}}{2^{2−m}(n + 1)!}F_{m+n}^{(n+1)} (\frac{1}{2}) .

Using (24) with x = 1/2, we write the last expression as

\frac{(−1)^{n+1}}{2^{2−m}(n + 1)!} (\frac{4}{5}n(n + 1)F_{m+n}^{(n−1)} (\frac{1}{2}) − \frac{4}{5} (\frac{1}{2})^{m} (m + n + 1)_{n+1}) .  (41)

Next, we determine F_{m+n}^{(n−1)}(1/2). Using (21), (31), and the induction hypothesis gives

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

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

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

= (n − 1)!2^{−m}5^{− \frac{n+1}{2}} (S_{n−1}(−m − 2) + 2^{m+n}L_{m+n+1}) .

Substituting this expression into (41) gives

\frac{(−1)^{n+1}}{2^{2−m}(n + 1)!}(\frac{4}{5}n(n + 1)(n − 1)!2^{−m}5^{− \frac{n+1}{2}} (S_{n−1}(−m − 2) + 2^{m+n}L_{m+n+1})

−\frac{4}{5} (\frac{1}{2})^{m} (m + n + 1)_{n+1})

= 5^{− \frac{n+3}{2}} (S_{n−1}(−m − 2) + 2^{m+n}L_{m+n+1}) − \frac{1}{5}\binom{m + n + 1}{n + 1}.

This implies

S_{n−1}(k − 2) − 5^{\frac{n+1}{2}} \binom{k − 1}{n + 1} = \frac{L_{k−n−1}}{(−2)^{k−n}} + 5^{\frac{n+3}{2}} ∑_{i=1}^{−k−1}(−2)^{i−1}F_{−i}\binom{k + i}{n + 1}.

Now define j(x) as

j(x) = S_{n−1}(x − 2) − 5^{\frac{n+1}{2}} \binom{x − 1}{n + 1}.

Establishing j(x) = S_{n+1}(x) will verify (36). It suffices to show that j(k) = −2^{n−k}L_{n−k+1} for k = 0, …, n + 1. We consider three cases.

• For k = 0,

j(0) = S_{n−1}(−2) − 5^{\frac{n+1}{2}} \binom{−1}{n + 1}

= \frac{L_{−1−n}}{(−2)^{−n}} + 5^{\frac{n+1}{2}} F_{−1}\binom{−1}{n + 1} − 5^{\frac{n+1}{2}} \binom{−1}{n + 1}

= −2^{n}L_{n+1}.

• For k = 1,

j(1) = S_{n−1}(−1) − 5^{\frac{n+1}{2}} \binom{0}{n + 1} = −2^{n−1}L_{n}.

• For 2 ≤ k ≤ n + 1, since \binom{k−1}{n+1} = 0, we have

j(k) = S_{n−1}(k − 2) − 5^{\frac{n+1}{2}} \binom{k − 1}{n + 1} = −2^{n−k}L_{n−k+1}.

Thus we have established (36) and the polynomial recurrence, for n odd,

S_{n+1}(x) − S_{n−1}(x − 2) = −5^{\frac{n+1}{2}} \binom{x − 1}{n + 1}.  (42)

For n even, the proofs of (37) and (38) are completely analogous to the odd case. The polynomial recurrences corresponding to (40) and (42) that arise for n even are

S_{n+1}(x) + 2S_{n}(x) + 4S_{n−1}(x) = −5^{\frac{n}{2}} \binom{x + 1}{n + 1},  (43)
S_{n+1}(x) − S_{n−1}(x − 2) = −5^{\frac{n}{2}} \binom{x − 1}{n + 1}.  (44)

Combining (40) and (43) gives (11), likewise (42) and (44) for (12). Finally, we want to show that each of the recurrences (11) and (12) with some initial

conditions determines the polynomials S_{n}(x) completely. That is, the polynomial sequences given by

U_{0}(x) = −1, U_{1}(x) = −x + 1, and

U_{n+1}(x) = −2 · 5^{\frac{1−(−1)^{n}}{2}} U_{n}(x) − 4U_{n−1}(x) − 5^{⌊ \frac{n+1}{2} ⌋}\binom{x + 1}{n + 1} for n ≥ 1,

V_{0}(x) = −1, V_{1}(x) = −x + 1, and

V_{n+1}(x) = V_{n−1}(x − 2) − 5^{⌊ \frac{n+1}{2} ⌋}\binom{x − 1}{n + 1} for n ≥ 1

satisfy U_{n}(x) = V_{n}(x) = S_{n}(x) for all n. We prove this for U_{n}(x); the proof for V_{n}(x) is similar.

By inspection, U_{0}(x) = S_{0}(x) and U_{1}(x) = S_{1}(x). Assume that U_{n}(x) = S_{n}(x) and U_{n−1}(x) = S_{n−1}(x) for some n ≥ 1. By its defining recurrence, U_{n+1}(x) has degree n + 1 and leading coefficient −5^{⌊(n+1)/2⌋}, as does S_{n+1}(x), so it is enough to show U_{n+1}(j) = S_{n+1}(j) for 0 ≤ j ≤ n. We need to consider n even or odd separately, each with two cases.

For n even:

• For 0 ≤ j ≤ n − 1,

U_{n+1}(j) = −2 · 5^{\frac{1−(−1)^{n}}{2}} S_{n}(j) − 4S_{n−1}(j) − 5^{⌊ \frac{n+1}{2} ⌋}\binom{j + 1}{n + 1}
= −2 · 5^{0}(−2^{n−1−j}L_{n−j}) − 4(−2)^{n−2−j}F_{j−n+1}
= 2^{n−j}(F_{n−j+1} + F_{n−j−1}) − (−2)^{n−j}F_{j−n+1}
= (−2)^{n−j}F_{j−n+1},

which matches S_{n+1}(j).

• For j = n, we have U_{n+1}(n) = −2(−1) − (1 − 5^{\frac{n}{2}} ) − 5^{\frac{n}{2}} = 1, which matches S_{n+1}(n).

For n odd:

• For 0 ≤ j ≤ n − 1,

U_{n+1}(j) = −2 · 5^{1}((−2)^{n−1−j}F_{j−n}) − 4(−2^{n−2−j})L_{n−1−j} − 0
= −2^{n−j}(L_{n−j+1} + L_{n−j−1}) + 2^{n−j}L_{n−j−1}
= −2^{n−j}L_{n−j+1},

which matches S_{n+1}(j).

• For j = n, we have U_{n+1}(n) = −2 · 5 · 0 − (1 − 5^{\frac{n+1}{2}} ) − 5^{\frac{n+1}{2}} = −1, which matches S_{n+1}(n).

Proof of Theorem 5. The proof is analogous to that of Theorem 4.

4 Expansion in binomial polynomials

The binomial polynomials \binom{x}{n} provide an alternative basis for polynomials: For any degree n polynomial h(x) with complex coefficients, there exist unique complex numbers a_{0}, …, a_{n} such that h(x) = ∑_{i=0}^{n} a_{i}\binom{x}{i}. Moreover, the coefficients a_{0}, …, a_{n} can be determined by

a_{i} = ∑_{k=0}^{i}(−1)^{i−k}\binom{i}{k}h(k)  (45)

for i = 0, …, n. Cahen and Chabert [1, 2] provide background on integer-valued polynomials such as these, including historical notes mentioning Newton and Pólya.

In this section we determine the binomial polynomial expansions for the polynomials of Section 2. This will contribute to the identities of Section 5. As in Section 3, we provide complete proofs for two of the five results, as the remaining proofs are very similar.

Theorem 8. The polynomials P_{n}(x) defined in Theorem 1 satisfy

P_{n}(x) = ∑_{i=0}^{n} F_{n−i+2}\binom{x}{i}.  (46)

Proof. Multiplying (4) by t^{n} and forming the formal power series over n gives

∑_{n=1}^{∞} t^{n}P_{n+1}(x) − ∑_{n=1}^{∞} t^{n}P_{n}(x) − ∑_{n=1}^{∞} t^{n}P_{n−1}(x) = ∑_{n=1}^{∞} t^{n}\binom{x + 1}{n + 1}.

Letting g(t, x) = ∑_{n=0}^{∞} t^{n}P_{n}(x), we have

\frac{1}{t}(g(t, x) − P_{0}(x) − tP_{1}(x)) − (g(t, x) − P_{0}(x)) − tg(t, x) = ∑_{n=1}^{∞} t^{n}\binom{x + 1}{n + 1}.

Putting in P_{0}(x) = 1, P_{1}(x) = x + 2, recognizing the generating function for F_{n+1}, and solving for g(t, x) yields

g(t, x) = \frac{1}{1 − t − t^{2}} (1 + (x + 1)t + ∑_{n=2}^{∞} t^{n}\binom{x + 1}{n})

= (∑_{n=0}^{∞} F_{n+1}t^{n}) (∑_{n=0}^{∞} t^{n}\binom{x + 1}{n})

= ∑_{n=0}^{∞} t^{n} ∑_{i=0}^{n} F_{n−i+1}\binom{x + 1}{i}

so that

P_{n}(x) = ∑_{i=0}^{n} F_{n−i+1}\binom{x + 1}{i}  (47)

= ∑_{i=0}^{n} F_{n−i+1}\binom{x}{i} + ∑_{i=1}^{n} F_{n−i+1}\binom{x}{i − 1}

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

The analogous results for Q_{n}(x) and R_{n}(x) have very similar proofs. Theorem 9. The polynomials Q_{n}(x) defined in Theorem 2 satisfy

Q_{n}(x) = ∑_{i=0}^{n}(−1)^{i}F_{2n−2i+1}\binom{x}{i}.  (48)

Theorem 10. The polynomials R_{n}(x) defined in Theorem 3 satisfy

R_{n}(x) = ∑_{i=0}^{n}(−1)^{i}2^{n−i−1}F_{2n−2i+3}\binom{x}{i}.  (49)

We record the equations analogous to (47):

Q_{n}(x) = ∑_{i=0}^{n}(−1)^{i}F_{2n−2i+2}\binom{x + 1}{i},  (50)
R_{n}(x) = ∑_{i=0}^{n}(−1)^{i}2^{n−i}F_{2n−2i+2}\binom{x + 1}{i}.  (51)

Again, S_{n}(x) and T_{n}(x) have more complicated results. We provide the complete proof for T_{n}(x); the proof for S_{n}(x) is very similar. Theorem 11. The polynomials S_{n}(x) defined in Theorem 4 satisfy,

• for n ≥ 2,

S_{n+2}(x) − 12S_{n}(x) + 16S_{n−2}(x) = −5^{⌊ \frac{n}{2} ⌋} (5\binom{x + 1}{n + 2} − 10\binom{x + 1}{n + 1} + 4\binom{x + 1}{n});

• for positive even n,

S_{n}(x) = − ∑_{i=0}^{n/2} 5^{i−1}2^{n−2i}F_{n−2i+2} (5\binom{x + 1}{2i} − 10\binom{x + 1}{2i − 1} + 4\binom{x + 1}{2i − 2}) , (52)
S_{n}(x) = ∑_{i=0}^{n}(−1)^{i+1}5^{⌊ \frac{i+1}{2} ⌋}2^{n−i−1}b_{n−i}\binom{x}{i} with b_{k} as defined in (2);  (53)

• for positive odd n,

S_{n}(x) = − ∑_{i=0}^{(n+1)/2} 5^{i−2}2^{n−2i+1}F_{n−2i+3} (5\binom{x + 1}{2i − 1} − 10\binom{x + 1}{2i − 2} + 4\binom{x + 1}{2i − 3}) , (54)
S_{n}(x) = ∑_{i=0}^{n}(−1)^{i}5^{⌊ \frac{i}{2} ⌋}2^{n−i−1}c_{n−i}\binom{x}{i} with c_{k} as defined in (3).  (55)

Theorem 12. The polynomials T_{n}(x) defined in Theorem 5 satisfy, • for n ≥ 2,

T_{n+2}(x) − 27T_{n}(x) + 81T_{n−2}(x) = (−1)^{n}5^{⌊ \frac{n}{2} ⌋} (5\binom{x + 1}{n + 2} − 15\binom{x + 1}{n + 1} + 9\binom{x + 1}{n});

(56)

• for positive even n,

T_{n}(x) = ∑_{i=0}^{n/2} 5^{i−1}3^{n−2i}F_{n−2i+2} (5\binom{x + 1}{2i} − 15\binom{x + 1}{2i − 1} + 9\binom{x + 1}{2i − 2}) ,  (57)
T_{n}(x) = ∑_{i=0}^{n}(−1)^{i}5^{⌊ \frac{i+1}{2} ⌋}3^{n−i−1}b_{n+2−i}\binom{x}{i} with b_{k} as defined in (2);  (58)

• for positive odd n,

T_{n}(x) = − ∑_{i=0}^{(n+1)/2} 5^{i−2}3^{n−2i+1}F_{n−2i+3} (5\binom{x + 1}{2i − 1} − 15\binom{x + 1}{2i − 2} + 9\binom{x + 1}{2i − 3}) , (59)
T_{n}(x) = ∑_{i=0}^{n}(−1)^{i}5^{⌊ \frac{i}{2} ⌋}3^{n−i−1}c_{n+2−i}\binom{x}{i} with c_{k} as defined in (3).  (60)

Proof. To prove (56), we consider the even and odd cases separately. For n even, (13) gives

T_{n+1}(x) − 3T_{n}(x) + 9T_{n−1}(x) = −5^{\frac{n}{2}} \binom{x + 1}{n + 1},

T_{n}(x) − 15T_{n−1}(x) + 9T_{n−2}(x) = 5^{\frac{n}{2}} \binom{x + 1}{n},

and a similar equation with initial term T_{n+2}(x). These combine to give

T_{n+2}(x) − 27T_{n}(x) + 81T_{n−2}(x) = 5^{\frac{n}{2}} (5\binom{x + 1}{n + 2} − 15\binom{x + 1}{n + 1} + 9\binom{x + 1}{n}) . (61)

The case of n odd similarly leads to

T_{n+2}(x) − 27T_{n}(x) + 81T_{n−2}(x) = −5^{\frac{n−1}{2}} (5\binom{x + 1}{n + 2} − 15\binom{x + 1}{n + 1} + 9\binom{x + 1}{n}) . (62)

With the integer floor notation, (61) and (62) can be combined as (56).

For (57) and (59), we introduce generating functions, as in the proof of Theorem 8. By (56),

∑_{n=2}^{∞} t^{n}T_{n+2}(x) − 27 ∑_{n=2}^{∞} t^{n}T_{n}(x) + 81 ∑_{n=2}^{∞} t^{n}T_{n−2}(x)

= ∑_{n=2}^{∞} t^{n}(−1)^{n}5^{⌊ \frac{n}{2} ⌋} (5\binom{x + 1}{n + 2} − 15\binom{x + 1}{n + 1} + 9\binom{x + 1}{n}) .

Writing g(t, x) = ∑_{n=0}^{∞} t^{n}T_{n}(x) and using initial T_{n}(x) values from Table 5, we find

g(t, x) = \frac{1}{1 − 27t^{2} + 81t^{4}} ∑_{n=0}^{∞} t^{n}(−1)^{n}5^{⌊ \frac{n−2}{2} ⌋} (5\binom{x + 1}{n} − 15\binom{x + 1}{n − 1} + 9\binom{x + 1}{n − 2}) .

From the identity (16) and weighting the Fibonacci numbers by powers of 3, we have the generating function

\frac{1}{1 − 27t^{2} + 81t^{4}} = ∑_{n=0}^{∞} 3^{2n}F_{2n+2}t^{2n} = ∑_{n=0}^{∞} d_{n}t^{n},

where

d_{n} = \begin{cases}3^{n}F_{n+2}, & if n is even; \\ 0, & if n is odd. \end{cases}

(This d_{n} allows us to avoid some separate parity cases.) Therefore,

g(t, x) = ∑_{n=0}^{∞} ∑_{k=0}^{n} t^{n}(−1)^{k}5^{⌊ \frac{k−2}{2} ⌋}d_{n−k} (5\binom{x + 1}{k} − 15\binom{x + 1}{k − 1} + 9\binom{x + 1}{k − 2})

and comparing coefficients of t^{n} gives

T_{n}(x) = ∑_{k=0}^{n}(−1)^{k}5^{⌊ \frac{k−2}{2} ⌋}d_{n−k} (5\binom{x + 1}{k} − 15\binom{x + 1}{k − 1} + 9\binom{x + 1}{k − 2}) ,

a combined expression for (57) and (59).

Finally, for (58) and (60), let T_{n}(x) = ∑_{i=0}^{n} a_{i}\binom{x}{i} and apply (45).

If n is even, then for 0 ≤ i ≤ n we have, using (20) and the binomial theorem,

a_{i} = ∑_{k=0}^{i}(−1)^{i−k}\binom{i}{k}T_{n}(k)

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

= (−1)^{i}3^{n−1}α^{n+2} ∑_{k=0}^{i} (−\frac{α}{3})^{k} \binom{i}{k} + (−1)^{i}3^{n−1}β^{n+2} ∑_{k=0}^{i} (−\frac{β}{3} )^{k} \binom{i}{k}

= (−1)^{i}3^{n−1}α^{n+2} (1 − \frac{α}{3})^{i} + (−1)^{i}3^{n−1}β^{n+2} (1 − \frac{β}{3} )^{i}

= (−1)^{i}3^{n−i−1}5^{\frac{i}{2}} (α^{n−i+2} + (−1)^{i}β^{n−i+2})

= \begin{cases}3^{n−i−1}5^{\frac{i}{2}} L_{n−i+2}, & if i is even; \\ −3^{n−i−1}5^{\frac{i+1}{2}} F_{n−i+2}, & if i is odd. \end{cases}

Given the definition of the b_{k}, this is (58).

The case of n odd is analogous using (18):

a_{i} = ∑_{k=0}^{i}(−1)^{i+k}3^{n−k−1}F_{n+k+2}\binom{i}{k}

= (−1)^{i}3^{n−1}5^{− \frac{1}{2}} α^{n+2} (1 − \frac{α}{3})^{i} − (−1)^{i}3^{n−1}5^{− \frac{1}{2}} β^{n+2} (1 − \frac{β}{3} )^{i}

= \begin{cases}3^{n−i−1}5^{\frac{i}{2}} F_{n−i+2}, & if i is even; \\ −3^{n−i−1}5^{\frac{i−1}{2}} L_{n−i+2}, & if i is odd. \end{cases}

Given the definition of the c_{k}, this is (60).

5 Applications

We conclude with several identities involving Fibonacci numbers, Lucas numbers, binomial coefficients, and the harmonic numbers that follow from the preceding results.

The first results follow from the theorems of Section 2 concerning the leading coefficients of the various polynomials.

Corollary 13. For every nonnegative integer n,

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

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

For every even nonnegative n,

(c) ∑_{i=0}^{n−1} \frac{L_{i−n}}{2^{i}} \binom{n}{i} = \frac{5^{n/2} − 1}{2^{n−1}},

(d) ∑_{i=0}^{n} (−\frac{1}{3})^{i} L_{n+i+2}\binom{n}{i} = \frac{5^{n/2}}{3^{n−1}} .

For every odd positive n,

(e) ∑_{i=0}^{n} \frac{F_{i−n}}{2^{i}} \binom{n}{i} = \frac{5^{(n−1)/2} − 1}{2^{n−1}},

(f) ∑_{i=0}^{n} (−\frac{1}{3})^{i} F_{n+i−2}\binom{n}{i} = \frac{5^{(n−1)/2}}{3^{n−1}} .

Proof. These identities follow from equating the leading coefficients of the polynomials in Section 2 with their alternative forms obtained from the Lagrange interpolation formula, e.g., (25). In particular, (a) follows from Theorem 2 and (b) from Theorem 3. For even n,

(c) follows from Theorem 4 and (d) from Theorem 5. Similarly, for odd n, (e) and (f) also follow from Theorems 4 and 5, respectively.

Next, we give a two-parameter result generalizing Corollary 13(a).

Corollary 14. For all nonnegative integers n and k,

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

Proof. We proceed by induction. Since F_{1} = 1, Corollary 13(a) is the k = 1 case. The k = 2 case,

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

was established as Corollary 3.2 in our previous article [3]. For k ≥ 3, the result follows using the Fibonacci recurrence. For k = 0, subtracting Corollary 13(a) from (63) leaves

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

There are several direct applications of the results in Section 4.

Corollary 15. For positive integers n,

(a) ∑_{i=0}^{n} F_{n−i+2}\binom{n}{i} = F_{2n+2},

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

(c) ∑_{i=0}^{n}(−1)^{i}2^{n−i−1}F_{2n−2i+3}\binom{n − 1}{i} = F_{3n+2}.

Also, for n even,

(d) ∑_{i=0}^{n/2} 5^{i−1}2^{n−2i}F_{n−2i+2} (5\binom{n}{2i} − 10\binom{n}{2i − 1} + 4\binom{n}{2i − 2}) = 1,

(e) ∑_{i=0}^{n/2} 5^{i−1}3^{n−2i}F_{n−2i+2} (5\binom{n}{2i} − 15\binom{n}{2i − 1} + 9\binom{n}{2i − 2}) = L_{2n+1}

and, for n odd,

(f) − ∑_{i=0}^{(n+1)/2} 5^{i−2}2^{n−2i+1}F_{n−2i+3} (5\binom{n}{2i − 1} − 10\binom{n}{2i − 2} + 4\binom{n}{2i − 3}) = 1,

(g) − ∑_{i=0}^{(n+1)/2} 5^{i−2}3^{n−2i+1}F_{n−2i+3} (5\binom{n}{2i − 1} − 15\binom{n}{2i − 2} + 9\binom{n}{2i − 3}) = F_{2n+1}.

Proof. For (a), let x = n in (46). For (b), let x = n in (48). For (c), let x = n − 1 in (49). For (d), let x = n − 1 in (52) and, for (e), let x = n − 1 in (57). For (f), let x = n − 1 in (54) and, for (g), let x = n − 1 in (59).

The following several corollaries use the derivatives of the binomial polynomial expansions found in Section 4. We provide one detailed proof and notes for the others. Note that the terms δ_{n,ℓ} vary slightly for each result.

Corollary 16. For every integer n ≥ 2 and ℓ ≥ 0,

∑_{i=ℓ}^{n+ℓ}H_{i}F_{i−ℓ+2} (\binom{n + ℓ}{i} − 3\binom{n + ℓ − 1}{i} + \binom{n + ℓ − 2}{i})

= \frac{F_{2n+ℓ+2}}{n + ℓ} − \frac{F_{2n+ℓ−2}}{n + ℓ − 1} − δ_{n,ℓ}

− ∑_{j=0}^{ℓ−1} ( (H_{n+ℓ} (\frac{n + j}{n} ) (\frac{n + j − 1}{n − 1}) − 3H_{n+ℓ−1} (\frac{n + j − 1}{n − 1}) + H_{n+ℓ−2})

× F_{ℓ−j}\binom{n + j − 2}{j}),

where δ_{n,0} = \frac{1}{n} and δ_{n,ℓ} = \binom{n+ℓ−1}{n}(H_{n+ℓ−1} − H_{ℓ−1}) for ℓ > 0. Proof. Differentiating (46) with respect to x and evaluating at x = n + ℓ gives

P′_{n}(n + ℓ) = ∑_{i=0}^{n} F_{n−i+2}\binom{n + ℓ}{i} ∑_{j=0}^{i−1} \frac{1}{n + ℓ − j}

= ∑_{i=0}^{n} F_{n−i+2}\binom{n + ℓ}{i} (H_{n+ℓ} − H_{n+ℓ−i})

= H_{n+ℓ} ∑_{i=0}^{n} F_{n−i+2}\binom{n + ℓ}{i} − ∑_{i=0}^{n} H_{n+ℓ−i}F_{n−i+2}\binom{n + ℓ}{i}

= H_{n+ℓ}P_{n}(n + ℓ) − ∑_{i=0}^{n} H_{n+ℓ−i}F_{n−i+2}\binom{n + ℓ}{n + ℓ − i}

= H_{n+ℓ}(F_{2n+ℓ+2} − ∑_{i=1}^{ℓ} F_{i}\binom{n + ℓ − i}{n}) − ∑_{j=ℓ}^{n+ℓ} H_{j}F_{j−ℓ+2}\binom{n + ℓ}{j}, (64)

where the last equality uses Theorem 1.

Differentiating (5) with respect to x and evaluating at x = n + ℓ gives

P′_{n}(n + ℓ) − 3P′_{n−1}(n − 1 + ℓ) + P′_{n−2}(n − 2 + ℓ) = \binom{x − 1}{n} ∑_{j=0}^{n−1} \frac{1}{x − 1 − j} |_{x=n+ℓ} (65)

which, for ℓ = 0, becomes

lim_{x→n} \binom{x − 1}{n}\frac{1}{x − 1 − (n − 1)} = \frac{1}{n}

while, for ℓ > 0, is

\binom{n + ℓ − 1}{n} (H_{n+ℓ−1} − H_{ℓ−1}) ,

matching δ_{n,ℓ} as defined in the corollary statement.

Using (64) for P′ terms in (65) and rearranging gives

∑_{i=ℓ}^{n+ℓ} H_{i}F_{i−ℓ+2} (\binom{n + ℓ}{i} − 3\binom{n + ℓ − 1}{i} + \binom{n + ℓ − 2}{i})

= (H_{n+ℓ}F_{2n+2+ℓ} − 3H_{n−1+ℓ}F_{2n+ℓ} + H_{n−2+ℓ}F_{2n−2+ℓ}) − (H_{n+ℓ} ∑_{i=1}^{ℓ} F_{i}\binom{n + ℓ − i}{n}

− 3H_{n−1+ℓ} ∑_{i=1}^{ℓ} F_{i}\binom{n − 1 + ℓ − i}{n − 1} + H_{n−2+ℓ} ∑_{i=1}^{ℓ} F_{i}\binom{n − 2 + ℓ − i}{n − 2}) − δ_{n,ℓ}. (66)

The first grouped expression in (66) simplifies as

H_{n+ℓ}F_{2n+2+ℓ} − 3H_{n−1+ℓ}F_{2n+ℓ} + H_{n−2+ℓ}F_{2n−2+ℓ}

= (H_{n−2+ℓ} + \frac{1}{n + ℓ − 1} + \frac{1}{n + ℓ}) F_{2n+2+ℓ}

− 3 (H_{n−2+ℓ} + \frac{1}{n + ℓ − 1}) F_{2n+ℓ} + H_{n−2+ℓ}F_{2n−2+ℓ}

= H_{n−2+ℓ}(F_{2n+2+ℓ} − 3F_{2n+ℓ} + F_{2n−2+ℓ}) + \frac{F_{2n+2+ℓ} − 3F_{2n+ℓ}}{n + ℓ − 1} + \frac{F_{2n+2+ℓ}}{n + ℓ}

= \frac{F_{2n+ℓ+2}}{n + ℓ} − \frac{F_{2n+ℓ−2}}{n + ℓ − 1},

where the last equality uses (16).

The expression with summations in (66), using the identity \binom{n}{k} = \frac{n}{k} \binom{n−1}{k−1}, becomes

H_{n+ℓ} ∑_{i=1}^{ℓ} F_{i}\binom{n + ℓ − i}{n} − 3H_{n−1+ℓ} ∑_{i=1}^{ℓ} F_{i}\binom{n − 1 + ℓ − i}{n − 1} + H_{n−2+ℓ} ∑_{i=1}^{ℓ} F_{i}\binom{n − 2 + ℓ − i}{n − 2}

= ∑_{i=1}^{ℓ} ( (H_{n+ℓ} · \frac{n + ℓ − i}{n} · \frac{n − 1 + ℓ − i}{n − 1} − 3H_{n−1+ℓ} · \frac{n − 1 + ℓ − i}{n − 1} + H_{n−2+ℓ})

× F_{i}\binom{n − 2 + ℓ − i}{n − 2}).

Using these two expressions in (66) and reindexing by j = ℓ − i leads to the desired identity.

Corollary 17. For every integer n ≥ 3 and ℓ ≥ 0,

∑_{i=ℓ+1}^{n+ℓ}H_{i}F_{i−ℓ} (\binom{n + ℓ}{i} − 3\binom{n + ℓ − 1}{i} + \binom{n + ℓ − 2}{i})

= \frac{F_{2n+ℓ}}{n + ℓ} − \frac{F_{2n+ℓ−4}}{n + ℓ − 1} − δ_{n,ℓ}

− ∑_{j=0}^{ℓ−1} ( (H_{n+ℓ} (\frac{n + j − 1}{n − 1}) (\frac{n + j − 2}{n − 2}) − 3H_{n+ℓ−1} (\frac{n + j − 2}{n − 2}) + H_{n+ℓ−2})

× F_{ℓ−j}\binom{n + j − 3}{j}),

where δ_{n,0} = \frac{1}{n−1} and δ_{n,ℓ} = \binom{n+ℓ−2}{n−1}(H_{n+ℓ−2} − H_{ℓ−1}) for ℓ > 0. Proof. Here, differentiate (47), otherwise the proof follows the same structure as that of Corollary 16. Corollary 18. For every integer n ≥ 2 and ℓ ≥ 0,

(−1)^{ℓ} ∑_{i=ℓ}^{n+ℓ}(−1)^{i}H_{i}F_{2i−2ℓ+1} (\binom{n + ℓ}{i} + \binom{n + ℓ − 1}{i} − \binom{n + ℓ − 2}{i})

= (−1)^{n} (\frac{F_{n−ℓ+1}}{n + ℓ} + \frac{F_{n−ℓ−1}}{n + ℓ − 1}) − δ_{n,ℓ}

+ ∑_{i=0}^{ℓ−1} ( (H_{n+ℓ} (\frac{n + i}{n}) (\frac{n + i − 1}{n − 1}) + H_{n+ℓ−1} (\frac{n + i − 1}{n − 1}) − H_{n+ℓ−2})

× F_{i−ℓ}\binom{n + i − 2}{i}),

where δ_{n,0} = \frac{1}{n} and δ_{n,ℓ} = \binom{n+ℓ−1}{n}(H_{n+ℓ−1} − H_{ℓ−1}) for ℓ > 0. Proof. The proof is similar to that of Corollary 16, incorporating (48) and (6). Corollary 19. For every integer n ≥ 3 and ℓ ≥ 0,

(−1)^{ℓ} ∑_{i=ℓ+1}^{n+ℓ}(−1)^{i}H_{i}F_{2i−2ℓ} (\binom{n + ℓ}{i} + \binom{n + ℓ − 1}{i} − \binom{n + ℓ − 2}{i})

= (−1)^{n} (\frac{F_{n−ℓ}}{n + ℓ} + \frac{F_{n−ℓ−2}}{n + ℓ − 1}) + δ_{n,ℓ}

− ∑_{i=0}^{ℓ−1} ( (H_{n+ℓ} (\frac{n + i − 1}{n − 1}) (\frac{n + i − 2}{n − 2}) + H_{n+ℓ−1} (\frac{n + i − 2}{n − 2}) − H_{n+ℓ−2})

× F_{i−ℓ}\binom{n + i − 3}{i}),

where δ_{n,0} = \frac{1}{n−1} and δ_{n,ℓ} = \binom{n+ℓ−2}{n−1}(H_{n+ℓ−2} − H_{ℓ−1}) for ℓ > 0. Proof. The proof is similar to that of Corollary 16, incorporating (50) and (6). Corollary 20. For every integer n ≥ 2 and ℓ ≥ 0,

(−1)^{ℓ} ∑_{i=ℓ}^{n+ℓ}(−1)^{i}2^{i−ℓ−1}H_{i}F_{2i−2ℓ+3} (\binom{n + ℓ}{i} + 4\binom{n + ℓ − 1}{i} − \binom{n + ℓ − 2}{i})

= \frac{(−1)^{n}}{2^{ℓ+1}} (\frac{F_{3n+ℓ+3}}{n + ℓ} + \frac{F_{3n+ℓ−3}}{n + ℓ − 1}) − δ_{n,ℓ}

+ ∑_{i=0}^{ℓ−1} ( (H_{n+ℓ} (\frac{n + i}{n}) (\frac{n + i − 1}{n − 1}) + 4H_{n+ℓ−1} (\frac{n + i − 1}{n − 1}) − H_{n+ℓ−2})

× \frac{F_{ℓ−i}}{2^{ℓ−i+1}} \binom{n + i − 2}{i}),

where δ_{n,0} = \frac{1}{n} and δ_{n,ℓ} = \binom{n+ℓ−1}{n}(H_{n+ℓ−1} − H_{ℓ−1}) for ℓ > 0. Proof. The proof is similar to that of Corollary 16, incorporating (49) and (9). Corollary 21. For every integer n ≥ 3 and ℓ ≥ 0,

(−1)^{ℓ} ∑_{i=ℓ+1}^{n+ℓ}(−1)^{i}2^{i−ℓ−1}H_{i}F_{2i−2ℓ} (\binom{n + ℓ}{i} + 4\binom{n + ℓ − 1}{i} − \binom{n + ℓ − 2}{i})

= \frac{(−1)^{n}}{2^{ℓ+1}} (\frac{F_{3n+ℓ}}{n + ℓ} + \frac{F_{3n+ℓ−6}}{n + ℓ − 1}) + δ_{n,ℓ}

− ∑_{i=0}^{ℓ−1} ( (H_{n+ℓ} (\frac{n + i − 1}{n − 1}) (\frac{n + i − 2}{n − 2}) + 4H_{n+ℓ−1} (\frac{n + i − 2}{n − 2}) − H_{n+ℓ−2})

× \frac{F_{ℓ−i}}{2^{ℓ−i+1}} \binom{n + i − 3}{i}),

where δ_{n,0} = \frac{1}{n−1} and δ_{n,ℓ} = \binom{n+ℓ−2}{n−1}(H_{n+ℓ−2} − H_{ℓ−1}) for ℓ > 0. Proof. The proof is similar to that of Corollary 16, incorporating (51) and (9).

We record a few of the simpler particular identities that follow from the previous corollaries.

Corollary 22. For every integer n ≥ 2,

(a) ∑_{i=1}^{n} H_{i}F_{i+2} (\binom{n}{i} − 3\binom{n − 1}{i} + \binom{n − 2}{i}) = \frac{F_{2n+2} − 1}{n} − \frac{F_{2n−2}}{n − 1} ,

(b) ∑_{i=1}^{n} H_{i}F_{i} (\binom{n}{i} − 3\binom{n − 1}{i} + \binom{n − 2}{i}) = \frac{F_{2n}}{n} − \frac{F_{2n−4} − 1}{n − 1},

(c) ∑_{i=1}^{n}(−1)^{i}H_{i}F_{2i+1} (\binom{n}{i} + \binom{n − 1}{i} − \binom{n − 2}{i}) = (−1)^{n} (\frac{F_{n−1}}{n − 1} + \frac{F_{n+1}}{n} ) − \frac{1}{n},

(d) ∑_{i=1}^{n}(−1)^{i}H_{i}F_{2i} (\binom{n}{i} + \binom{n − 1}{i} − \binom{n − 2}{i}) = (−1)^{n} (\frac{F_{n}}{n} + \frac{F_{n−2}}{n − 1}) + \frac{1}{n − 1},

(e) ∑_{i=1}^{n}(−2)^{i}H_{i}F_{2i+3} (\binom{n}{i} + 4\binom{n − 1}{i} − \binom{n − 2}{i}) = (−1)^{n} (\frac{F_{3n−3}}{n − 1} + \frac{F_{3n+3}}{n} ) − \frac{2}{n},

(f) ∑_{i=1}^{n}(−2)^{i}H_{i}F_{2i} (\binom{n}{i} + 4\binom{n − 1}{i} − \binom{n − 2}{i}) = (−1)^{n} (\frac{F_{3n}}{n} + \frac{F_{3n−6}}{n − 1} ) + \frac{2}{n − 1},

(g) ∑_{i=1}^{n} H_{i+1}F_{i} (\binom{n + 1}{i + 1} − 3\binom{n}{i + 1} + \binom{n − 1}{i + 1}) = \frac{F_{2n+1} − 1}{n + 1} − \frac{F_{2n−3} + 2}{n},

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

Proof. Identities (a)–(f) follow from Corollaries 16 through 21 with ℓ = 0, respectively. Identities (g) and (h) follow from Corollary 17 with ℓ = 1 and ℓ = 2, respectively.

In fact, each value of ℓ in each of Corollaries 16 through 21 produces an identity.

We conclude this section with results particular to the polynomials S_{n}(x) of Theorem 4. Notice that the recurrence (12) combines S_{n+1}(x) and S_{n−1}(x − 2) into a scaled binomial polynomial; this simplification is the core of the following results. The analogous (14) does not combine as nicely, so there are not similar results based on T_{n}(x).

We rewrite (12) as

S_{k+1}(x + 1) − S_{k−1}(x − 1) = −5^{⌊ \frac{k+1}{2} ⌋}\binom{x}{k + 1}

and differentiate with respect to x on both sides,

S′_{k+1}(x + 1) − S′_{k−1}(x − 1) = −5^{⌊ \frac{k+1}{2} ⌋}\binom{x}{k + 1} ∑_{i=0}^{k} \frac{1}{x − i}.

Letting x = k gives

S′_{k+1}(k + 1) − S′_{k−1}(k − 1) = −\frac{5^{⌊ \frac{k+1}{2} ⌋}}{k + 1} .  (67)

That equation informs our last corollary. Corollary 23. With b_{k} and c_{k} as defined in (2) and (3), and for every n ≥ 1,

(a) ∑_{k=1}^{2n}(−2)^{k}5^{n−⌊ \frac{k}{2} ⌋}b_{k}H_{k}\binom{2n}{k} = 2H_{2n} − ∑_{k=1}^{n} \frac{5^{k}}{k} ,

(b) ∑_{k=1}^{2n+1}(−2)^{k−1}5^{n−⌊ \frac{k}{2} ⌋}b_{k}H_{k}\binom{2n + 1}{k} = ∑_{k=0}^{n} \frac{5^{k}}{2k + 1},

(c) ∑_{k=1}^{2n}(−2)^{k−1}5^{n−⌊ \frac{k−1}{2} ⌋}c_{k}H_{k}\binom{2n}{k} = − ∑_{k=1}^{n} \frac{5^{k}}{2k − 1},

(d) ∑_{k=1}^{2n+1}(−2)^{k}5^{n−⌊ \frac{k}{2} ⌋+ \frac{1+(−1)^{k}}{2}} c_{k}H_{k}\binom{2n + 1}{k} = −2H_{2n+1} + ∑_{k=1}^{n} \frac{5^{k}}{k} .

Proof. For (a), summing (67) evaluated at k = 1, 3, …, 2n − 1 gives

S′_{2n}(2n) = S′_{2n}(2n) − S′_{0}(0) = −\frac{5}{2} − \frac{5^{2}}{4} − ⋯ − \frac{5^{n}}{2n} = −\frac{1}{2} ∑_{k=1}^{n} \frac{5^{k}}{k} .  (68)

Next, we find a different expression for S′_{2n}(2n). Differentiating (53) with respect to x and evaluating at x = 2n gives

S′_{2n}(2n) = ∑_{i=0}^{2n}(−1)^{i+1}5^{⌊ \frac{i+1}{2} ⌋}2^{2n−i−1}b_{2n−i}\binom{2n}{i} ∑_{j=0}^{i−1} \frac{1}{2n − j}

= ∑_{i=0}^{2n}(−1)^{i+1}5^{⌊ \frac{i+1}{2} ⌋}2^{2n−i−1}b_{2n−i}\binom{2n}{i}(H_{2n} − H_{2n−i})

= H_{2n} ∑_{i=0}^{2n}(−1)^{i+1}5^{⌊ \frac{i+1}{2} ⌋}2^{2n−i−1}b_{2n−i}\binom{2n}{i}

− ∑_{i=0}^{2n}(−1)^{i+1}5^{⌊ \frac{i+1}{2} ⌋}2^{2n−i−1}b_{2n−i}H_{2n−i}\binom{2n}{i}

= H_{2n}S_{2n}(2n) − ∑_{i=0}^{2n}(−1)^{i+1}5^{⌊ \frac{i+1}{2} ⌋}2^{2n−i−1}b_{2n−i}H_{2n−i}\binom{2n}{2n − i}

= −H_{2n} − ∑_{k=0}^{2n}(−1)^{2n−k+1}5^{⌊ \frac{2n−k+1}{2} ⌋}2^{k−1}b_{k}H_{k}\binom{2n}{k}

= −H_{2n} + \frac{1}{2} ∑_{k=0}^{2n}(−2)^{k}5^{n−⌊ \frac{k}{2} ⌋}b_{k}H_{k}\binom{2n}{k}.

Combining this with (68) establishes (a).

The verification of (b) is very similar: Sum (67) evaluated at k = 2, 4, …, 2n and use (55) for the other expression of S′_{2n}(2n).

For (c), differentiating (52) with respect to x and evaluating at x = 2n gives

S′_{2n}(2n) = − ∑_{i=0}^{n} 5^{i−1}2^{2n−2i}F_{2n−2i+2} (5\binom{2n + 1}{2i}(H_{2n+1} − H_{2n−2i+1})

− 10\binom{2n + 1}{2i − 1}(H_{2n+1} − H_{2n−2i+2}) + 4\binom{2n + 1}{2i − 2}(H_{2n+1} − H_{2n−2i+3}))

= H_{2n+1}S_{2n}(2n) + ∑_{i=0}^{n} 5^{i}2^{2n−2i}F_{2n−2i+2}H_{2n−2i+1}\binom{2n + 1}{2n − 2i + 1}

− ∑_{i=0}^{n} 5^{i}2^{2n−2i+1}F_{2n−2i+2}H_{2n−2i+2}\binom{2n + 1}{2n − 2i + 2}

+ ∑_{i=0}^{n} 5^{i−1}2^{2n−2i+2}F_{2n−2i+2}H_{2n−2i+3}\binom{2n + 1}{2n − 2i + 3}

= −H_{2n+1} + ∑_{k=0}^{n} 5^{n−k}2^{2k}F_{2k+2}H_{2k+1}\binom{2n + 1}{2k + 1}

− ∑_{k=0}^{n} 5^{n−k+1}2^{2k−1}F_{2k}H_{2k}\binom{2n + 1}{2k}

+ ∑_{k=0}^{n} 5^{n−k}2^{2k}F_{2k}H_{2k+1}\binom{2n + 1}{2k + 1}

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

− ∑_{k=0}^{n} 5^{n−k+1}2^{2k−1}F_{2k}H_{2k}\binom{2n + 1}{2k}

= −H_{2n+1} + ∑_{k=0}^{n} 5^{n−k}2^{2k}L_{2k+1}H_{2k+1}\binom{2n + 1}{2k + 1}

− ∑_{k=0}^{n} 5^{n−k+1}2^{2k−1}F_{2k}H_{2k}\binom{2n + 1}{2k}

using (19). Doubling both sides, recalling the definition of the c_{k}, and combining with (68) gives (c).

The verification of (d) is similar, differentiating (54) and evaluating at x = 2n + 1.

6 Further work

We believe that the coefficients of the various polynomials, with initial values given in the tables of Section 2, merit further study.

Also, the sum in Corollary 22(b) can be rewritten

∑_{i=1}^{n} H_{i}F_{i} (\binom{n}{i}− 3\binom{n − 1}{i} + \binom{n − 2}{i})

= ∑_{i=1}^{n} H_{i}F_{i}\binom{n}{i} − 3 ∑_{i=1}^{n−1} H_{i}F_{i}\binom{n − 1}{i} + ∑_{i=1}^{n−2} H_{i}F_{i}\binom{n − 2}{i}.

With the other side of Corollary 22(b), we have the sum W_{n} = ∑_{i=1}^{n} H_{i}F_{i}\binom{n}{i} satisfying the recurrence

W_{n} − 3W_{n−1} + W_{n−2} = \frac{F_{2n}}{n} − \frac{F_{2n−4} − 1}{n − 1}  (69)

for all n ≥ 2. A solution to the nonhomogeneous second order linear recurrence (69), with initial condition W_{0} = 0 and W_{1} = 1, would give us a closed form for ∑_{i=1}^{n} H_{i}F_{i}\binom{n}{i}. Each identity in Corollary 22 could give rise to a similar recurrence.

7 Acknowledgments

We appreciate the helpful comments of the anonymous referee.

References

[1] P. J. Cahen and J. L. Chabert, Integer-valued Polynomials, Surveys and Monographs 48, American Mathematical Society, 1997.

[2] P. J. Cahen and J. L. Chabert, What you should know about integer-valued polynomials, Amer. Math. Monthly 123 (2016), 311–337.

[3] B. Hopkins and A. Tangboonduangjit, Fibonacci-producing rational polynomials, Fibonacci Quart. 56 (2018), 303–312.

[4] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, OEIS Foundation

   Inc., https://oeis.org.

[5] S. Vajda, Fibonacci and Lucas Numbers, and the Golden Section, Dover, 2008.

2020 Mathematics Subject Classification: Primary 11B39; Secondary 11C08. Keywords: interpolating polynomial, polynomial recurrence, Fibonacci number, Lucas number, harmonic number, identity.

(Concerned with sequences \underline{A000032}, \underline{A000045}, \underline{A001008}, \underline{A002805}, \underline{A005013}, \underline{A005247}, \underline{A007318}, \underline{A052568}, and \underline{A078700}.)

Received February 14 2022; revised versions received March 13 2022; March 16 2022. Published in Journal of Integer Sequences, March 24 2022.

Return to Journal of Integer Sequences home page.