A REPRESENTATION AND SOME PROPERTIES FOR k–FIBONACCI SEQUENCES

Gwang–Yeon Lee, Jin–Soo Kim and Sang–Gu Lee*

Abstract. The k–Fibonacci sequence {g_{n}^{(k)}} is defined as:

g_{1}^{(k)} = … = g_{k−2}^{(k)} = 0, g_{k−1}^{(k)} = g_{k}^{(k)} = 1

and for n > k ≥ 2,

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

In this paper, we give a combinatorial representation of g_{n}^{(k)} and give some properties for k–Fibonacci sequence.

1. Introduction. The well–known Fibonacci sequence {F_{n}} is defined as:

F_{1} = F_{2} = 1 and, for n > 2, F_{n} = F_{n−1} + F_{n−2}.

We call F_{n} the nth Fibonacci number. The Fibonacci sequence is

(F_{0} := 0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ….

Now, we consider the generalization of the Fibonacci sequence, which is called the k–Fibonacci sequence for the positive integer k ≥ 2. The k–Fibonacci sequence {g_{n}^{(k)}} is defined as:

g_{1}^{(k)} = ⋯ = g_{k−2}^{(k)} = 0, g_{k−1}^{(k)} = g_{k}^{(k)} = 1

and for n > k ≥ 2,

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

We call g_{n}^{(k)} the nth k–Fibonacci number. For example, if k = 2, then {g_{n}^{(2)}} is the Fibonacci sequence, {F_{n}}, and if k = 4, then g_{1}^{(4)} = g_{2}^{(4)} = 0, g_{3}^{(4)} = g_{4}^{(4)} = 1, and then the 4-Fibonacci sequence is

0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, ….

Let I_{k−1} be the identity matrix of order k − 1 and let E be an 1 × (k − 1) matrix whose entries are ones. For any k ≥ 2, the fundamental recurrence relation

g_{n}^{(k)} = g_{n−1}^{(k)} + g_{n−2}^{(k)} + ⋯ + g_{n−k}^{(k)}

can be defined by the vector recurrence relation

[ g_{n+1}^{(k)} ; g_{n+2}^{(k)} ; ⋮ ; g_{n+k}^{(k)} ] = Q_{k} [ g_{n}^{(k)} ; g_{n+1}^{(k)} ; ⋮ ; g_{n+k−1}^{(k)} ]  (1.1)

where

Q_{k} = [ \begin{matrix}0 & I_{k−1} \\ 1 & E \end{matrix} ]_{k×k} .  (1.2)

The matrix Q_{k} is said to be the k–Fibonacci matrix. By applying (1.1), we have

[ g_{n+1}^{(k)} ; g_{n+2}^{(k)} ; ⋮ ; g_{n+k}^{(k)} ] = Q_{k}^{n} [ g_{1}^{(k)} ; g_{2}^{(k)} ; ⋮ ; g_{k}^{(k)} ] .

Let {g_{n}^{(k)}} be a k–Fibonacci sequence, and let

G_{k} = (g_{1}, g_{2}, g_{3}, …), g_{i} = g_{i+k−2}^{(k)}, i = 1, 2, …,

and if i ≤ 0, then g_{i} = 0.

For example, if k = 2, then G_{2} = (1, 1, 2, 3, 5, 8, 13, …). And if k = 4, then G_{4} = (1, 1, 2, 4, 8, 15, 29, 56, 108, …).

In [3], the author considered the completeness on {g_{n}^{(k)}} and gave a representation for the recurrence relation g_{n}^{(k)}. In [4], the authors found a relationship between the k–Fibonacci number g_{n}^{(k)} and the number of 1-factors of a bipartite graph, and in [5], the authors considered the eigenvalues of k–Fibonacci matrix Q_{k} and gave some interesting examples in combinatorics and probability with respect to the k–Fibonacci sequences.

In this paper, we give a combinatorial representation of g_{n}^{(k)} and introduce some properties for k–Fibonacci sequences.

2. Combinatorial representation of g_{n}. In this section, we give a representation for the nth k–Fibonacci number by using the generating function G_{k}(x).

We can easily find the characteristic polynomial, x^{k} − x^{k−1} − ⋯ − x − 1, of the k–Fibonacci matrix Q_{k}. It follows that all of the eigenvalues of Q_{k} satisfy

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

And we can find the following fact in [5]:

x^{n} = g_{n−k+2}x^{k−1} + (g_{n−k+1} + g_{n−k} + ⋯ + g_{n−2k+3})x^{k−2}
+ (g_{n−k+1} + g_{n−k} + ⋯ + g_{n−2k+4})x^{k−3}  (2.1)
+ ⋯ + (g_{n−k+1} + g_{n−k})x + g_{n−k+1}.

Let

G_{k}(x) = g_{1} + g_{2}x + g_{3}x^{2} + ⋯ + g_{n+1}x^{n} + · · · .

Then

G_{k}(x) − xG_{k}(x) − x^{2}G_{k}(x) − ⋯ − x^{k}G_{k}(x) = (1 − x − x^{2} − ⋯ − x^{k})G_{k}(x).

Using equation (2.1), we have

(1 − x − x^{2} − ⋯ − x^{k})G_{k}(x) = g_{1} = 1.

Thus,

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

for 0 ≤ x + x^{2} + ⋯ + x^{k} < 1.

Let f_{k}(x) = x + x^{2} + ⋯ + x^{k}. Then 0 ≤ f_{k}(x) < 1 and we have the following lemma.

\underline{Lemma 2.1}. For positive integers p and n, the coefficient of x^{n} in (f_{k}(x))^{p} is

∑_{l=0}^{p}(−1)^{l}\binom{p}{l}\binom{n − kl − 1}{n − kl − p}, \frac{n}{k} ≤ p ≤ n.

\underline{Proof}.

(f_{k}(x))^{p} = (x + x^{2} + ⋯ + x^{k})^{p}

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

= x^{p} (\frac{1 − x^{k}}{1 − x} )^{p}

= x^{p} ((1 − x^{k}) (\frac{1}{1 − x}))^{p}

= x^{p} ((∑_{l=0}^{p} \binom{p}{l}(−1)^{l}x^{kl}) (∑_{i=0}^{∞} \binom{p + i − 1}{i}x^{i})) .

In the above equation, we only consider the coefficient of x^{n}. Since the first term on the right is x^{p}, kl + i = n − p, that is, i = n − kl − p. If l = q for any q = 0, 1, …, p, then the second term on the right is

((−1)^{q}\binom{p}{q}\binom{n − kq − 1}{n − kq − p}) x^{n−p}.

So, the coefficient of x^{n} is

∑_{l=0}^{p}(−1)^{l}\binom{p}{l}\binom{n − kl − 1}{n − kl − p}, \frac{n}{k} ≤ p ≤ n.

The proof is completed.

Now we have a combinatorial representation for g_{n}. \underline{Theorem 2.2}. For positive integers p and n,

g_{n+1} = ∑_{\frac{n}{k} ≤p≤n} ∑_{l=0}^{p}(−1)^{l}\binom{p}{l}\binom{n − kl − 1}{n − kl − p}.  (2.2)

\underline{Proof}. Since

\begin{aligned}G_{k}(x) & = g_{1} + g_{2}x + g_{3}x^{2} + ⋯ + g_{n+1}x^{n} + ⋯ \\ & = \frac{1}{1 − x − x^{2} − ⋯ − x^{k}} , \end{aligned}

the coefficient of x^{n} is the n + 1st Fibonacci number, g_{n+1} , in G_{k}. And,

G_{k}(x) = \frac{1}{1 − x − x^{2} − ⋯ − x^{k}}

= \frac{1}{1 − f_{k}(x)}

= 1 + f_{k}(x) + (f_{k}(x))^{2} + ⋯ + (f_{k}(x))^{n} + ⋯  (2.3)

= 1 + f_{k}(x) + x^{2} ∑_{l=0}^{2} \binom{2}{l}(−1)^{l}x^{kl} ∑_{i=0}^{∞} \binom{i + 1}{i}x^{i}+

⋯ + x^{n} ∑_{l=0}^{n} \binom{n}{l}(−1)^{l}x^{kl} ∑_{i=0}^{∞} \binom{n + i − 1}{i}x^{i} + · · · .

Since we consider the coefficient of x^{n}, we only need the first n + 1 terms on the right. The (p + 1)st term in (2.3) is

x^{p} ∑_{l=0}^{p} \binom{p}{l}(−1)^{l}x^{kl} ∑_{i=0}^{∞} \binom{p + i − 1}{i}x^{i}.

So, kl + i = n − p, and \frac{n}{k} ≤ p ≤ n. Hence, by Lemma 2.1, we have (2.2).

If k = 2, then
G_{2} = (1, 1, 2, 3, 5, 8, 13, 21, …)

is the Fibonacci sequence {F_{n}}. Since the generating function for {F_{n}} is G_{2}(x) = \frac{1}{1−x−x^{2}} , and hence,

\begin{aligned}G_{2}(x) & = \frac{1}{1 − x(1 + x)} \\ & = 1 + x(1 + x) + x^{2}(1 + x)^{2} + ⋯ + x^{n}(1 + x)^{n} + · · · . \end{aligned}

If the first n + 1 terms on the right are examined in reverse order, it is seen that the coefficient of x^{n} in G_{2}(x) is

1 + \binom{n − 1}{1} + \binom{n − 2}{2} + ⋯  (2.4)

as asserted. So, we have the following corollary.

\underline{Corollary 2.3}. Let F_{n+1} be the (n + 1)st Fibonacci number. Then

\begin{aligned}F_{n+1} & = ∑_{i=0} \binom{n − i}{i} \\ & = ∑_{\frac{n}{2} ≤p≤n} ∑_{l=0}^{p}(−1)^{l}\binom{p}{l}\binom{n − 2l − 1}{n − 2l − p}. \end{aligned}

\underline{Proof}. By (2.2) and (2.4), the proof is completed.

3. Properties of k–Fibonacci Sequences. In this section, we give some properties for k–Fibonacci sequences. First, we have the following theorem by using vector recurrence relation (1.1).

\underline{Theorem 3.1 [3]}. For positive integers n and m,

g_{n+m} = g_{n}g_{m−(k−1)} + (g_{n} + g_{n−1})g_{m−(k−2)}+
(g_{n} + g_{n−1} + g_{n−2})g_{m−(k−3)} + ⋯
+ (g_{n} + g_{n−1} + g_{n−2} + ⋯ + g_{n−(k−2)})g_{m−1} + g_{n+1}g_{m}.

\underline{Proof}. For G_{k}, k ≥ 2, since g_{1} = g_{2} = 1, we can replace the matrix Q_{k} in (2.2) with

Q_{k} = [ \begin{matrix}0 & g_{1} & 0 & ⋯ & 0 \\ 0 & 0 & g_{1} & ⋯ & 0 \\ ⋮ & ⋮ & & ... & ⋮ \\ 0 & 0 & & & g_{1} \\ g_{1} & g_{1} & ⋯ & g_{1} & g_{2} \end{matrix} ] .

Then

Q_{k}^{n} = [ \begin{matrix}g_{n−(k−1)} & g_{1,2}^{†} & g_{1,3}^{†} & ⋯ & g_{1,k−1}^{†} & g_{n−(k−2)} \\ g_{n−(k−2)} & g_{2,2}^{†} & g_{2,3}^{†} & ⋯ & g_{2,k−1}^{†} & g_{n−(k−3)} \\ ⋮ & ⋮ & ⋮ & ⋯ & ⋮ & ⋮ \\ g_{n−1} & g_{k−1,2}^{†} & g_{k−1,3}^{†} & ⋯ & g_{k−1,k−1}^{†} & g_{n} \\ g_{n} & g_{k,2}^{†} & g_{k,3}^{†} & ⋯ & g_{k,k−1}^{†} & g_{n+1} \end{matrix} ] ,

where

g_{i,2}^{†} = g_{n−(k−i)} + g_{n−(k−(i−1))},
g_{i,3}^{†} = g_{n−(k−i)} + g_{n−(k−(i−1))} + g_{n−(k−(i−2))},

⋮
g_{i,k−1}^{†} = g_{n−(k−i)} + g_{n−(k−(i−1))} + g_{n−(k−(i−2))} + ⋯ + g_{n−(k−(i−(k−2)))}.

Since Q_{k}^{n}Q_{k}^{m} = Q_{k}^{n+m}, g_{n+m} = (Q_{k}^{n+m})_{k,1}.

Therefore,

g_{n+m} = g_{n}g_{m−(k−1)} + g_{k,2}^{†}g_{m−(k−2)} + g_{k,3}^{†}g_{m−(k−3)} + ⋯
+ g_{k,k−1}^{†}g_{m−1} + g_{n+1}g_{m}

= g_{n}g_{m−(k−1)} + (g_{n} + g_{n−1})g_{m−(k−2)} + (g_{n} + g_{n−1} + g_{n−2})g_{m−(k−3)} + ⋯

+ (g_{n} + g_{n−1} + g_{n−2} + ⋯ + g_{n−(k−2)})g_{m−1} + g_{n+1}g_{m}.

We also have another representation of the nth k–Fibonacci number for positive intergers n and m.

\underline{Corollary 3.2}. For positive integers n and m,

g_{n+m} = g_{n−1}g_{m−(k−2)} + (g_{n−1} + g_{n−2})g_{m−(k−3)}+
(g_{n−1} + g_{n−2} + g_{n−3})g_{m−(k−4)} + ⋯
+ (g_{n−1} + g_{n−2} + g_{n−3} + ⋯ + g_{n−(k−1)})g_{m} + g_{n}g_{m+1}.

\underline{Proof}. Since g_{n+m} = (Q_{k}^{n+m})_{k,1} = (Q_{k}^{n+m})_{k−1,k}, the proof is completed.

For example, for n > k,

g_{2n} = g_{2n−1} + g_{2n−2} + ⋯ + g_{2n−k}
= g_{n+n}
= g_{n−1}g_{n−(k−2)} + (g_{n−1} + g_{n−2})g_{n−(k−3)} + ⋯
+ (g_{n−1} + g_{n−2} + ⋯ + g_{n−(k−1)})g_{n} + g_{n}g_{n+1}.

So, we can get g_{2n} by using g_{n+1}, g_{n}, …, g_{n−k+2}.

The above fact raises a question [1, 2]. What is the relationship between g_{n} and g_{nt} for a positive integer t. In particular, is there a t such that g_{n} is a factor of g_{nt}? In the Fibonacci numbers, F_{n}|F_{tn} for all t = 1, 2, 3, …. However, this is not true, in general, for k–Fibonacci numbers, k ≥ 3.

\underline{Lemma 3.3}. For any positive integer n, the k–Fibonacci numbers g_{nk+n−k} and g_{nk+n−k+1} are odd numbers.

\underline{Proof}. If n = 1, then g_{1} = g_{2} = 1, i.e., g_{1} and g_{2} are odd numbers. By induction on n, we may assume true for n, and consider n + 1.

First,

g_{(n+1)k+(n+1)−k} = g_{nk+n+1}
= g_{nk+n} + g_{nk+n−1} + ⋯ + g_{nk+n−k+2} + g_{nk+n−k+1}
= g_{nk+n−1} + g_{nk+n−2} + ⋯ + g_{nk+n−k+1} + g_{nk+n−k}
+ (g_{nk+n−1} + g_{nk+n−2} + ⋯ + g_{nk+n−k+2} + g_{nk+n−k+1})
= 2(g_{nk+n−1} + g_{nk+n−2} + ⋯ + g_{nk+n−k+1}) + g_{nk+n−k}.

Then g_{(n+1)k+(n+1)−k} is an odd number since g_{nk+n−k} is an odd number by hypothesis. Similarly, g_{(n+1)k+(n+1)−k+1} is also an odd number.

Therefore, for any positive integer n, the k–Fibonacci numbers g_{nk+n−k} and g_{nk+n−k+1} are odd numbers.

Since g_{n}^{(k)} = g_{n−k+2}, our question can be replaced from “Is there any t such that g_{n}^{(k)}|g_{nt}^{(k)} for some n?” to “Is there any t such that g_{n−k+2}|g_{nt−k+2} for some n?”

\underline{Theorem 3.4}. For k ≥ 3, there exists t such that g_{n−k+2} |̸g_{nt−k+2} for some n.

\underline{Proof}. If k = 3, then
G_{3} = (1, 1, 2, 4, 7, 13, 24, 44, 81, 147, …).

Here, g_{4} = 4, g_{9} = 81 and hence, g_{4} |̸g_{9}. In this case, n = 5 and k = 3.

Now, suppose that k ≥ 4. Then, for any positive integer n, the g_{nk+n−k} and g_{nk+n−k+1} are odd numbers. Let n = k + 2, t = k and let m = n + 1. Then

mt − k + 2 = (n + 1)k − k + 2 = (n + \frac{n − 2}{k}) k − k + 2 = nk + n − k.

So, g_{mt−k+2} is an odd number. Since n = k + 2, k ≥ 4 and G_{k} = (1, 1, 2, 4, 8, …),

g_{m−k+2} = g_{n+1−k+2} = g_{5}.

Since k ≥ 4, in any cases, g_{5} = 8. Since g_{m−k+2} is an even number and g_{mk−k+2} is an odd number, there exists t such that g_{n−k+2} |̸g_{nt−k+2} for some n.

Now we have another question for any positive integers m and n. The question is “how many k–Fibonacci numbers are there between n^{m} and n^{m+1}?”

\underline{Lemma 3.5}. For positive integers n and r,
ng_{r} ≤ g_{r+n}.  (2.3)

\underline{Proof}. If n = 1, then g_{r} ≤ g_{r+1}. By induction on n, we may assume true for n, and consider n + 1. That is,

ng_{r} ≤ g_{r+n} ⇒ ng_{r} + g_{r} ≤ g_{r+n} + g_{r}
⇒ (n + 1)g_{r} ≤ g_{r+n−1} + g_{r+n−2} + ⋯ + g_{r+n−k} + g_{r}

= g_{r+n} + (g_{r+n−1} + ⋯ + g_{r+n−(k−1)} + g_{r+n−k} + g_{r}) − g_{r+n}

= g_{r+n+1} + g_{r+n−k} + g_{r} − g_{r+n}.

Since g_{r+n} = g_{r+n−1} +g_{r+n−2} +⋯+g_{r+n−k} and n ≥ 1, g_{r+n−k} +g_{r} ≤ g_{r+n}. Thus, (n + 1)g_{r} ≤ g_{r+n+1}.

Therefore, ng_{r} ≤ g_{r+n} for any positive integers n, r.

\underline{Theorem 3.6}. Let m and n be any two positive integers. Then there are no more than n k–Fibonacci numbers between the consecutive powers n^{m} and n^{m+1}.

\underline{Proof}. Suppose that the interval between some n^{m} and n^{m+1} were to contain at least n + 1 k–Fibonacci numbers:

n^{m} < g_{r+1}, g_{r+2}, …, g_{r+n+1}, … < n^{m+1}.

Since n^{m} < g_{r+1}, n · n^{m} < ng_{r+1}. So, by (2.3),

n^{m+1} < ng_{r+1} ≤ g_{r+n+1}.

Consequently, n^{m+1} < g_{r+n+1}, a contradiction.

One of the most well–known properties of the Fibonacci sequence is the formula for the sum S_{n}^{(2)} of the first n terms. A glance at the first few cases quickly leads to the conjecture

S_{n}^{(2)} = F_{1} + F_{2} + ⋯ + F_{n} = F_{n+2} − 1,

which is immediately confirmed by mathematical induction. In case k ≥ 3, we can easily verify that

S_{n}^{(k)} = \frac{1}{k − 1} (g_{n+2}^{(k)} − g_{n+(k−2)}^{(k)} − 2g_{n+(k−3)}^{(k)} − ⋯ − (k − 2)g_{n+1}^{(k)} − 1) .

*This paper was supported by Faculty Research Fund, Sungkyunkwan Univ., 1999.

\underline{References}

1. W. Y. C. Chen and J. D. Louck, “The Combinatorial Power of the Companion Matrix,” Linear Algebra Appl. 232 (1996), 261–278.

2. R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, New York, 1985.

3. G.–Y. Lee, “A Completeness on Generalized Fibonacci Sequences,” Bull. Korean Math. Soc. 32 (1995), 239–249.

4. G.–Y. Lee and S.–G. Lee, “A Note of Generalized Fibonacci Numbers,” The Fibonacci Quarterly, 33 (1995), 273–278.

5. G.–Y. Lee, S.–G. Lee and H.–G. Shin, “On the k–generalized Fibonacci Matrix Q_{k},” Linear Algebra Appl., 251 (1997), 73–88.

Gwang–Yeon Lee Department of Mathematics HanSeo University Seosan 356–820, Korea email: gylee@gaya.hanseo.ac.kr

Jin–Soo Kim Department of Mathematics Sungkyunkwan University Suwon 440–746, Korea email: lion@math.skku.ac.kr

Sang–Gu Lee Department of Mathematics Sungkyunkwan University Suwon 440-746, Korea email: sglee@yurim.skku.ac.kr