On Linear Recurrence Equations Arising from Compositions of Positive Integers

Milan Janjić Department of Mathematics and Informatics University of Banja Luka Banja Luka, 78000 Republic of Srpska, Bosnia and Herzegovina

                    agnus@blic.net

Abstract

For an arithmetic function f_{0}, we define a new arithmetic function f_{1}, generalizing the linear recurrence for the numbers of compositions of positive integers. Using f_{1} in the same way, we then define f_{2}, and so on.

We establish some patterns related to the sequence f_{1}, f_{2}, . . .. Our investigations depend on the following result: if f_{0} satisfies a linear recurrence equation of order k, then each function f_{m} will also satisfy a linear recurrence equation of the same order.

In several results, we derive a recurrence equation for f_{m}(n), in terms of m and n. For each result, we give a combinatorial meaning for f_{m}(n) in terms of the number of restricted words over a finite alphabet.

We also find new combinatorial interpretations of the Fibonacci polynomials, as well as the Chebyshev polynomials of the second kind.

1 Introduction

Researchers usually investigate compositions of positive integers through their generating functions, connecting them to the so-called invert transforms.

In this paper, we take a different approach. Investigating some generalizations of the linear recurrence equations for the numbers of compositions, we proceed to show that certain linear recurrences may be considered as recurrences for the numbers of some kinds of compositions.

In conclusion, we provide a number of results, which illustrate some consequences of our findings. We are interested in two particular problems: obtaining a recurrence equation for f_{m}(n) when f_{0} is given, and investigating relationships of the sequence f_{1}, f_{2}, … with the number of restricted words over a finite alphabet.

In our interpretation of f_{m}(n) in terms of restricted words, the number of letters in the alphabet is determined by the parameter m, while the length of a word is determined by the parameter n.

In particular, if f_{0} takes values in {0, 1}, then f_{1}(n) counts the number of some compositions of n, so that f_{1} always produces a relationship between the compositions and the binary words.

In fact, our sequence of functions might be understood as a way to transfer some properties from the binary words to words over a finite alphabet.

We derive connections our sequence of our sequence with the Fibonacci polynomials and the Chebyshev polynomials of the second kind. Fibonacci numbers are generalized in several ways.

We finish the paper by giving the combinatorial meaning for a class of sequences when f_{0} satisfies a particular linear recurrence equation of second order with constant coefficients.

We start with the definition of our sequence.

Definition 1. We define a pair (f_{0}, f_{1}) of arithmetic functions as follows: Let f_{0} be an arbitrary arithmetic function. A function f_{1} is recursively defined through the convolution

f_{1}(n) = ∑_{i=1}^{n} f_{0}(i)f_{1}(n − i), (n ≥ 1),  (1)

where f_{1}(0) = 1.

Inductively, for each m > 0, we define the pair (f_{m−1}, f_{m}).

Corollary 2. For each m ≥ 1, we have

f_{m}(1) = f_{0}(1), f_{m}(2) = mf_{0}(1)^{2} + f_{0}(2).

Proof. We use induction with respect to m. From Equation (1), we conclude that the claim holds for m = 1. Suppose that the claim is true for m. Then f_{m+1}(1) = f_{m}(1), and so f_{m+1}(1) = f_{0}(1). In the same way, we obtain f_{m+1}(2) = f_{m}(1)^{2} + f_{m}(2). Applying the induction hypothesis gives

f_{m+1}(2) = f_{0}(1)^{2} + mf_{0}(1)^{2} + f_{0}(2) = (m + 1)f_{0}(1)^{2} + f_{0}(2).

Remark 3. If f_{0}(i) = 1, (i ≥ 1) then Equation 1 becomes the recurrence for the numbers of compositions of positive integers.

Remark 4. Note that f_{m} is a particular case of 1-determinants, defined in Janjić [2].

Using the notion of the invert transform, we easily find the generating function for the sequence f_{1}(1), f_{1}(2), . . ..

Proposition 5. The sequence {f_{1}(n)}_{n=1}^{∞} is the invert transform of the sequence {f_{0}(n)}_{n=1}^{∞}.

Proof. It is easy to see that Equation (1) is equivalent to

[1 + ∑_{i=1}^{∞} f_{1}(i)x^{i}] · [1 − ∑_{i=1}^{∞} f_{0}(i)x^{i}] = 1.

Hence, the generating function of the sequence f_{1}(1), f_{1}(2), … is

\frac{1}{1 − ∑_{i=1}^{∞} f_{0}(i)x^{i}} .

In general, an arithmetic function maps the set of positive (or nonnegative) integers into the set of complex numbers. The results of the next section are valid for such functions.

2 A result on linear recurrences

We proceed to prove that, if f_{0} satisfies a linear recurrence equation of order k, then f_{1} also satisfies a linear recurrence of the same order. To stress the dependence of f_{0} and f_{1} on k, we write f_{i}(n; k) instead of f_{i}(n) for i = 1, 2.

Theorem 6. Let f_{0} be an arithmetic function, and let k be a positive integer. If there exist constant numbers (complex) a_{0}(1), a_{0}(2), …, a_{0}(k) such that

f_{0}(n + k; k) = ∑_{i=1}^{k} a_{0}(i)f_{0}(n + k − i; k), (n ≥ 1),  (2)

where f_{0}(1; k), f_{0}(2; k), …, f_{0}(k; k) are arbitrary numbers (complex), then we have

f_{1}(i; k) = ∑_{j=1}^{i} f_{0}(j; k)f_{1}(i − j; k), (i = 1, 2, …, k), and  (3)

f_{1}(n + k; k) = ∑_{i=1}^{k} a_{1}(i)f_{1}(n + k − i; k), (n ≥ 1),  (4)

where

a_{1}(1) = a_{0}(1) + f_{0}(1; k),

a_{1}(i) = a_{0}(i) + f_{0}(i; k) − ∑_{j=1}^{i−1} a_{0}(j)f_{0}(i − j; k), (2 ≤ i ≤ k). (5)

Proof. We first consider the case k = 1. If f_{0}(n + 1; 1) = a_{0}(1)f_{0}(n; 1), (n ≥ 1), then

f_{1}(n + 1; 1) = ∑_{i=1}^{n+1} f_{0}(i; 1)f_{1}(n + 1 − i; 1) = f_{0}(1; 1)f_{1}(n; 1) + ∑_{i=2}^{n+1} f_{0}(i; 1)f_{1}(n + 1 − i; 1),

which implies f_{1}(n + 1; 1) = [f_{0}(1; 1) + a_{0}(1)]f_{1}(n; 1). Hence, Theorem 6 is true for k = 1.

Assume that k > 1. For 1 ≤ i ≤ k, we have

f_{1}(n + k − i; k) = ∑_{j=1}^{n+k−i} f_{0}(j; k)f_{1}(n + k − i − j; k).

We denote f_{1}(n + k − i; k) = X_{i} + Y_{i}, (i = 1, …, n), where

X_{i} = ∑_{j=1}^{k−i} f_{0}(j; k)f_{1}(n + k − i − j; k), Y_{i} = ∑_{j=k−i+1}^{n+k−i} f_{0}(j; k)f_{1}(n + k − i − j; k), (6)

with X_{k} = 0. It follows that

∑_{i=1}^{k} a_{0}(i)X_{i} = ∑_{i=2}^{k} [∑_{j=1}^{i−1} a_{0}(j)f_{0}(i − j; k)] f_{1}(n + k − i; k).  (7)

Also, after some calculations, we obtain

∑_{i=1}^{k} a_{0}(i)Y_{i} = f_{1}(n + k; k) − ∑_{i=1}^{k} f_{0}(i; k)f_{1}(n + k − i; k).  (8)

From equations (7) and (8), we obtain

∑_{i=1}^{k} a_{i}f_{1}(n + k − i; k) = ∑_{i=1}^{k} a_{i}(X_{i} + Y_{i}) =

∑_{i=2}^{k} [∑_{j=1}^{i−1} a_{0}(j)f_{0}(i − j; k)] f_{1}(n + k − i; k) + f_{1}(n + k; k) − ∑_{j=1}^{k} f_{0}(j; k)f_{1}(n + k − j; k).

We finally have

f_{1}(n + k; k) = ∑_{i=1}^{k}[a_{i} + f_{0}(i; k)]f_{1}(n + k − i; k) − ∑_{i=2}^{k} [∑_{j=1}^{i−1} a_{i}f_{0}(i − j, k)] f_{1}(n + k − i; k),

which is Equation (4), under the conditions (3). Remark 7. In the conditions of Theorem 6, we may always find an explicit formula for f_{1}(n; k), when k = 1, 2, 3, 4 by solving the characteristic equations.

The simplest case of Theorem 6 is

Corollary 8. If f_{0}(n + 1) = af_{0}(n), (n ≥ 1), for some a, then for m ≥ 1 we have

f_{m}(n + 1) = [mf_{0}(1) + a]f_{m}(n), (n ≥ 1).

The explicit formula for f_{m} is

f_{m}(n) = f_{0}(1)[mf_{0}(1) + a]^{n−1}, (n ≥ 1).

Proof. For m = 1, according to Theorem 6, we have a_{1}(1) = a + f_{0}(1), and the claim is true for m = 1. The rest follows by induction.

We finished this section by stating the recurrence equation for f_{m}, (m ≥ 1), assuming that f_{0} satisfies a linear recurrence of order 2.

Corollary 9. If f_{0}(1), f_{0}(2) are arbitrary, and

f_{0}(n + 2) = a_{0}(1)f_{0}(n + 1) + a_{0}(2)f_{0}(n),

then

f_{m}(1) = f_{0}(1), f_{m}(2) = mf_{0}(1)^{2} + f_{0}(2),  (9)

and

f_{m}(n + 2) = a_{m}(1)f_{m}(n + 1) + a_{m}(2)f_{m}(n),  (10)

where a_{m}(1) = a_{0}(1) + mf_{0}(1), a_{m}(2) = a_{0}(2) − ma_{0}(1)f_{0}(1) + mf_{0}(2).

Proof. This is a particular case of Theorem 6.

We stress that in all that follows the values of arithmetical functions f_{m}, (m ≥ 0) will be nonnegative integers.

3 Compositions and words

The function f_{1} generalizes the notions of the numbers of compositions of positive integers for several kinds of compositions. We state some of them.

Corollary 10. 1. If f_{0}(i) is either 1 or 0 and Q = {i : f_{0}(i) = 1}, then f_{1}(n) equals the number of compositions of n, the parts of which belong to Q.

2. If f_{0}(i) = 1 for all i, then f_{1}(n)(= 2^{n−1}) equals the number of all compositions of n.

3. If f_{0}(i) ≥ 0 for all i, then f_{1}(n) equals the number of the colored compositions of n, in which part i may appear in f_{0}(i) different colors.

Proof. All claims are easy to prove.

Remark 11. Note that Claim 3 above is, in fact, the combinatorial interpretation of the invert transform in Bernstein and Sloane [1].

The Catalan numbers C_{i}, (i = 0, 1, …) may also be considered as a kind of colored compositions.

Proposition 12. If f_{0}(i) = C_{i−1} for all i ≥ 1, then f_{1}(n) = C_{n}.

Proof. The claim follows from Segner’s formula for the Catalan numbers; see Koshy [5, Formula (5.6), p. 117].

Now we show that the function f_{1} also counts the number of the k-matrix compositions, considered by Munarini at al. [6].

A k-matrix composition of n is a matrix with k rows, in which the entries are nonnegative integers, there are no columns consisting of zeros only, and the sum of all entries equals n. Let mc(n; k) denote the number of such compositions. We have

Proposition 13. If f_{0}(i) = \binom{k+i−1}{k−1}, (i = 1, 2, …), then mc(n; k) = f_{1}(n).

Proof. For given i, (1 ≤ i ≤ k), the equation x_{1} + x_{2} + ⋯ + x_{k} = i has \binom{k+i−1}{k−1} nonnegative solutions. This means that there are \binom{k+i−1}{k−1}·mc(n−i; k) k-matrix compositions of n, ending with a column having the sum of all elements equal i. Taking mc(0; k) = 1, we obtain

mc(n; k) = ∑_{i=1}^{n} \binom{i + k − 1}{k − 1} mc(n − i; k).

Comparing this equation with Equation (1), we conclude that mc(n; k) = f_{1}(n).

Remark 14. The sequences in Sloane [7], the members of which count k-compositions are: \underline{A003480}, \underline{A145839}, \underline{A145840}, \underline{A145841}, \underline{A161434}.

We next note that, for a suitably chosen f_{0}, the function f_{1} counts the number of particular partitions of positive integers. Namely, for the set Q = {q_{1}, q_{2}, …, q_{n}} of positive integers, we let p(Q, n) denote the number of partitions of n, the parts of which belong to Q.

Janjić and Petković, in [3], consider the following function:

a_{i} = ∑_{j=0}^{i}(−1)^{i−j}\binom{n + k + 1}{i − j}\binom{j, n}{k, Q}, (i ≥ 0),

where numbers \binom{j,n}{k,Q} are defined in the following way:

1. k = ∑_{t=1}^{n}(q_{t} − 1).

2. Consider a set X consisting of n blocks X_{1}, X_{2}, …, X_{n}, such that |X_{i}| = q_{i} for all i and an additional block Y, such that |Y | = j.

The number \binom{j,n}{k,Q} is the number of (n + k)−subsets of X intersecting each block X_{i}, (i = 1, 2, …, n).

From Janjić [4, Theorem 2], we obtain

Proposition 15. If f_{0}(i) = −a_{i} for all i, then

f_{1}(n) = p(Q, n), (n = 1, 2, …, n).

Remark 16. Some sequences in Sloane [7] generated by f_{1} in Proposition 15 are: \underline{A001401}, \underline{A001045}, \underline{A008616}, \underline{A008676}, \underline{A109707}, \underline{A025795}, \underline{A008677}, \underline{A025839}, \underline{A029144}, \underline{A029280}.

Corollary 17. If a = 1, m = 1, and f_{0}(1) = p, where p is a positive integer, then f_{1}(n) = p(1 + p)^{n−1}, which is the number of the colored compositions of n, such that each part may appear in p different colors.

Remark 18. Some sequences in Sloane [7] generated by f_{1} from Corollary 17 are: \underline{A000079}, \underline{A000244}, \underline{A025192}, \underline{A020699}, \underline{A093138}.

Assume that f_{0}(i) = 1, (i ≥ 1). Then, by Corollary 17 we have

f_{m}(n) = (m + 1)^{n−1}.

In this particular case, we obtain the following relationship of our sequence and numbers of words over an alphabet with m + 1 letters.

Corollary 19. The number f_{m}(n) equals the number of words of length n−1 over an alphabet of m + 1 letters.

We consider the case when values of f_{0} are either 0 or 1. Take g_{0}(i) = 1, (i = 1, 2, …). Then, for all i, we have f_{0}(i) ≤ g_{0}(i). Since each term in Equation (1) is nonnegative, we conclude that f_{m}(n) ≤ g_{m}(n), (n ≥ 0) for each m, and since g_{m}(n) = (m + 1)^{n+1}, we obtain

Proposition 20. If the values of f_{0} are either 0 or 1, then f_{m} counts some restricted words over the alphabet {0, 1, …, m}.

Our further investigation may be summarized by the following two problems.

Problem 21. Suppose that f_{0} takes values either 0 or 1.

1. Find either a recurrence or an explicit formula for f_{m}(n) in terms of m and n.

2. Describe the set of restricted words over the alphabet {0, 1, …, m} counted by f_{m}(n).

Problem 22. Solve Problem 21 when f_{0} may have values other than 0 and 1.

4 Some results concerning Problem 21

Proposition 23. Assume that f_{0}(1) = 0, and f_{0}(i) = 1, (i > 1). Then we have

f_{m}(1) = 0, f_{m}(2) = 1,

and

f_{m}(n + 2) = f_{m}(n + 1) + mf_{m}(n).

Proof. The function f_{0} clearly satisfies the following linear recurrence of order 2.

f_{0}(1) = 0, f_{0}(2) = 1, and f_{0}(n + 2) = a_{0}(1)f_{0}(n + 1) + a_{0}(2)f_{0}(n), (n ≥ 1),

where a_{0}(1) = 1, a_{0}(2) = 0.

Now the assertion is an immediate consequence of Corollary 9.

Corollary 24. For n ≥ 0, the number f_{m}(n + 2) from Proposition 23 counts the number of words of length n − 1, over the alphabet {0, 1, …, m}, where no two consecutive letters are nonzero.

Proof. We let g(n) denote the number of required words of length n. We have g(0) = 1 = f_{m}(3), since only an empty word has length 0. Further, we have g(1) = m + 1 = f_{m}(4).

Consider words of length n+1, (n > 0). There are g(n) such words beginning with 0. If a word begins with j ≠ 0, then the next letter must be 0, which yields that there are g(n − 1) such words. Since j may take m different values, we see that g(n + 1) = g(n) + mg(n − 1). It follows that g(n − 1) = f_{m}(n + 2), (n ≥ 0).

Remark 25. In the case m = 1, Corollary 24 gives the following well-known property of the Fibonacci numbers: For n ≥ 1, Fibonacci number F_{n+1} counts 11-avoiding binary words of length n − 1. The case m = 2 gives the analogous property of the Jacosthal numbers.

Remark 26. Some sequences in Sloane [7] generated by f_{m} from Corollary 24 for different m’s are: \underline{A000045}, \underline{A001045}, \underline{A006130}, \underline{A006131}, \underline{A015440}, \underline{A015441}, \underline{A015442}, \underline{A015443}, \underline{A015445}, \underline{A015446}, \underline{A015447}, \underline{A053404}.

Proposition 27. We define

f_{0}(i) = \begin{cases}1, & if i is odd; \\ 0, & if i is even. \end{cases}

Then

f_{m}(1) = 1, f_{m}(2) = m,

and

f_{m}(n + 2) = mf_{m}(n + 1) + f_{m}(n).  (11)

Proof. The function f_{0} satisfies the following recurrence:

f_{0}(1) = 1, f_{0}(2) = 0,
f_{0}(n + 2) = a_{0}(1)f_{0}(n + 1) + a_{0}(2)f_{0}(n),

where a_{0}(1) = 0, a_{0}(2) = 1. The claim is now a simple consequence of Corollary 9.

Corollary 28. If f_{0}(i) is defined as in Proposition 27, then the number f_{m}(n + 1) equals the number n-length over the alphabet {0, 1, …, m} avoiding runs of zeros of odd lengths.

Proof. We let d(n) denote the number of required words of length n. Then, obviously, d(0) = 1, d(1) = m. For n > 1, there are md(n − 1) words of length n beginning with a nonzero letter. If a word begins with 0, then it must begin with at least two zeros. Hence there are d(n − 2) such words.

We conclude that d(n) = f_{m}(n + 1), (n ≥ 0).

As an immediate consequence of Proposition 27, we obtain the following connection of our functions with Fibonacci polynomials F_{n}(x).

Corollary 29. In terms of Proposition 27, we have

f_{m}(n) = F_{n}(m).

Proposition 27 also generalizes the Fibonacci number through the golden ratio.

Corollary 30. If α and β are solutions of the characteristic equation of Equation (11), then the explicit formula for f_{m} in Proposition 27 is

f_{m}(n) = C_{1}(Φ_{m})^{n} + C_{2}(−Φ_{m}^{−1})^{n},

where

C_{1} = \frac{f_{m}(2) − βf_{m}(1)}{α(α − β)}, C_{2} = −\frac{f_{m}(2) − αf_{m}(1)}{β(α − β)}.

For Φ_{m}, we have

1. Φ_{1} is the golden ratio, that is, Φ_{1} = \frac{1+\sqrt{5}}{2}.

2. Φ_{2} is the silver ratio, that is, Φ_{2} = 1 + \sqrt{2}.

3. Φ_{3} is the bronze ratio, that is, Φ_{3} = \frac{3+\sqrt{1}3}{2}.

4. Generally, Φ_{m} = \frac{m+\sqrt{4+m^{2}}}{2} .

Remark 31. Some sequences from Sloane’s [7] generated by recurrence from Corollary 30 are: \underline{A000045}, \underline{A000129}, \underline{A006190}, \underline{A001076}, \underline{A052918}, \underline{A005668}, \underline{A054413}, \underline{A041025}, \underline{A041041}.

Proposition 32. Let k be a positive integer. We define

f_{0}(i; k) = \begin{cases}1, & if 1 ≤ i ≤ k; \\ 0, & otherwise. \end{cases}

Then, for m ≥ 1, we have

f_{m}(i; k) = (m + 1)^{i−1}, (i = 1, 2, …, k),  (12)

and

f_{m}(n + k; k) = m ∑_{i=1}^{k} f_{1}(n + k − i; k).  (13)

Proof. In this case, we have f_{0}(i; k) = 1, a_{0}(i) = 0, (i = 1, 2, …, k). Equation (3) now gives a_{1}(i) = 1, (1 ≤ i ≤ k), which yields that Equation (13) holds for m = 1.

Assume that Equation (13) holds for m. To prove that f_{m+1}(i; k) = (m + 2)^{i−1}, (1 ≤ i ≤ k), it is enough to use induction and the identity:

(m + 2)^{i−1} = (m + 1)^{i−1} + ∑_{j=1}^{i−1}(m + 1)^{j−1}(m + 2)^{i−1−j}.

This identity is easy to prove.

We have a_{m}(i) = m, (i = 1, …, k). Using equation (5), we obtain a_{m+1}(1) = m + f_{m}(1; k) = m + 1. For 2 ≤ i ≤ k, using induction and the identity

m + 1 = m + (m + 1)^{i−1} − m ∑_{j=1}^{i−1}(m + 1)^{i−1−j},

which is also easy to prove, we conclude that the claim holds for m + 1.

It is known that F_{n+2} equals the number of 00-avoiding binary words of length n. Example 32 generalizes this property in the following way:

Corollary 33. The number f_{m}(n + 1; k) from Proposition 32 equals the number of words of length n over the alphabet {0, 1, …, m}, avoiding runs of k zeros.

Proof. Let g(n; k) denote the number of required words of length n. We have g(0; k) = 1, since only the empty word has length 0. Next, we have g(i; k) = (m + 1)^{i}, (1 ≤ i ≤ k − 1), since no word of length < k has a run of k zeros. Suppose that n ≥ k. We calculate g(n + k − 1; k), (n ≥ 1). There are mg(n + k − 2; k) words of length n + k − 1, beginning with a nonzero letter. The remaining words begin with 0. It is clear that there are mg(n+k−3; k) words beginning with an isolated zero. In the same way, we have mg(n + k − 4; k) words beginning with the run of two isolates zeros, and so on.

Finally, there are mg(n + 1; k) words beginning with k − 1 successive zeros. Hence,

g(n + k − 1; k) = m ∑_{i=1}^{k} g(n + k − 1 − i; k), (n ≥ 1).

We see that g(n; k) and f_{m}(n + 1; k) satisfy the same recurrence equation.

Remark 34. In particular, the function f_{1}(n + 1; 2) counts binary words with no adjacent zeros. It follows that f_{1}(n + 1; 2) = F_{n+2}. The case k = 3 produces analogous property of Tribonacci numbers, and so on. Remark 35. Several sequences in Sloane [7] generated by f_{m} form Corollary 33 are: \underline{A000045}, \underline{A028859}, \underline{A155020}, \underline{A125145}, \underline{A086347}, \underline{A180033}, \underline{A180167}, \underline{A000073}, \underline{A119826}, \underline{A000078}, \underline{A209239}, \underline{A001591}, \underline{A001592}, \underline{A122189}, \underline{A079262}, \underline{A104144}, \underline{A122265}, \underline{A168082}, \underline{A168083}, \underline{A168084}, \underline{A220469}, \underline{A220493}, \underline{A249169}.

5 Some results concerning Problem 22

We first derive a recursion for f_{m} in the case when f_{0} is a linear function of i.

Proposition 36. If p, q ≠ 0 are arbitrary numbers, and f_{0}(i) = q(i − 1) + p, (i ≥ 1), then

f_{m}(1) = p, f_{m}(2) = q + p + mp^{2},  (14)

f_{m}(n + 2) = (mp + 2)f_{m}(n + 1) + (mq − mp − 1)f_{m}(n), (n > 0).  (15)

Proof. It is easy to see that f_{0} satisfies the following recurrence:

f_{0}(1) = p, f_{0}(2) = q + p,
f_{0}(n + 2) = a_{0}(1)f_{0}(n + 1) + a_{0}(2)f_{0}(n),

where

a_{0}(1) = 2, a_{0}(2) = −1.

Therefore we may apply Corollary 9. It follows that

f_{m+1}(1) = f_{m}(1) = p, f_{m+1}(2) = [f_{m}(1)]^{2} + f_{m}(2) =
p^{2} + q + p + mp^{2} = q + p + (m + 1)p^{2}.

Also, we have

a_{m+1}(1) = a_{m}(1) + f_{m}(1) = mp + 2 + p = (m + 1)p + 2,
a_{m+1}(2) = a_{m}(2) + f_{m}(2) − a_{m}(1)f_{m}(1) =
mq − mp − 1 + q + p + mp^{2} − (mp + 2)p = (m + 1)q − (m + 1)p − 1,

and the proposition is proved.

In a particular case of the preceding proposition, we find the combinatorial meaning of f_{m}(n) in terms of restricted words.

Corollary 37. 1. If f_{0}(i) = i, (i ≥ 1) then, for m ≥ 1, we have

f_{m}(1) = 1, f_{m}(2) = m + 2,  (16)

f_{m}(n + 2) = (m + 2)f_{m}(n + 1) − f_{m}(n), (n > 0).  (17)

2. The number f_{m}(n) equals the number of 01-avoiding words of length n − 1 over the alphabet {0, 1, 2, 3, …, m + 1}.

3. For n ≥ 1, we have f_{m}(n) = U_{n−1}(\frac{m+2}{2}), where U_{n}(x) is the nth Chebyshev polynomial of the second kind, evaluated at x = \frac{m+2}{2}.

Proof. 1. This is the case q = p = 1 of Proposition 36.

2. We let g(n) denote the number of required words of length n − 1. It is clear that g(1) = 1, and g(2) = m + 2.

At the beginning of each word of length n+1 put a letter of {0, 1, …, m+1} to obtain (m + 2)g(n + 1) words of length n + 2. Exactly g(n) of these words begin with 01. Subtracting this number from (m + 2)g(n + 1), we conclude that g satisfies Recurrence (17), which means that g(n) = f_{m}(n), (n ≥ 1).

3. Equations (16) and (17) are the recurrence for the numbers U_{n−1}(\frac{m+2}{2}).

We see that, for m = 1, formula (17) is the recurrence for Fibonacci numbers of even indices, that is f_{1}(n) = F_{2n}, (n = 1, 2, …).

We stress two particular results. The first concerns a relationship between Fibonacci numbers and Chebyshev polynomials of the second kind, and the second describes the restricted words counting by F_{2n}.

Remark 38. 1. For n ≥ 1, we have

F_{2n} = U_{n−1} (\frac{3}{2}) .

2. The number F_{2n} equals the number of 01-avoiding words of length n − 1 over the alphabet {0, 1, 2}.

Remark 39. Some sequences in Sloane [7] generated by Recurrence (17) are: \underline{A001906}, \underline{A001353}, \underline{A004254}, \underline{A001109}, \underline{A004187}, \underline{A001090}, \underline{A018913}, \underline{A004189}, \underline{A004190}, \underline{A004191}, \underline{A078362}, \underline{A007655}, \underline{A078364}, \underline{A077412}, \underline{A078366}, \underline{A049660}, \underline{A078368}, \underline{A075843}, \underline{A092499}, \underline{A077421}, \underline{A097778}.

We finish our investigation with a result which gives a combinatorial interpretation in terms of restricted words for a class of the functions f_{m}, when f_{0} satisfies a linear recurrence equation of the second order.

Proposition 40. Let p > 1 and q be integers such that 1 ≤ q ≤ p. Define f_{0} recursively in the following way:

f_{0}(1) = 1, f_{0}(2) = p,

and

f_{0}(n + 2) = (p − 1)f_{0}(n + 1) + (p − q)f_{0}(n), (n ≥ 1).

Then, for m ≥ 0, we have

f_{m}(1) = 1, f_{m}(2) = m + p,

and

f_{m}(n + 2) = (m + p − 1)f_{m}(n + 1) + (m + p − q)f_{m}(n).  (18)

Proof. We again apply Corollary 9. Clearly, f_{m}(1) = 1, f_{m}(2) = m + p. Further we have

a_{m+1}(1) = f_{m}(1) + a_{m}(1) = 1 + m + p − 1 = m + p,
a_{m+1}(2) = f_{m}(2) + a_{m}(2) − f_{m}(1)a_{m}(1) =
m + p + m + p − q − m − p + 1 = m + 1 + p − q.

Corollary 41. For m ≥ 0, the number f_{m}(n + 1) from Proposition 40 equals the number of ii-avoiding words of length n over the alphabet {0, 1, …, m + p − 1}, for i ∈ {0, 1, …, q − 1}.

Proof. Let g(n) be the number of required words of length n. We obviously have g(0) = 1, g(1) = m + p.

It remains to prove that g(n) satisfies recurrence equation (18). There are (m+p−q)g(n) words of length n + 2 in which the first two letters are the same. The remaining words begin with two different letters. At the beginning of a word of length n + 1 which begins with a letter i, put a letter j (j ≠ i) to obtain (m + p − 1) words of length n + 2, the second letter of which is i. When i runs over all elements of the alphabet, we obtain all words of length n + 2 beginning with two different letters. Hence,

g(n + 2) = (m + p − 1)g(n + 1) + (m + p − q)g(n), (n ≥ 0).

We conclude that g(n) = f_{m}(n + 1), (n ≥ 0).

Remark 42. Some sequences in Sloane [7] generated by the preceding corollary are: \underline{A000045}, \underline{A000129}, \underline{A126473} , \underline{A126501}, \underline{A126528}, \underline{A122391}, \underline{A180037}, \underline{A099842}, \underline{A003948}, \underline{A015451}, \underline{A003949}, \underline{A015453}, \underline{A003950}, \underline{A015454}, \underline{A003951}, \underline{A015455}, \underline{A003952}, \underline{A003953}, \underline{A015456}, \underline{A015457}, \underline{A003954}, \underline{A170732}, \underline{A170733}, \underline{A170734}. Remark 43. Note that the first two sequences in the above remark are Fibonacci and Pell numbers.

References

[1] M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Algebra Appl. 226/228, (1996), 57–72.

[2] M. Janjić, Determinants and recurrence sequences, J. Integer Seq. 15 (2012), Article 12.3.5.

[3] M. Janjić and B. Petković, A counting function generalizing binomial coefficients and some other classes of integers, J. Integer Seq. 17 (2014), Article 14.3.5.

[4] M. Janjić, A generating function for the numbers of insets, J. Integer Seq. 17 (2014), Article 14.9.7.

[5] T. Koshy, Catalan Numbers with Applications, Oxford University Press, 2009.

[6] E. Munarini, M. Poneti, and S. Rinaldi, Matrix compositions, FPSAC 2006: Formal Power Series and Algebraic Combinatorics, San Diego, 2006, pp. 445–456. Available at

   http://garsia.math.yorku.ca/fpsac06/papers/49.pdf.

[7] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

2000 Mathematics Subject Classification: Primary 05A10; Secondary 11B39. Keywords: linear recurrence equation, composition, Fibonacci number, restricted word.

(Concerned with sequences \underline{A000045}, \underline{A000073}, \underline{A000078}, \underline{A000079}, \underline{A000129}, \underline{A000244}, \underline{A001045}, \underline{A001076}, \underline{A001090}, \underline{A001109}, \underline{A001353}, \underline{A001401}, \underline{A001591}, \underline{A001592}, \underline{A001906}, \underline{A003480}, \underline{A003948}, \underline{A003949}, \underline{A003950}, \underline{A003951}, \underline{A003952}, \underline{A003953}, \underline{A003954}, \underline{A004187}, \underline{A004189}, \underline{A004190}, \underline{A004191}, \underline{A004254}, \underline{A005668}, \underline{A006130}, \underline{A006131}, \underline{A006190}, \underline{A007655}, \underline{A008616}, \underline{A008676}, \underline{A008677}, \underline{A015440}, \underline{A015441}, \underline{A015442}, \underline{A015443}, \underline{A015445}, \underline{A015446}, \underline{A015447}, \underline{A015451}, \underline{A015453}, \underline{A015454}, \underline{A015455}, \underline{A015456}, \underline{A015457}, \underline{A018913}, \underline{A020699}, \underline{A025192}, \underline{A025795}, \underline{A025839}, \underline{A028859}, \underline{A029144}, \underline{A029280}, \underline{A041025}, \underline{A041041}, \underline{A049660}, \underline{A052918}, \underline{A053404}, \underline{A054413}, \underline{A075843}, \underline{A077412}, \underline{A077421}, \underline{A078362}, \underline{A078364}, \underline{A078366}, \underline{A078368}, \underline{A079262}, \underline{A086347}, \underline{A092499}, \underline{A093138}, \underline{A097778}, \underline{A099842}, \underline{A104144}, \underline{A109707}, \underline{A119826}, \underline{A122189}, \underline{A122265}, \underline{A122391}, \underline{A125145}, \underline{A126473}, \underline{A126501}, \underline{A126528}, \underline{A145839}, \underline{A145840}, \underline{A145841}, \underline{A155020}, \underline{A161434}, \underline{A168082}, \underline{A168083}, \underline{A168084}, \underline{A170732}, \underline{A170733}, \underline{A170734}, \underline{A180033}, \underline{A180037}, \underline{A180167}, \underline{A209239}, \underline{A220469}, \underline{A220493}, and \underline{A249169}.)

Received November 9 2014; revised version received January 30 2015; February 5 2015; February 25 2015. Published in Journal of Integer Sequences, May 17 2015.

Return to Journal of Integer Sequences home page.