Some Applications of the Lagrange Inversion Formula for the k-Fibonacci Numbers

Bakir Farhi Laboratoire de Mathématiques appliquées Faculté des Sciences Exactes Université de Bejaia 06000 Bejaia Algeria

                  bakir.farhi@univ-bejaia.dz

Abstract We provide summation formulas for the k-Fibonacci numbers (k ∈ ℤ, k ≥ 2) and their asymptotic equivalents in terms of generalized binomial coefficients. Our main tools are the Lagrange inversion formula and one of its consequences due to Hermite.

1 Introduction and notation

Throughout this paper, we let ℕ denote the set of positive integers and ℕ_{0} := ℕ ∪ {0} the set of nonnegative integers. Next, the (compositional) inverse function of a function f is denoted by f^{⟨−1⟩} and the coefficient of z^{n} (n ∈ ℕ_{0}) in a power series φ(z) is denoted by [z^{n}]φ(z). Further, we let \binom{a}{b} (a, b ∈ ℤ) denote the generalized binomial coefficient defined by

\binom{a}{b} := \begin{cases}\frac{a(a−1)···(a−b+1)}{b!}, & if b ≥ 0; \\ \binom{a}{a−b}, & if a ≥ b; \\ 0, & if a < b < 0. \end{cases}  (1)

Using this definition, we easily check the following formulas:

\binom{a}{b} = \binom{a − 1}{b − 1} + \binom{a − 1}{b}  (∀(a, b) ∈ ℤ^{2} \ \{(0, 0)\}),  (2)

\binom{a}{b} = \begin{cases}(−1)^{b−1}\binom{b−a−1}{b}, & if b ≤ a < 0; \\ (−1)^{b}\binom{b−a−1}{b}, & else. \end{cases}  (∀(a, b) ∈ ℤ^{2}).  (3)

For x ∈ ℝ and n ∈ ℤ, we let x\underline{n} denote the n^{th} falling factorial power of x, defined by

x\underline{n} := \begin{cases}x(x − 1) ⋯ (x − n + 1), & if n > 0; \\ 1, & if n = 0; \\ ((x + 1)(x + 2) ⋯ (x − n))^{−1} , & if n < 0. \end{cases}

(See [4, §2.6].) For a given integer k ≥ 2, the k-Fibonacci sequence is the integer sequence (F_{n}^{(k)})_{n∈ℕ_{0}} given by the recurrence relation

F_{n+k}^{(k)} = F_{n}^{(k)} + F_{n+1}^{(k)} + ⋯ + F_{n+k−1}^{(k)}  (∀n ∈ ℕ_{0}),  (4)

with the initial values F_{0}^{(k)} = F_{1}^{(k)} = ⋯ = F_{k−2}^{(k)} = 0 and F_{k−1}^{(k)} = 1. The special case k = 2 corresponds to the usual Fibonacci sequence, simply denoted by (F_{n})_{n∈ℕ_{0}} and given by

\begin{cases}F_{0} = 0, F_{1} = 1, \\ F_{n+2} = F_{n} + F_{n+1} (∀n ∈ ℕ_{0}) \end{cases}

(see the sequence \underline{A000045} in the OEIS [10]). The above linear recurrence relation (4) of order k for the k-Fibonacci sequence easily implies the following simpler linear recurrence relation of order (k + 1):

F_{n+k+1}^{(k)} = 2F_{n+k}^{(k)} − F_{n}^{(k)}  (∀n ∈ ℕ_{0})  (5)

(see [6] for the details). By relying on (5), we easily check that we have

\begin{aligned}F_{n}^{(k)} & = 2^{n−k}  for k ≤ n < 2k, \\ F_{2k}^{(k)} & = 2^{k} − 1. \end{aligned}  (6)

The k-Fibonacci sequence plays an important role in many areas of mathematics, including discrete mathematics and combinatorics. Here is a simple combinatorial interpretation: given an integer k ≥ 2, the number of possible ways of writing a positive integer n as a sum of numbers, all belonging to the set {1, 2, …, k} (taking into account the permutations), is exactly F_{n+k−1}^{(k)}. To find a closed form of F_{n}^{(k)}, the theory of linear recurrence sequences associates the linear recurrence (4) with the polynomial equation (known as its characteristic equation)

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

Multiplying the both sides of (7) by (x−1) and rearranging, we obtain the simpler polynomial equation

x^{k+1} − 2x^{k} + 1 = 0,  (8)

which is nothing else than the characteristic equation associated to the linear recurrence (5). The closed form of F_{n}^{(k)} then depends on the complex roots of Equation (7) and their multiplicities. Furthermore, in order to establish a simple asymptotic equivalent for F_{n}^{(k)} (as n → +∞), it is necessary to locate the complex roots of Equation (7) in the complex plane, a topic that has been investigated by several authors. Using the famous Rouché theorem of complex analysis, Miles [8] proved that Equation (7) has exactly k − 1 pairwise distinct complex roots in the open unit disk D(0, 1) of the complex plane and a unique complex root ρ_{k} of modulus greater than 1; more precisely, ρ_{k} is real and belongs to the interval (1, 2). Wolfram [14] showed that we have more precisely

2 − \frac{2}{2^{k}} < ρ_{k} < 2.  (9)

For the special case k = 2, ρ_{k} is nothing else than the famous golden ratio, commonly denoted by ϕ (ϕ = \frac{\sqrt{5}+1}{2} = 1.618 …). Miller [9] found an elementary way to prove the Miles result, which relies on Descartes’s rules of signs. Letting α_{k,1}, α_{k,2}, …, α_{k,k} = ρ_{k} denote the complex roots of Equation (7), the theory of linear recurrence sequences shows that F_{n}^{(k)} has the closed form F_{n}^{(k)} = ∑_{ℓ=1}^{k} λ_{k,ℓ}α_{k,ℓ}^{n} (∀n ∈ ℕ_{0}), where the λ_{k,ℓ}’s are complex numbers (not depending on n) which can be calculated by relying on the initial values of the sequence (F_{n}^{(k)})_{n}. Spickerman and Joyner [11] showed that

λ_{k,ℓ} = \frac{α_{k,ℓ}^{k+1} − α_{k,ℓ}^{k}}{α_{k,ℓ} (2α_{k,ℓ}^{k} − (k + 1))} (∀ℓ ∈ \{1, 2, …, k\}),

and Dresden [3] simplified this to

λ_{k,ℓ} = \frac{α_{k,ℓ} − 1}{α_{k,ℓ} (2 + (k + 1)(α_{k,ℓ} − 2))} = \frac{α_{k,ℓ} − 1}{α_{k,ℓ} ((k + 1)α_{k,ℓ} − 2k)} (∀ℓ ∈ \{1, 2, …, k\}).

So we have

F_{n}^{(k)} = ∑_{ℓ=1}^{k} \frac{α_{k,ℓ} − 1}{(k + 1)α_{k,ℓ} − 2k} α_{k,ℓ}^{n−1} (∀n ∈ ℕ_{0}).

Then, since ρ_{k} is the largest root of (7) in modulus, we derive the following asymptotic equivalence (as n → +∞):

F_{n}^{(k)} ∼_{+∞} \frac{ρ_{k} − 1}{(k + 1)ρ_{k} − 2k} ρ_{k}^{n−1}.  (10)

Let us denote the expression on the right-hand side of (10) by As_{n}^{(k)}; that is

As_{n}^{(k)} := \frac{ρ_{k} − 1}{(k + 1)ρ_{k} − 2k} ρ_{k}^{n−1}  (11)

(for all integer k ≥ 2 and all n ∈ ℕ_{0}). Next, for all integer k ≥ 2, define

ε_{k} := 2 − ρ_{k}.

From (9), we have that ε_{k} ∈ (0, 2^{1−k}) ⊂ (0, 1/2). Furthermore, from the fact that ρ_{k} is a root of Equation (8), we derive that

ε_{k} = \frac{1}{(2 − ε_{k})^{k}} ,  (12)

which is a crucial equality for our purpose.

The goal of this paper is first to represent ρ_{k}^{n} and As_{n}^{(k)} as series involving binomial coefficients. Then, by judiciously truncating the series related to As_{n}^{(k)}, we derive a representation of F_{n}^{(k)} as a finite sum involving binomial coefficients. Our results are essentially obtained by employing the Lagrange inversion formula and one of its consequences due to Hermite (see §2). While some of these results have been previously pointed out by other authors, they were often accompanied by ad hoc proofs, and in some instances, contained mistakes (see §3 for detailed discussion).

2 The Lagrange inversion formula

The Lagrange inversion formula is one of the most important formulas of combinatorics. In its general form, it can be stated as follows

Theorem 1 (The Lagrange inversion formula). Let α, z_{0} ∈ ℂ and f be a complex analytic function of z at a neighborhood of z_{0}. Let also w = w(z) be a complex analytic function of z at a neighborhood of z_{0}, which is implicitly defined by

w = z_{0} + αf(w).  (13)

Then for every complex analytic function g of z at a neighborhood of z_{0}, we have (for |α| sufficiently small)

g(w) = g(z_{0}) + ∑_{n=1}^{+∞} \frac{α^{n}}{n!} ((\frac{d}{dz} )^{n−1}(f^{n}g′)) (z_{0}).

Taking in particular g(z) = z, we get (for |α| sufficiently small)

w = z_{0} + ∑_{n=1}^{+∞} \frac{α^{n}}{n!} ((\frac{d}{dz} )^{n−1}(f^{n})) (z_{0}).

Note that the last part of this important theorem was proved in 1770 by Lagrange [7], who applied it to solve the Kepler equation y = x + α sin y, while its generalization (i.e., the first part of Theorem 1) was obtained by Bürmann [1] in 1798. One simple way to prove Theorem 1 uses contour integration in the complex plane, while other more elementary approaches employ algebraic techniques on formal series (see, e.g., [2, 12]) or utilize induction (see [13]). From Theorem 1, we derive the following interesting corollary, which is due to Hermite (see Comtet’s book [2, §3.8]):

Corollary 2 (Hermite). Let φ be a complex analytic function at a neighborhood of 0 such that φ(0) ≠ 0 and let ψ be the compositional inverse function of the function z → \frac{z}{φ(z)} at a

neighborhood of 0 (ψ exists because (\frac{z}{φ(z)})′ (0) = \frac{1}{φ(0)} ≠ 0). Then for every complex function g, which is analytic at a neighborhood of 0, we have

\frac{z · (g ∘ ψ)(z)}{ψ(z) · ((\frac{z}{φ(z)})′ ∘ ψ(z))} = ∑_{n=0}^{+∞} z^{n}[z^{n}] (g(z)φ(z)^{n}) .

Since this last result of Hermite is unfamiliar, we have preferred to include its proof in this paper.

Proof of Corollary 2. Let f be a primitive of the function \frac{g}{φ} at a neighborhood of 0. By

definition of ψ, we have (\frac{z}{φ(z)} ∘ ψ) (z) = z; that is ψ is implicitly given by

ψ(z) = 0 + z · (φ ∘ ψ) (z).  (14)

So by applying the first part of Theorem 1 with (14) filling the role of (13); that is with w replaced by ψ, f by φ, α by z, z_{0} by 0, and g by f, we get

(f ∘ ψ) (z) = f(0) + ∑_{n=1}^{+∞} \frac{z^{n}}{n!} ((\frac{d}{dz} )^{n−1}(φ(z)^{n}f′(z))) (0)

= f(0) + ∑_{n=1}^{+∞} \frac{z^{n}}{n} [z^{n−1}] (g(z)φ(z)^{n−1}) (since f′ = \frac{g}{φ})

= f(0) + ∑_{n=0}^{+∞} \frac{z^{n+1}}{n + 1} [z^{n}] (g(z)φ(z)^{n}) .

By differentiating with respect to z, we get

ψ′(z) · (f′ ∘ ψ) (z) = ∑_{n=0}^{+∞} z^{n} [z^{n}] (g(z)φ(z)^{n}) .

But since

ψ′(z) = ((\frac{z}{φ(z)})^{⟨−1⟩})′ = \frac{1}{(\frac{z}{φ(z)})′ ∘ ψ(z)}

and

(f′ ∘ ψ) (z) = (\frac{g}{φ} ∘ ψ) (z) = \frac{(g ∘ ψ)(z)}{(φ ∘ ψ)(z)} = \frac{1}{ψ(z)} · \frac{ψ(z)}{(φ ∘ ψ)(z)} · (g ∘ ψ) (z)

= \frac{1}{ψ(z)} · \underbrace{(\frac{z}{φ(z)} ∘ ψ(z))}_{=z} · (g ∘ ψ) (z) = \frac{z}{ψ(z)} · (g ∘ ψ) (z),

it follows that

\frac{z · (g ∘ ψ)(z)}{ψ(z) · ((\frac{z}{φ(z)})′ ∘ ψ(z))} = ∑_{n=0}^{+∞} z^{n}[z^{n}] (g(z)φ(z)^{n}) ,

as required.

3 The results and the proofs

We begin with the following result, which expresses the powers of ρ_{k} (k ≥ 2) as real series involving binomial coefficients.

Theorem 3. For all positive integers k and n, with k ≥ 2, we have

ρ_{k}^{n} = 2^{n} − n2^{n−k−1} ∑_{ℓ=0}^{+∞} \frac{1}{ℓ + 1}\binom{k(ℓ + 1) + ℓ − n}{ℓ}\frac{1}{2^{(k+1)ℓ}} .

In particular, we have

ρ_{k} = 2 − \frac{1}{2^{k}} ∑_{ℓ=0}^{+∞} \frac{1}{ℓ + 1}\binom{k(ℓ + 1) + ℓ − 1}{ℓ}\frac{1}{2^{(k+1)ℓ}} .

Proof. Let k and n be two fixed positive integers with k ≥ 2. By applying the first part of Theorem 1 with (12) filling the role of (13); that is with w = ε_{k}, f(z) = (2 − z)^{−k}, α = 1, z_{0} = 0, and g(z) = (2 − z)^{n}, we get

(2 − ε_{k})^{n} = 2^{n} + ∑_{ℓ=1}^{+∞} \frac{1}{ℓ!} ((\frac{d}{dz} )^{ℓ−1}((2 − z)^{−kℓ}(−n(2 − z)^{n−1}))) (0)

= 2^{n} − n ∑_{ℓ=1}^{+∞} \frac{1}{ℓ!} ((\frac{d}{dz} )^{ℓ−1}(2 − z)^{−kℓ+n−1}) (0)

= 2^{n} − n ∑_{ℓ=1}^{+∞} \frac{1}{ℓ} [z^{ℓ−1}] (2 − z)^{−kℓ+n−1}.

But according to the generalized binomial formula and (3), we have

[z^{ℓ−1}] (2 − z)^{−kℓ+n−1} = \binom{−kℓ + n − 1}{ℓ − 1}2^{−kℓ+n−ℓ}(−1)^{ℓ−1} = \binom{kℓ − n + ℓ − 1}{ℓ − 1}\frac{2^{n}}{2^{(k+1)ℓ}}

for all ℓ ∈ ℕ. Thus

(2 − ε_{k})^{n} = 2^{n} − n ∑_{ℓ=1}^{+∞} \frac{1}{ℓ}\binom{kℓ − n + ℓ − 1}{ℓ − 1}\frac{2^{n}}{2^{(k+1)ℓ}}

= 2^{n} − n ∑_{ℓ=0}^{+∞} \frac{1}{ℓ + 1}\binom{k(ℓ + 1) + ℓ − n}{ℓ}\frac{2^{n}}{2^{(k+1)(ℓ+1)}} ;

that is

ρ_{k}^{n} = 2^{n} − n2^{n−k−1} ∑_{ℓ=0}^{+∞} \frac{1}{ℓ + 1}\binom{k(ℓ + 1) + ℓ − n}{ℓ}\frac{1}{2^{(k+1)ℓ}} ,

as required.

Remark 4.

1. In the proof of Theorem 3, we have omitted the verification of the convergence of the series ∑_{ℓ=0}^{+∞} \frac{1}{ℓ+1} \binom{k(ℓ+1)+ℓ−n}{ℓ} \frac{1}{2^{(k+1)ℓ}}. Note that this convergence can be easily confirmed by using, for example, the elementary upper bounds \binom{m}{ℓ} ≤ \frac{2^{m}}{\sqrt{m+2}} (for 1 ≤ ℓ ≤ m).

2. Actually, the formula of ρ_{k} in the second part of Theorem 3 was already discovered by Wolfram [14], who obtained it in a more complicated way.

3. As its proof shows, Theorem 3 is actually valid even for n ∈ ℤ. The particular cases n = −1 and n = k provide the results of Hare et al. [5, Theorem 1.1] (notice that ρ_{k}^{k} = \frac{1}{2−ρ_{k}}).

4. Theorem 3 can be also obtained by using the generalized binomial series and the generalized binomial formula, investigated in [4, §5.4]. Indeed, according to [4], the generalized binomial series ℬ_{t} (t ∈ ℝ) is defined by

ℬ_{t}(z) := ∑_{ℓ=0}^{+∞}(tℓ)\underline{ℓ−1} \frac{z^{ℓ}}{ℓ!}

and satisfies the functional equation:

ℬ_{t}(z)^{1−t} − ℬ_{t}(z)^{−t} = z.  (15)

For all r ∈ ℝ, we have in addition the generalized binomial formula:

ℬ_{t}(z)^{r} = ∑_{ℓ=0}^{+∞} \binom{tℓ + r}{ℓ}\frac{r}{tℓ + r}z^{ℓ}  (16)

(setting t = 0, we obtain the usual binomial formula). Now, giving an integer k ≥ 2, by transforming the equality ρ_{k}^{k+1} − 2ρ_{k}^{k} + 1 = 0 into (\frac{1}{2}ρ_{k})^{1+k} − (\frac{1}{2}ρ_{k})^{k} = −\frac{1}{2^{k+1}} and comparing this with (15), we derive that ρ_{k} = 2ℬ_{−k} (−\frac{1}{2^{k+1}} ). The formula of Theorem 3 then follows by combining this last formula with the generalized binomial formula (16).

By setting k to 2 in Theorem 3, we derive important formulas for the golden ratio ϕ and its powers. More precisely, we obtain the following corollary:

Corollary 5. For every positive integer n, we have

ϕ^{n} = 2^{n} − n2^{n−3} ∑_{ℓ=0}^{+∞} \frac{1}{ℓ + 1}\binom{3ℓ + 2 − n}{ℓ}\frac{1}{2^{3ℓ}} .

In particular, we have

ϕ = 2 − ∑_{ℓ=0}^{+∞} \frac{1}{ℓ + 1}\binom{3ℓ + 1}{ℓ}\frac{1}{2^{3ℓ+2}} .  □

More interestingly, we are going to find representations as series (analogous to those of Theorem 3) for the asymptotic equivalent As_{n}^{(k)} of F_{n}^{(k)}. To achieve this, we rely on the following key theorem:

Theorem 6. For all integers k and a, with k ≥ 2, we have

∑_{ℓ=0}^{+∞} \binom{(k + 1)ℓ + a}{ℓ}2^{−(k+1)ℓ} = 2^{a+1} · \frac{ρ_{k}^{−a}}{(k + 1)ρ_{k} − 2k} .

Proof. Let k and a be fixed integers, with k ≥ 2. We apply Corollary 2 for the functions φ(z) = (2 − z)^{−k} and g(z) = (2 − z)^{−a−1}, which are both analytic at a neighborhood of 0 and we have φ(0) = 2^{−k} ≠ 0. In this situation, the compositional inverse function ψ of the function z ↦ \frac{z}{φ(z)} = z(2 − z)^{k} (at a neighborhood of 0) satisfies (according to (12)): ψ(1) = ε_{k}. So by specializing in formula of Corollary 2 the variable z to 1, we get

\frac{1 · (g ∘ ψ)(1)}{ψ(1) · ((z(2 − z)^{k})′ ∘ ψ) (1)} = ∑_{ℓ=0}^{+∞} 1^{ℓ}[z^{ℓ}](2 − z)^{−kℓ−a−1}.

But since ψ(1) = ε_{k} (as clarified above), (z(2 − z)^{k})′ = (2 − z)^{k−1} (2 − (k + 1)z), and for all ℓ ∈ ℕ_{0}: [z^{ℓ}](2 − z)^{−kℓ−a−1} = \binom{−kℓ−a−1}{ℓ}2^{−kℓ−a−1−ℓ}(−1)^{ℓ} = \binom{(k+1)ℓ+a}{ℓ}2^{−(k+1)ℓ−a−1} (by using the generalized binomial formula and then (3)), it follows that

\frac{(2 − ε_{k})^{−a−1}}{ε_{k}(2 − ε_{k})^{k−1} (2 − (k + 1)ε_{k})} = ∑_{ℓ=0}^{+∞} \binom{(k + 1)ℓ + a}{ℓ}2^{−(k+1)ℓ−a−1}.

Finally, since ε_{k}(2 − ε_{k})^{k} = 1 (according to (12)), 2 − ε_{k} = ρ_{k}, and 2 − (k + 1)ε_{k} = 2 − (k + 1)(2 − ρ_{k}) = (k + 1)ρ_{k} − 2k, we conclude to

\frac{ρ_{k}^{−a}}{(k + 1)ρ_{k} − 2k} = ∑_{ℓ=0}^{+∞} \binom{(k + 1)ℓ + a}{ℓ}2^{−(k+1)ℓ−a−1},

which immediately gives the required formula of the theorem.

Remark 7. The convergence of the series in the formula of Theorem 6 can be verified by using, for example, the Stirling formula n! ∼_{+∞} n^{n}e^{−n}\sqrt{2πn}.

Relying on Theorem 6, we are now able to provide a series representation (involving binomial coefficients) for the asymptotic equivalent As_{n}^{(k)} of F_{n}^{(k)}. This is the subject of the following theorem:

Theorem 8. For all nonnegative integers k and n, with k ≥ 2 and n ≠ 1, we have

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

Proof. Let k and n be two fixed nonnegative integers such that k ≥ 2 and n ≠ 1. By applying Theorem 6 for a = −n, we get

∑_{ℓ=0}^{+∞} \binom{(k + 1)ℓ − n}{ℓ}2^{−(k+1)ℓ} = 2^{−n+1} · \frac{ρ_{k}^{n}}{(k + 1)ρ_{k} − 2k} .  (17)

Similarly, by applying Theorem 6 for a = k + 1 − n, we get

∑_{ℓ=0}^{+∞} \binom{(k + 1)ℓ + k + 1 − n}{ℓ}2^{−(k+1)ℓ} = 2^{k+2−n} · \frac{ρ_{k}^{n−k−1}}{(k + 1)ρ_{k} − 2k} .  (18)

But we notice that

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

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

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

(since \binom{(k+1)ℓ−n}{ℓ−1} = 0 for ℓ = 0, because n ≠ 1). Thus Formula (18) is simplified to

∑_{ℓ=0}^{+∞} \binom{(k + 1)ℓ − n}{ℓ − 1}2^{−(k+1)ℓ} = 2^{−n+1} \frac{ρ_{k}^{n−k−1}}{(k + 1)ρ_{k} − 2k} .  (19)

Next, by subtracting side by side Equation (19) from Equation (17) and then multiplying by 2^{n−2}, we get

2^{n−2} ∑_{ℓ=0}^{+∞} (\binom{(k + 1)ℓ − n}{ℓ} − \binom{(k + 1)ℓ − n}{ℓ − 1}) 2^{−(k+1)ℓ} = \frac{1}{2} · \frac{ρ_{k}^{n} − ρ_{k}^{n−k−1}}{(k + 1)ρ_{k} − 2k}

= \frac{1}{2} · \frac{ρ_{k} − ρ_{k}^{−k}}{(k + 1)ρ_{k} − 2k} · ρ_{k}^{n−1}

= \frac{1}{2} · \frac{ρ_{k} − (2 − ρ_{k})}{(k + 1)ρ_{k} − 2k} · ρ_{k}^{n−1} (in view of (12))

= \frac{ρ_{k} − 1}{(k + 1)ρ_{k} − 2k} ρ_{k}^{n−1}

= As_{n}^{(k)} (according to (11)),

as required.

Observing Formula of Theorem 8, and because As_{n}^{(k)} is close to F_{n}^{(k)} for n large, a natural question arises: can replacing the series therein with its truncation at some positive integer N(n, k) (depending on n and k) yield the k-Fibonacci numbers? Exploring this direction, we have established the following result, which is essentially equivalent to that of Howard and Cooper [6, Theorem 2.4], but with some corrections (see below for the details).

Theorem 9. For all integers n, k ≥ 2, we have

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

To prepare for the proof of Theorem 9, let us provisionally define (for all integers n, k ≥ 2)

G_{n}^{(k)} := 2^{n−2} ∑_{0≤ℓ≤ \frac{n−1}{k+1}} (\binom{(k + 1)ℓ − n}{ℓ} − \binom{(k + 1)ℓ − n}{ℓ − 1}) 2^{−(k+1)ℓ}.

We first establish the following two propositions:

Proposition 10. Let n, k ≥ 2 be two integers. Then we have

\begin{aligned}G_{n}^{(k)} & = 2^{n−2}  for 2 ≤ n ≤ k + 1, \\ G_{k+2}^{(k)} & = 2^{k} − 1. \end{aligned}  (20)

Proof. For 2 ≤ n ≤ k + 1, the only integer ℓ in the range [0, \frac{n−1}{k+1}] is ℓ = 0. So the definition of G_{n}^{(k)} gives

G_{n}^{(k)} = 2^{n−2} (\binom{−n}{0} − \binom{−n}{−1}) = 2^{n−2}

(since \binom{−n}{0} = 1 and \binom{−n}{−1} = 0), as required.

Next, for n = k + 2, the only integers in the range [0, \frac{n−1}{k+1}] = [0, 1] are 0 and 1. So the definition of G_{k+2}^{(k)} gives

G_{k+2}^{(k)} = 2^{k} ((\underbrace{\binom{−k − 2}{0}}_{=1} − \underbrace{\binom{−k − 2}{−1}}_{=0}) + (\underbrace{\binom{−1}{1}}_{=−1} − \underbrace{\binom{−1}{0}}_{=1}) 2^{−k−1})

= 2^{k} (1 − 2^{−k})
= 2^{k} − 1,

as required. This completes the proof of the proposition.

Proposition 11. For all integers n, k ≥ 2, we have

G_{n+k+1}^{(k)} = 2G_{n+k}^{(k)} − G_{n}^{(k)}.

Proof. Let n, k ≥ 2 be two fixed integers. We have by definition

2G_{n+k}^{(k)} = 2^{n+k−1} ∑_{0≤ℓ≤ \frac{n+k−1}{k+1}} (\binom{(k + 1)ℓ − n − k}{ℓ} − \binom{(k + 1)ℓ − n − k}{ℓ − 1}) 2^{−(k+1)ℓ}. (21)

But summing on ℓ such that 0 ≤ ℓ ≤ \frac{n+k−1}{k+1} is equivalent to summing on ℓ such that 0 ≤ ℓ ≤ \frac{n+k}{k+1}, except perhaps in the case where \frac{n+k}{k+1} is an integer. Suppose that we are in the latter (i.e., \frac{n+k}{k+1} ∈ ℤ). Then since \frac{n+k}{k+1} ≥ \frac{k+2}{k+1} > 1, we have \frac{n+k}{k+1} ≥ 2. Thus for ℓ = \frac{n+k}{k+1} ≥ 2, we find that \binom{(k+1)ℓ−n−k}{ℓ} − \binom{(k+1)ℓ−n−k}{ℓ−1} = \binom{0}{ℓ} − \binom{0}{ℓ−1} = 0, implying that the sum for 0 ≤ ℓ ≤ \frac{n+k−1}{k+1} in (21) can be replaced by the sum for 0 ≤ ℓ ≤ \frac{n+k}{k+1} even in the case where \frac{n+k}{k+1} ∈ ℤ. So we have in all cases

2G_{n+k}^{(k)} = 2^{n+k−1} ∑_{0≤ℓ≤ \frac{n+k}{k+1}} (\binom{(k + 1)ℓ − n − k}{ℓ} − \binom{(k + 1)ℓ − n − k}{ℓ − 1}) 2^{−(k+1)ℓ}. (22)

Next, we have by definition

G_{n}^{(k)} = 2^{n−2} ∑_{0≤ℓ≤ \frac{n−1}{k+1}} (\binom{(k + 1)ℓ − n}{ℓ} − \binom{(k + 1)ℓ − n}{ℓ − 1}) 2^{−(k+1)ℓ}

= 2^{n−2} ∑_{1≤ℓ≤ \frac{n+k}{k+1}} (\binom{(k + 1)(ℓ − 1) − n}{ℓ − 1} − \binom{(k + 1)(ℓ − 1) − n}{ℓ − 2}) 2^{−(k+1)(ℓ−1)}

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

But since ℓ = 0 gives \binom{(k+1)ℓ−n−k−1}{ℓ−1} − \binom{(k+1)ℓ−n−k−1}{ℓ−2} = \binom{−n−k−1}{−1} − \binom{−n−k−1}{−2} = 0 (because −n − k − 1 ≤ −5), we have even

G_{n}^{(k)} = 2^{n+k−1} ∑_{0≤ℓ≤ \frac{n+k}{k+1}} (\binom{(k + 1)ℓ − n − k − 1}{ℓ − 1} − \binom{(k + 1)ℓ − n − k − 1}{ℓ − 2}) 2^{−(k+1)ℓ}. (23)

By subtracting (side to side) (23) from (22) and using the formulas

\binom{(k + 1)ℓ − n − k}{ℓ} − \binom{(k + 1)ℓ − n − k − 1}{ℓ − 1} = \binom{(k + 1)ℓ − n − k − 1}{ℓ}

and

\binom{(k + 1)ℓ − n − k}{ℓ − 1} − \binom{(k + 1)ℓ − n − k − 1}{ℓ − 2} = \binom{(k + 1)ℓ − n − k − 1}{ℓ − 1}

that result from (2), we get

2G_{n+k}^{(k)} − G_{n}^{(k)} = 2^{n+k−1} ∑_{0≤ℓ≤ \frac{n+k}{k+1}}(\binom{(k + 1)ℓ − n − k − 1}{ℓ} − \binom{(k + 1)ℓ − n − k − 1}{ℓ − 1}) 2^{−(k+1)ℓ}

= G_{n+k+1}^{(k)},

as required.

We are now ready to prove Theorem 9.

Proof of Theorem 9. Let k ≥ 2 be a fixed integer. We have to show that F_{n+k−2}^{(k)} = G_{n}^{(k)} for all integer n ≥ 2. Since the two sequences (F_{n+k−2}^{(k)})_{n≥2} and (G_{n}^{(k)})_{n≥2} satisfy the same linear recurrence relation of order (k + 1), which is

u_{n+k+1} = 2u_{n+k} − u_{n}

(according to (5) and to Proposition 11) then it suffices to show that F_{n+k−2}^{(k)} and G_{n}^{(k)} coincide at the first (k + 1) consecutive values of n; that is

F_{n+k−2}^{(k)} = G_{n}^{(k)}  for 2 ≤ n ≤ k + 2.  (24)

To confirm (24), we distinguish the following two cases:

• 1^{st} case: (if 2 ≤ n ≤ k + 1). In this case, we have k ≤ n + k − 2 ≤ 2k − 1, implying (according to (6)) that F_{n+k−2}^{(k)} = 2^{n−2}. Since we have also (according to (20)) G_{n}^{(k)} = 2^{n−2} then F_{n+k−2}^{(k)} = G_{n}^{(k)} for this case.

• 2^{nd} case: (If n = k + 2). In this case, we have F_{n+k−2}^{(k)} = F_{2k}^{(k)} = 2^{k} − 1 (according to (6)) and G_{n}^{(k)} = G_{k+2}^{(k)} = 2^{k} − 1 (according to (20)). Hence F_{n+k−2}^{(k)} = G_{n}^{(k)} also for this case. This confirms (24) and completes this proof.

By shifting the index n to (n − k + 2) in Theorem 9, we derive the following corollary:

Corollary 12. For all integers n and k such that n ≥ k ≥ 2, we have

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

By taking k = 2 in Corollary 12, we derive in particular an expression of the usual Fibonacci numbers as finite sums involving binomial coefficients and nonpositive powers of 8. This is given by the following corollary:

Corollary 13. For all integer n ≥ 2, we have

F_{n} = 2^{n−2} ∑_{0≤ℓ≤ \frac{n−1}{3}} (\binom{3ℓ − n}{ℓ} − \binom{3ℓ − n}{ℓ − 1}) 2^{−3ℓ}.  □

We end this paper by deriving a result from Corollary 12 that corrects that of Howard and Cooper [6, Theorem 2.4].

Corollary 14. For all integers n and k such that n ≥ k ≥ 2 and n ≠ 2k − 1, we have

F_{n}^{(k)} = 2^{n−k} + ∑_{1≤ℓ≤ \frac{n−k+1}{k+1}}(−1)^{ℓ} (\binom{n − (ℓ + 1)k + 2}{ℓ} − \binom{n − (ℓ + 1)k}{ℓ − 2}) 2^{n−(k+1)ℓ−k}.

Proof. Let n, k ∈ ℤ be fixed with n ≥ k ≥ 2 and n ≠ 2k − 1. According to Formula (2), we have

\binom{a}{ℓ} − \binom{a}{ℓ − 1} = \binom{a − 1}{ℓ} − \binom{a − 1}{ℓ − 2} (∀(a, ℓ) ∈ ℤ^{2} \ \{(0, 0), (0, 1)\}).

By applying this last formula for each of the couples (a, ℓ) = ((k + 1)ℓ − n + k − 2, ℓ) (0 ≤ ℓ ≤ \frac{n−k+1}{k+1}), which are all different from (0, 0) and (0, 1), we transform Formula of Corollary 12 to

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

Then, by applying Formula (3) for all the binomial coefficients occurring in the last formula, we conclude to

F_{n}^{(k)} = 2^{n−k} ∑_{0≤ℓ≤ \frac{n−k+1}{k+1}}(−1)^{ℓ} (\binom{n − (ℓ + 1)k + 2}{ℓ} − \binom{n − (ℓ + 1)k}{ℓ − 2}) 2^{−(k+1)ℓ}

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

as required.

Remark 15.

1. Howard and Cooper [6, Theorem 2.4] stated Formula of Corollary 14 with the erroneous condition of summation 1 ≤ ℓ ≤ \frac{n−1}{k+1}. This condition coincides with ours only for k = 2. Therefore, Corollary 14 corrects Theorem 2.4 of [6].

2. Applying (3) for all the binomial coefficients appearing in Formula of Corollary 12, we transform the later to

F_{n}^{(k)} = 2^{n−k} + ∑_{1≤ℓ≤ \frac{n−k+1}{k+1}}(−1)^{ℓ} (\binom{n − (ℓ + 1)k + 1}{ℓ} + \binom{n − (ℓ + 1)k}{ℓ − 1}) 2^{n−(k+1)ℓ−k}

(valid for n ≥ k ≥ 2). Note that the last formula and the formula of Corollary 14 have the advantage that the binomial coefficients which appear in them are ordinary (i.e., have nonnegative entries). Additionally, the two formulas in question are equivalent (we pass from the one to the other via Formula (2)).

4 Acknowledgment

The author would like to thank the anonymous referee for many helpful comments.

References

[1] H. Bürmann, Essai de calcul fonctionnaire aux constantes ad-libitum, Mem. Inst. Nat. Sci Arts Sci. Math. Phys. 2 (1799), 13–17.

[2] L. Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, Springer, 2012.

[3] Gregory P. B. Dresden, A simplified Binet formula for k-generalized Fibonacci numbers, J. Integer Sequences 17 (2014), Article 14.4.7.

[4] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics. A Foundation for Computer Science, Addison-Wesley, 1989.

[5] K. Hare, H. Prodinger, and J. Shallit, Three series for the generalized golden mean, Fibonacci Quart. 52 (2014), 307–313.

[6] F. T. Howard and Curtis Cooper, Some Identities for r-Fibonacci Numbers, Fibonacci Quart. 49 (2011), 231–243.

[7] J.-L. Lagrange, Nouvelle méthode pour résoudre les équations littérales par le moyen des séries, Histoire de l’Académie Royale des Sciences et Belles-Lettres de Berlin (1770), 251–326.

[8] E. P. Miles, Generalized Fibonacci numbers and associated matrices, Amer. Math. Monthly 67 (1960), 745–752.

[9] M. D. Miller, On generalized Fibonacci numbers, Amer. Math. Monthly 78 (1971), 1108–1109.

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

    at https://oeis.org.

[11] W. R. Spickerman and R. N. Joyner, Binet’s formula for the recursive sequence of order k, Fibonacci Quart. 22 (1984), 327–331.

[12] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

[13] E. Surya and L. Warnke, Lagrange inversion formula by induction, to appear in Amer.

    Math. Monthly. Available at https://arxiv.org/abs/2305.17576v1.

[14] D. A. Wolfram, Solving generalized Fibonacci recurrences, Fibonacci Quart. 36 (1998), 129–145.

2020 Mathematics Subject Classification: Primary 11B39; Secondary 11B83, 11B65, 11B37. Keywords: Fibonacci number, k-Fibonacci number, linear recurrent sequence, binomial coefficient, the Lagrange inversion formula.

(Concerned with sequence \underline{A000045}.)

Received September 28 2023; revised versions received September 30 2023; December 3 2023; December 21 2023; January 3 2024. Published in Journal of Integer Sequences, January 3 2024.

Return to Journal of Integer Sequences home page.