Polygonal Chain Sequences in the Space of Compact Sets

Steven Schlicker Grand Valley State University Allendale, MI 49401 USA

                   schlicks@gvsu.edu

Lisa Morales University of California, Riverside Riverside, CA 92521 USA

               lmora008@student.ucr.edu

Daniel Schultheis University of California, San Diego La Jolla, CA 92093 USA

                dschulth@math.ucsd.edu

Abstract

Configurations in the hyperspace of all non-empty compact subsets of n-dimensional real space provide a potential wealth of examples of familiar and new integer sequences. For example, Fibonacci-type sequences arise naturally in this geometry. In this paper, we introduce integer sequences that are determined by polygonal chain configurations.

1 Introduction

The Hausdorff metric h provides a way of measuring the distance between nonempty closed and bounded subsets of ℝ^{n} using the standard Euclidean metric d_{E}. The metric h imposes a geometry on H(ℝ^{n}), the hyperspace of all non-empty, compact subsets of ℝ^{n}. The concept of betweenness in this geometry gives rise to interesting examples of integer sequences. In this context we will introduce polygonal chains and new integer sequences related to them. Throughout this article, we let F_{k} denote the k^{th} Fibonacci number (with F_{0} = 0, F_{1} = 1) and L_{k} the k^{th} Lucas number (with L_{0} = 2, L_{1} = 1). Recall that the Lucas numbers L_{k} satisfy

L_{k} = F_{k−1} + F_{k+1} = 2F_{k−1} + F_{k}.

2 The Hausdorff Metric

The Hausdorff metric h was introduced by Felix Hausdorff in the early 20th century as a way to measure the distance between compact sets. The Hausdorff metric imposes a geometry on the space H(ℝ^{n}), which will be the subject of our study. To distinguish between ℝ^{n} and H(ℝ^{n}), we will refer to points in ℝ^{n} and elements in H(ℝ^{n}).

Definition 1. Let A and B be elements in H(ℝ^{n}). The Hausdorff distance, h(A, B), between A and B is

h(A, B) = max{d(A, B), d(B, A)},

where d(A, B) = max_{a∈A}{d(a, B)} and d(a, B) = min_{b∈B}{d_{E}(a, b)}.

As an example, let A be the two point set {(−1, 0), (1, 0)} and B the circle centered at (0,0) of radius 1 in ℝ^{2}. Since A ⊂ B, we have d(A, B) = 0. However, d(B, A) = d_{E}((0, 1), (1, 0)) = \sqrt{2}. Note that d(A, B) ≠ d(B, A), so the function d is not symmetric. That is why we need the maximum of d(A, B) and d(B, A) to obtain a metric. In our example, we have h(A, B) = d(B, A) = \sqrt{2}. See Barnsley [1] for a proof that h is a metric on H(ℝ^{n}). The corresponding metric space, (H(ℝ^{n}), h), is then itself a complete metric space [1].

3 Betweenness in H(ℝ^{n})

Betweenness will play a major role in this paper, allowing us to find new integer sequences. In this section we define “betweenness” in H(ℝ^{n}), mimicking the idea of betweenness in ℝ^{n} under the Euclidean metric. It is in this context that we will later define polygonal chains and introduce an infinite family of new integer sequences. Before we discuss betweenness, we define the dilation of a set, which will play a critical role in what follows.

Definition 2. Let A ∈ H(ℝ^{n}) and let s > 0 be a real number. The dilation of A by s is the set

(A)_{s} = {x ∈ ℝ^{n} : d_{E}(x, a) ≤ s for some a ∈ A}.

As a simple example, the dilation of a single point set A = {a} by s is the closed ball centered at a of radius s. In general, the s-dilation of the set A is the union of all closed s balls centered at points in A. Using dilations, we can alternatively define h(A, B) as the minimum value of s so that the s-dilation of A encloses B and the s-dilation of B encloses A.

Figure 1: Infinitely many elements at the same location between A and B.

An important and useful result about dilations is the following (Theorem 4 from the article [6]).

Theorem 3. Let A ∈ H(ℝ^{n}) and let s > 0. Then (A)_{s} is a compact set with h(A, (A)_{s}) = s. Moreover, if C ∈ H(ℝ^{n}) and h(A, C) ≤ s, then C ⊆ (A)_{s}.

In other words, the element (A)_{s} is the largest element (in the sense of containment) that is a distance s from A. Now we discuss betweenness. In the standard Euclidean geometry, a point x lies between the points a and b if and only if d_{E}(a, b) = d_{E}(a, x) + d_{E}(x, b). We extend this idea to H(ℝ^{n}).

Definition 4. Let A, B ∈ H(ℝ^{n}) with A ≠ B. The element C ∈ H(ℝ^{n}) lies between A and B if h(A, B) = h(A, C) + h(C, B).

Notation: We write ACB to signify that C is between A and B as in Blumenthal [5]. Betweenness in ℝ^{n} is quite different than betweenness in H(ℝ^{n}). Consider the following examples.

Example 5. Let A the union of the origin with the circle centered at (0,0) with radius 10 and B the circle centered at (0,0) with radius 5 in H(ℝ^{2}) as shown in Figure 1. Then h(A, B) = d(A, B) = d(B, A) = 5. The union C ∪C^{∗} of the two dashed circles is the element (A)_{2} ∩ (B)_{3}. Theorem 3 shows that any element X satisfying AXB with h(A, X) = s and h(B, X) = h(A, B) − s must be a subset of (A)_{s} ∩ (B)_{h(A,B)−s}. It is not difficult to see that if X_{c} = {c} ∪ C^{∗} where c is any point on the circle C, then X satisfies AXB with h(A, X) = 2. So in this example, there are infinitely many different elements X satisfying AXB and h(A, X) = 2.

Example 6. Let A = {(−2, 0), (0, 0), (2, 0)} and B = {(−1, 0), (1, 0)} in ℝ^{2} as shown in Figure 2. Let 0 < s < h(A, B) and let t = h(A, B) − s. In this case, the set C = (A)_{s} ∩ (B)_{t} is the four point set C = {c_{1}, c_{2}, c_{3}, c_{4}}. Since any element C′ that lies between A and B at the distance s from A is a subset of C, there are at most 16 elements C′ that could satisfy AC′B with h(A, C′) = s. However, not every subset of C has this property. For example, if C′ = {c_{1}}, then h(A, C′) = 3 + t and C′ does not satisfy AC′B. We leave it to the reader to show that the sets C, {c_{1}, c_{2}, c_{4}} and {c_{1}, c_{3}, c_{4}} are the only sets that lie between A and B at the distance s from A. It is this situation in which we have only finitely many elements

Figure 2: Exactly 3 different elements at the same location between A and B.

between two fixed elements at a specific distance from one of them that will be of interest to us.

The next definition formalizes what is meant when we refer to two elements at the same location between sets A and B.

Definition 7. Let A, B ∈ H(ℝ^{n}) with A ≠ B and let C, C′ ∈ H(ℝ^{n}) satisfy ACB and AC′B. The elements C, C′ are said to be at the same location between A and B if h(A, C) = h(A, C′) = s for some 0 < s < h(A, B).

4 Finding Points Between A and B

Let A, B ∈ H(ℝ^{n}). If a set C ∈ H(ℝ^{n}) satisfies ACB with h(A, C) = s, then it follows from Theorem 3 that C ⊆ (A)_{s} ∩ (B)_{h(A,B)−s}. As we saw in Examples 5 and 6, for some elements A and B there are infinitely many different elements at the same location between A and B and for other A and B there are only finitely many elements at the same location between them. The latter situation is of interest to us. In article [4], the authors show that in order for a pair of elements A and B in H(ℝ^{n}) to have a finite number of elements in H(ℝ^{n}) at a given location between A and B, every point in A must be a common distance r = h(A, B) away from B (that is, d(a, B) = r for all a ∈ A) and every point in B must be that same distance r from A (d(b, A) = r for all b ∈ B). If this condition is not met, there will be infinitely many elements in H(ℝ^{n}) at each location between A and B. If a pair of elements A, B ∈ H(ℝ^{n}) satisfies this condition, we call the pair a configuration.

Definition 8. A finite configuration is a pair [A, B] of finite sets A, B ∈ H(ℝ^{n}) where d(a, B) = d(b, A) = h(A, B) for all a ∈ A and b ∈ B.

In article [4], the authors also show that if [A, B] is a finite configuration, then the number of elements C satisfying ACB and h(A, C) = s is independent of s for all 0 < s < h(A, B). Thus, we denote by #([A, B]) the number of elements between A and B in a finite configuration [A, B] at any distance s.

Note that if [A, B] is a finite configuration, then C = (A)_{s} ∩ (B)_{h(A,B)−s} will be a finite set for any 0 < s < h(A, B), so there are only finitely many subsets of C and #([A, B]) must be finite by Theorem 3 (see Figure 2 for an example). There are infinite configurations, but in this paper we will only be concerned with finite ones.

Figure 3: The P_{4} configuration.

5 String and Polygonal Configurations

Two basic configurations that will be relevant to our work are string and polygonal configurations. A string configuration is any finite set of points equally spaced on a line segment, with sets A and B consisting of alternate points on the line [9]. Figure 2 is an example. If |A ∪ B| = k, then we will call the string configuration [A, B] a k − string and denote it as S_{k}. So Figure 2 shows a 5-string or S_{5}. In article [9] (Theorem 6.1) the authors show

#(S_{k}) = F_{k−1}.

In Figure 2, the elements {c_{1}, c_{2}, c_{3}, c_{4}}, {c_{1}, c_{2}, c_{4}}, and {c_{1}, c_{3}, c_{4}} are the elements that satisfy ACB at the indicated location in this example. This is as expected, since #(S_{5}) = F_{4} = 3.

Another basic family of configurations is the collection of polygonal configurations. Let A and B be the alternate vertices of a regular 2m-gon with m ∈ ℕ. We denote the configuration [A, B] in this case by P_{m} and call this a polygonal configuration [9]. An example of P_{4} is shown in Figure 3, with the set A as the filled points and the set B as the open points. Line segments are drawn between points to indicate the pairs of points a ∈ A and b ∈ B satisfying d_{E}(a, b) = h(A, B). These points will be important in what follows.

Definition 9. Let [A, B] be a finite configuration. The points a ∈ A and b ∈ B are adjacent if d_{E}(a, b) = h(A, B). If a ∈ A, the adjacency set of a, [a]_{B}, is defined as [a]_{B} = {b ∈ B : d_{E}(a, b) = h(A, B)}.

Again in the paper [9] (Theorem 6.3) the authors show

#(P_{m}) = F_{2m} + 2F_{2m−1} = L_{2m}.

String and polygonal configurations form the building components of polygonal chains.

6 Polygonal Chains

A polygonal chain P C_{m,l}^{k} is a configuration obtained by connecting k copies of P_{m} at antipodal points with string configurations of a fixed length l + 1. When k = 1, we define P C_{m,l}^{1} to be P_{m}. Examples of polygonal chains are shown in Figure 4. In this section we determine recursive formulas to find #(P C_{m,l}^{k}).

Figure 4: Top: P C_{2,3}^{3} Bottom: P C_{3,2}^{2}.

6.1 Adjoining Configurations

To compute #(P C_{m,l}^{k}), we will ultimately reduce the problem to one of determining #(X) for smaller configurations X created from adjoins of polygonal and string configurations. Before discussing adjoins, we need to understand equivalent configurations. The idea here is that in the computation of #([A, B]) the distance between adjacent points is irrelevant - only adjacencies matter.

Definition 10. The finite configuration [X, Y] is equivalent to the finite configuration [A, B] if there are bijections f : A → X and g : B → Y such that for all a ∈ A and b ∈ B, we have a adjacent to b if and only if f(a) is adjacent to g(b). When [X, Y] is equivalent to [A, B] we write [X, Y] ∼ [A, B].

It is easy to show that the relation ∼ is an equivalence relation on the set of finite configurations. One important result involving equivalent configurations is that if [X, Y] and [A, B] are equivalent configurations, then #([X, Y]) = #([A, B]) [4] (Theorem 4.1). Now we adjoin a point to a configuration.

Definition 11. Let [A, B] be a finite configuration. The configuration [A, B](a, y) obtained by adjoining a point y ∉ A ∪ B to [A, B] at the point a ∈ A is the configuration [A, B′], where B′ = B ∪ {y}, d_{E}(y, a) = h(A, B), and d_{E}(y, x) > h(A, B) for all x ∈ A ∪ B with x ≠ a.

For example, Figure 5 shows the configuration obtained by adjoining a point y to P_{4} at point a.

One tool for computing #([A, B](a, y)) for a finite configuration [A, B] is the following [9] (Theorem 6.2).

Figure 5: Adjoining a point to P_{4}.

Figure 6: Adjoining P_{2} and P_{3}.

Theorem 12. Let [A, B] be a finite configuration. Define a new configuration X′ by adjoining a point y to [A, B] at the point a ∈ A. Furthermore, assume a is adjacent to k points in B, each of which is adjacent to at least one more point in A. Then

#(X′) = #([A, B]) + #([A − {a}, B]).

As an example, if [A, B] = P_{4} and X′ = [A, B](a, y) as shown in Figure 5, then #(X′) = #(P_{4}) + #(S_{7}) = L_{8} + F_{6} = 55.

We can also adjoin two configurations.

Definition 13. Let [A, B] and [X, Y] be finite configurations and let a ∈ A and y ∈ Y. Let [X′, Y′] be a configuration equivalent to [X, Y] through bijections f : X → X′ and g : Y → Y′ so that

1. h(X′, Y′) = h(A, B),

2. d_{E}(g(y), a) = h(A, B),

3. d(z, A ∪ B) > h(A, B) for all z ∈ X′ ∪ Y′, z ≠ g(y), and

4. d(w, X′ ∪ Y′) > h(A, B) for all w ∈ A ∪ B, w ≠ a.

The adjoin [A, B][a]⊕[X, Y][y] of the configurations at the points a and y is the configuration [A ∪ X′, B ∪ Y′].

As an example, the adjoin of P_{2} with P_{3} at the points a and y is shown in Figure 6. Notation: In this paper, we will consider configurations obtained by adjoining string

configurations at their endpoints to polygonal configurations. If we adjoin a single string configuration to a polygonal configuration, the point of adjoin does not matter due to symmetry. The notation we use for adjoining a string configuration S_{l} to a polygonal configuration P_{m} is P_{m} ⊕ S_{l}. There are cases in which we will adjoin more than one string configuration to

Figure 7: P_{3} ⊕ {S_{1}[1]; S_{1}[4]}.

a polygonal configuration. In these situations, we will label the vertices of a polygonal configuration counterclockwise in order (the starting point does not matter due to symmetry). The notation we will use to adjoin string configurations of length s and t to a polygonal configuration P_{m} at the points labeled i and j, respectively is P_{m} ⊕{S_{s}[i], S_{t}[j]}. An illustration of P_{3} ⊕ {S_{1}[1]; S_{1}[4]} is shown in Figure 7.

The next theorem shows us a method for computing #(X) by breaking X into smaller disconnected configurations. A configuration [A, B] is connected if, given a ∈ A and b ∈ B, there is a sequence {x_{k}}_{k=1}^{m} ∈ A ∪ B such that x_{1} = a, x_{m} = b and x_{i} is adjacent to x_{i+1} for each i [4]. In other words, there is a string in A ∪ B connecting a to b. A configuration is disconnected if it is not connected. The proof of Theorem 15 depends on the next result from the paper [4] (Theorem 6.1).

Theorem 14. Let [A, B] be a configuration and let r = h(A, B). If [X, Y] is a configuration with h(A, B) = h(X, Y), d_{E}(a, y) > h(A, B) for all a ∈ A and y ∈ Y, and d_{E}(b, x) > h(A, B) for all b ∈ B and x ∈ X, then #([A ∪ X, B ∪ Y]) = #([A, B])#([X, Y]).

In other words, if [U, V] is a disconnected configuration constructed from configurations [A, B] and [X, Y], with U = A ∪ X and V = B ∪ Y, then #([U, V]) = #([A, B])#([X, Y]). The next theorem describes another important computation technique.

Theorem 15. Let [A, B] and [X, Y] be finite configurations and let [U, V] = [A, B][a] ⊕ [X, Y][y] for some a ∈ A and y ∈ Y. Then

#([U, V]) = #([A, B]) #([X, Y]) + #([A ⊕ S_{1}[a], B]) #[X, Y ⊕ S_{1}[y]].

Proof. Without loss of generality, we assume h(A, B) = h(X, Y). Let s, t > 0 with s + t = h(A, B). Let C = (A)_{s} ∩ (B)_{t} be the largest element that lies between A and B at a distance s from A, and let Z = (X)_{s} ∩ (Y)_{t} be the largest element that lies between X and Y at a distance s from X. Then in the configuration [U, V], the largest element between A ∪ X and B ∪ Y will be C ∪ Z ∪ {c_{0}}, where c_{0} is the point which lies between the newly adjacent points a and y. See Figure 6 for an illustration.

We now consider which subsets D of C ∪ Z ∪ {c_{0}} satisfy UDV. Since D satisfies UDV, we know that [a′]_{D} ≠ ∅, [b′]_{D} ≠ ∅, [x′]_{D} ≠ ∅, and [y′]_{D} ≠ ∅ for all a′ ∈ A, b′ ∈ B, x′ ∈ X, and y′ ∈ Y. We consider two cases.

Case 1 c_{0} ∉ D. In this case, let C′ = {d ∈ D : d ∈ [a′]_{D} for some a′ ∈ A} and let Z′ = D−C′. By construction, if c′ ∈ C′, then c′ ≠ c_{0} and so c′ ∈ C. Thus C′ ⊆ C. If z′ ∈ Z′, then z′ ≠ c_{0} and z′ ∈ Z. Now, if a′ ∈ A and b′ ∈ B, we know [a′]_{D} ≠ ∅ and [b′]_{D} ≠ ∅. Therefore, [a′]_{C′} ≠ ∅ and [b′]_{C′} ≠ ∅. So C′ satisfies AC′B. Similarly, Z′ satisfies XZ′Y. By Theorem 14, the number of such sets D = C′ ∪ Z′ is #([A, B]) #([X, Y]).

Case 2 c_{0} ∈ D. In this case, we have c_{0} ∈ [a]_{D} and c_{0} ∈ [y]_{D}. The existence of the point c_{0} in D allows for the potential removal of other points in D that are adjacent to a or y. In other words, D = C′ ∪ {c_{0}} ∪ Z′, where C′ satisfies AC′(B ⊕ S_{1}[a]) and Z′ satisfies (X ⊕ S_{1}[y])Z′Y. The number of such sets D is #([A ⊕ S_{1}[a], B]) · #(X, Y ⊕ S_{1}[y]]).

By combining the results of the two cases here, we arrive at the expected formula #([U, V]) = #([A, B]) #([X, Y]) + #([A ⊕ S_{1}[a], B]) #[X, Y ⊕ S_{1}[y]].

Figure 8: P C_{2,3}^{3} ⊕ S_{1}.

As an example, consider the configuration X obtained by adjoining P_{3} and P_{2} as shown in Figure 6. Theorem 15 shows

#(X) = #(P_{3}) #(P_{2}) + #(P_{3} ⊕ S_{1}) #(P_{2} ⊕ S_{1}).

Now Theorem 12 gives us #(P_{3} ⊕ S_{1}) = #(P_{3}) + #(S_{5}) = 18 + 3 = 21 and #(P_{2} ⊕ S_{1}) = #(P_{2}) + #(S_{3}) = 7 + 1 = 8. So

#(X) = (18)(7) + (21)(8) = 294.

7 Finding #(P C_{m,l}^{k})

In this section, we determine a pair of recursive formulas to find #(P C_{m,l}^{k}). As the first step in our computations, we determine #(X ⊕ S_{t}) for t ≥ 2 for any finite configuration X in terms of #(X) and #(X ⊕ S_{1}).

Theorem 16. Let X be a finite configuration and t ≥ 2. Then

#(X ⊕ S_{t}) = F_{t}#(X ⊕ S_{1}) + F_{t−1}#(X).

Proof. Using Theorem 12, we see that our theorem is certainly true with t = 2 and t = 3. We proceed by induction and suppose our theorem is true for all s, 1 ≤ s ≤ t. Then

#(X ⊕ S_{t+1}) = #(X ⊕ S_{t}) + #(X ⊕ S_{t−1})
= [F_{t}#(X ⊕ S_{1}) + F_{t−1}#(X)] + [F_{t−1}#(X ⊕ S_{1}) + F_{t−2}#(X)]
= (F_{t} + F_{t−1})#(X ⊕ S_{1}) + (F_{t−1} + F_{t−2})#(X)
= F_{t+1}#(X ⊕ S_{1}) + F_{t}#(X).

By P C_{m,l}^{k} ⊕S_{t} we mean the adjoin of S_{t} with P C_{m,l}^{k} at a point antipodal to the connected strings. An example of P C_{2,3}^{3} ⊕ S_{1} is shown in Figure 8. A direct consequence of Theorem 16 is

Corollary 17. For m ≥ 2, k ≥ 1, l ≥ 1, and t ≥ 2,

#(P C_{m,l}^{k} ⊕ S_{t}) = F_{t}#(P C_{m,l}^{k} ⊕ S_{1}) + F_{t−1}#(P C_{m,l}^{k})

Now we add in the case when t = 1 for polygonal configurations. Note first that

L_{2m} + F_{2m−2} = (F_{2m−2} + F_{2m−1}) + F_{2m+1} = F_{2m} + F_{2m+1} = F_{2m+2}.

Corollary 18. For m ≥ 2 and t ≥ 1,

#(P_{m} ⊕ S_{t}) = F_{t}F_{2m+2} + F_{t−1}L_{2m}.

Proof. When t = 1, a direct application of Theorem 12 gives us

#(P_{m} ⊕ S_{1}) = #(P_{m}) + #(S_{2m−1}) = L_{2m} + F_{2m−2} = F_{2m+2} = F_{1}F_{2m+2} + F_{0}L_{2m}.

For t ≥ 2, we use Theorem 16 to obtain

#(P_{m} ⊕ S_{t}) = F_{t}#(P_{m} ⊕ S_{1}) + F_{t−1}#(P_{m}) = F_{t}F_{2m+2} + F_{t−1}L_{2m}.

We need one more preliminary calculation before we determine #(P C_{m,l}^{k}).

Lemma 19. For m ≥ 2,

#(P_{m} ⊕ {S_{1}[1]; S_{1}[m + 1]}) = F_{m+2}^{2}.

Proof. Figure 7 shows an example of the configurations in question. By Theorem 12 and Corollary 18,

#(P_{m} ⊕ {S_{1}[1]; S_{1}[m + 1]}) = #(P_{m} ⊕ S_{1}) + #(S_{2m−1} ⊕ S_{1}[m])
= F_{2m+2} + #(S_{2m−1}) + #(S_{m−1})^{2} = F_{2m+2} + F_{2m−2} + F_{m−2}^{2}.

We use the identity

F_{2m} = F_{m+1}^{2} − F_{m−1}^{2}

for m ≥ 1 (see [7], Corollary 5.4 or [3], Identity 14 (note that f_{m} = F_{m+1})) to obtain

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

Now we derive recursive formulas for #(P C_{m,l}^{k}) and #(P C_{m,l}^{k} ⊕S_{1}) in terms of #(P C_{m,l}^{k−1}) and #(P C_{m,l}^{k−1} ⊕ S_{1}). Remember that #(P C_{m,l}^{1}) = #(P_{m}) = L_{2m} and #(P C_{m,l}^{1} ⊕ S_{1}) = #(P_{m} ⊕ S_{1}) = F_{2m+2}. To include all cases together, we extend the Fibonacci sequence in the negative direction by defining F_{−1} = 1. We also define X ⊕ S_{0} to be X for any finite configuration X.

Theorem 20. For m ≥ 2, k ≥ 2, and l ≥ 1,

#(P C_{m,l}^{k}) = (L_{2m}F_{l−2} + F_{2m+2}F_{l−1}) #(P C_{m,l}^{k−1}) + (L_{2m}F_{l−1} + F_{2m+2}F_{l}) #(P C_{m,l}^{k−1} ⊕ S_{1})

where

#(P C_{m,l}^{k} ⊕ S_{1}) = (F_{2m+2}F_{l−2} + F_{l−1}F_{m+2}^{2}) #(P C_{m,l}^{k−1})
+ (F_{2m+2}F_{l−1} + F_{l}F_{m+2}^{2}) #(P C_{m,l}^{k−1} ⊕ S_{1}).

Figure 9: Using Theorem 15 to compute #(P C_{m,l}^{k}) and #(P C_{m,l}^{k} ⊕ S_{1}).

Proof. We use Theorem 15 applied at the adjacent points indicated with an asterisk as illustrated in Figure 9, and Corollary 17:

#(P C_{m,l}^{k}) = #(P_{m})#(P C_{m,l}^{k−1} ⊕ S_{l−1}) + #(P_{m} ⊕ S_{1})#(P C_{m,l}^{k−1} ⊕ S_{l})
= L_{2m} (F_{l−1}#(P C_{m,l}^{k−1} ⊕ S_{1}) + F_{l−2}#(P C_{m,l}^{k−1}))
+ F_{2m+2} (F_{l}#(P C_{m,l}^{k−1} ⊕ S_{1}) + F_{l−1}#(P C_{m,l}^{k−1}))

= (L_{2m}F_{l−1} + F_{2m+2}F_{l}) #(P C_{m,l}^{k−1} ⊕ S_{1}) + (L_{2m}F_{l−2} + F_{2m+2}F_{l−1}) #(P C_{m,l}^{k−1}).

Finally, we determine the recursive formula for #(P C_{m,l}^{k} ⊕ S_{1}) by using Theorem 15, applied at the adjacent points indicated with an asterisk in Figure 9. This gives us #(P C_{m,l}^{k} ⊕ S_{1}) = #(P C_{m,l}^{k−1} ⊕ S_{l−1})#(P_{m} ⊕ S_{1}) + #(P C_{m,l}^{k−1} ⊕ S_{l})#(P_{m} ⊕ {S_{1}[1]; S_{1}[m + 1]}). Therefore, Lemma 19 and Corollary 17 yield

#(P C_{m,l}^{k} ⊕ S_{1}) = F_{2m+2}#(P C_{m,l}^{k−1} ⊕ S_{l−1}) + #(P C_{m,l}^{k−1} ⊕ S_{l})F_{m+2}^{2}
= F_{2m+2} (F_{l−1}#(P C_{m,l}^{k−1} ⊕ S_{1}) + F_{l−2}#(P C_{m,l}^{k−1}))
+ (F_{l}#(P C_{m,l}^{k−1} ⊕ S_{1}) + F_{l−1}#(P C_{m,l}^{k−1})) F_{m+2}^{2}
= (F_{2m+2}F_{l−1} + F_{l}F_{m+2}^{2}) #(P C_{m,l}^{k−1} ⊕ S_{1})
+ (F_{2m+2}F_{l−2} + F_{l−1}F_{m+2}^{2}) #(P C_{m,l}^{k−1}).

As examples of the use of Theorem 20,

#(P C_{3,1}^{2}) = L_{6}#(P C_{3,1}^{1}) + F_{8}#(P C_{3,1}^{1} ⊕ S_{1})

= 18#(P_{3}) + 21#(P_{3} ⊕ S_{1})

= 18(18) + 21(21)

= 765,

#(P C_{2,2}^{2}) = F_{2m+2}#(P C_{m,l}^{k−1}) + [L_{2m} + F_{2m+2}] #(P C_{m,l}^{k−1} ⊕ S_{1})

= 8#(P_{2}) + [7 + 8]#(P_{2} ⊕ S_{1})

= (8)(7) + (15)(8)

= 176,

Sloane A-number  i  1  2  3  4  5
\underline{A152927}  #(P_{2,1}^{i}) 7  113 1815 29153 468263
\underline{A152928}  #(P_{i,1}^{2})  113  765  5234  35865
\underline{A152929}  #(P_{2,i}^{2}) 113 176  289  465  754
\underline{A152930}  #(P_{2,2}^{i}) 7  176 4393 109649 2736832
\underline{A152931}  #(P_{i,2}^{3})  4393 80361 1425131 25671393
\underline{A152932}  #(P_{3,i}^{3}) 32733 80361 215658 559305 1469565

Table 1: Some polygonal chain sequences

and

#(P C_{2,3}^{2}) = [L_{4}F_{1} + F_{6}F_{2}] #(P C_{2,3}^{1}) + [L_{4}F_{2} + F_{6}F_{l}] #(P C_{2,3}^{1} ⊕ S_{1})

= [(7)(1) + (8)(1)]#(P_{2}) + [(7)(1) + (8)(2)]#(P_{2} ⊕ S_{1}) = (15)(7) + (23)(8) = 289.

8 Polygonal Chain Sequences

Theorem 20 gives us recursive formulas for finding #(P C_{m,l}^{k}). By fixing any two of m, k, or l and letting the other parameter vary, we create infinite families of integer sequences. Examples of the first few terms of several of these sequences are given in Table 1. We suspect that it is possible to define many new types of configurations in this geometry that provide more interesting and previously unknown integer sequences.

9 Asymptotic Behavior

Polygonal chain sequences appear to exhibit asymptotically exponential behavior as the sequences of successive quotients in Table 2 illustrate. These sequences are natural extensions of string and polygonal sequences, both of which involve Fibonacci and Lucas numbers, so we might expect the ratios of polygonal chain sequences to do so as well. To understand this behavior, we investigate these quotients.

9.1 Fixing m and l

In this section we consider the asymptotic behavior of the sequences obtained by letting k vary for fixed values of m and l. For easier notation, let X_{k,m,l} = #(P C_{m,l}^{k}) and Y_{k,m,l} = #(P C_{m,l}^{k} ⊕ S_{1}). Theorem 20 shows that

X_{k,m,l} = a_{m,l}X_{k−1,m,l} + b_{m,l}Y_{k−1,m,l} and Y_{k,m,l} = c_{m,l}X_{k−1,m,l} + d_{m,l}Y_{k−1,m,l} (1)

\begin{matrix}i & 6 & 7 & 8 & 9 & 10 \\ \frac{#(P_{2,1}^{i+1})}{#(P_{2,1}^{i})} & 16.06225775 & 16.06225775 & 16.06225775 & 16.06225775 & 16.06225775 \\ \frac{#(P_{i+1,1}^{2})}{#(P_{i,1}^{2})} & 6.854063862 & 6.854096407 & 6.854101155 & 6.854101848 & 6.854101949 \\ \frac{#(P_{2,i+1}^{2})}{#(P_{2,i}^{2})} & 1.618539787 & 1.617840851 & 1.618107769 & 1.618005808 & 1.618044753 \\ \frac{#(P_{2,2}^{i+1})}{#(P_{2,2}^{i})} & 24.95993579 & 24.95993579 & 24.95993579 & 24.95993579 & 24.95993579 \\ \frac{#(P_{i+1,2}^{3})}{#(P_{i,2}^{3})} & 17.95473888 & 17.94023899 & 17.94580726 & 17.94368472 & 17.94449609 \\ \frac{#(P_{3,i+1}^{3})}{#(P_{3,i}^{3})} & 2.619410257 & 2.617508525 & 2.618234731 & 2.617957317 & 2.618063275 \end{matrix}

Table 2: Ratios of polygonal chain sequences to 8 decimal places.

for values of a_{m,l}, b_{m,l}, c_{m,l}, and d_{m,l} that depend on only m and l. We can determine the asymptotic behavior of X_{k,m,l} by writing this system in matrix form:

[\begin{matrix}X_{k,m,l} \\ Y_{k,m,l} \end{matrix}] = [\begin{matrix}a_{m,l} & b_{m,l} \\ c_{m,l} & d_{m,l} \end{matrix}] [\begin{matrix}X_{k−1,m,l} \\ Y_{k−1,m,l} \end{matrix}] .

Let M_{m,l} = [\begin{matrix}a_{m,l} & b_{m,l} \\ c_{m,l} & d_{m,l} \end{matrix}]. Then

[\begin{matrix}X_{k,m,l} \\ Y_{k,m,l} \end{matrix}] = (M_{m,l})^{k−1} [\begin{matrix}X_{1,m,l} \\ Y_{1,m,l} \end{matrix}] .

The eigenvalues of M_{m,l} are

λ_{m,l} = \frac{(d_{m,l} + a_{m,l}) + \sqrt{(d_{m,l} − a_{m,l})^{2} + 4b_{m,l}c_{m,l}}}{2}

and

\overline{λ}_{m,l} = \frac{(d_{m,l} + a_{m,l}) − \sqrt{(d_{m,l} − a_{m,l})^{2} + 4b_{m,l}c_{m,l}}}{2} .

Since (d_{m,l} − a_{m,l})^{2} + 4b_{m,l}c_{m,l} > 0, we see that M_{m,l} has two distinct real eigenvalues. Thus M_{m,l} is diagonalizable to the matrix D_{m,l} = [\begin{matrix}λ_{m,l} & 0 \\ 0 & \overline{λ}_{m,l} \end{matrix}]. If Q_{m,l} is the matrix whose columns are the eigenvectors of M_{m,l}, then

[\begin{matrix}X_{k,m,l} \\ Y_{k,m,l} \end{matrix}] = (Q_{m,l} [\begin{matrix}(λ_{m,l})^{k−1} & 0 \\ 0 & (\overline{λ}_{m,l})^{k−1} \end{matrix}] Q_{m,l}^{−1}) [\begin{matrix}X_{1,m,l} \\ Y_{1,m,l} \end{matrix}] .

Note that Q_{m,l} = [ 1 1_{\frac{λ_{m,l}−a_{m,l}}{b_{m,l}} \frac{d_{m,l}−λ_{m,l}}{b_{m,l}}} ] and Q_{m,l}^{−1} = (\frac{1}{2λ_{m,l}−(a_{m,l}+d_{m,l})}) [\begin{matrix}λ_{m,l} − d_{m,l} & b_{m,l} \\ λ_{m,l} − a_{m,l} & −b_{m,l} \end{matrix}].

Since X_{1,m,l} = L_{2m} and Y_{1,m,l} = F_{2m+2}, we have

X_{k,m,l} = R_{m,l}λ_{m,l}^{k−1} + S_{m,l}\overline{λ}_{m,l}^{k−1}  (2)

where R_{m,l} = (\frac{1}{2λ_{m,l}−(a_{m,l}+d_{m,l})}) ((λ_{m,l} − d_{m,l})L_{2m} + b_{m,l}F_{2m+2}) and

S_{m,l} = (\frac{1}{2λ_{m,l}−(a_{m,l}+d_{m,l})}) ((λ_{m,l} − a_{m,l})L_{2m} − b_{m,l}F_{2m+2}). So (2) provides a non-recursive

formula for computing X_{k,m,l}. Now λ_{m,l} > \overline{λ}_{m,l}, so we have

\frac{X_{k,m,l}}{X_{k−1,m,l}} = \frac{R_{m,l}λ_{m,l}^{k−1} + S_{m,l}\overline{λ}_{m,l}^{k−1}}{R_{m,l}λ_{m,l}^{k−2} + S_{m,l}\overline{λ}_{m,l}^{k−2}}

= \frac{R_{m,l}λ_{m,l} + S_{m,l}\overline{λ}_{m,l} (\frac{\overline{λ}_{m,l}}{λ_{m,l}} )^{k−2}}{R_{m,l} + S_{m,l} (\frac{\overline{λ}_{m,l}}{λ_{m,l}} )^{k−2}}

→ \frac{R_{m,l}λ_{m,l}}{R_{m,l}}

= λ_{m,l}

as k → ∞. Thus,

lim_{k→∞} \frac{X_{k,m,l}}{X_{k−1,m,l}} = λ_{m,l}.

The values of a_{m,l}, b_{m,l}, c_{m,l}, and d_{m,l} are given by Theorem 20:

a_{m,l} = L_{2m}F_{l−2} + F_{2m+2}F_{l−1}, b_{m,l} = L_{2m}F_{l−1} + F_{2m+2}F_{l},
c_{m,l} = F_{2m+2}F_{l−2} + F_{l−1}F_{m+2}^{2}, and d_{m,l} = F_{2m+2}F_{l−1} + F_{l}F_{m+2}^{2}.

Thus the sequence of polygonal chain numbers as k varies for fixed m and l behaves asymptotically as the exponential sequence with ratio λ_{m,l}. For example, λ_{2,1} = 8 + \sqrt{65} ≈ 16.06225775 and λ_{2,2} = \frac{25+3\sqrt{69}}{2} ≈ 24.95993579 (compare to the ratios in Table 2).

9.2 Limits of Fibonacci and Lucas Sequences

To determine the asymptotic behavior of the sequences {X_{k,m,l}} as either m or l vary, we will need some limits of sequences of quotients of Fibonacci and Lucas numbers. Let φ = \frac{1+\sqrt{5}}{2} be the golden ratio. The following results concerning Fibonacci and Lucas numbers are well known.

• lim_{m→∞} \frac{F_{m+1}}{F_{m}} = φ ([7] Corollary 8.5, [8] (25))

• lim_{m→∞} \frac{L_{m+1}}{L_{m}} = φ ([7] Corollary 8.7, [8] (25))

• φ^{m} = F_{m}φ + F_{m−1} for m ≥ 1 ([7] Lemma 5.1, [3] Corollary 33)

• lim_{m→∞} \frac{F_{m+j}}{F_{m}} = φ^{j} for j ≥ 0 ([3] Corollary 31, [8] (27))

• For j ≥ 0, lim_{m→∞} \frac{L_{m+j}}{L_{m}} = φ^{j} ([8] (27))

We will also need other limits of ratios of Fibonacci and Lucas numbers. Lemma 21. For m ≥ 2 and j ≥ 0,

1. For j ≥ 0, lim_{m→∞} \frac{L_{m}}{F_{m+j}} = \frac{1 + φ^{2}}{φ^{j+1}}

2. lim_{m→∞} \frac{F_{2m+2}}{F_{m+2}^{2}} = \frac{φ^{4} − 1}{φ^{4}} = \frac{1 + φ^{2}}{φ^{3}}

3. lim_{m→∞} \frac{F_{2m+2}}{F_{m+3}^{2}} = \frac{φ^{4} − 1}{φ^{6}} = \frac{1 + φ^{2}}{φ^{5}}

4. lim_{m→∞} \frac{F_{2m+4}}{F_{m+2}^{2}} = \frac{φ^{4} − 1}{φ^{2}} = \frac{1 + φ^{2}}{φ}

5. lim_{m→∞} \frac{L_{2m}}{F_{m+2}^{2}} = \frac{(φ^{2} + 1)^{2}}{φ^{6}}

Proof. We prove 2 and 5, the remainder are similar. Recalling that φ^{2} − 1 = φ,

lim_{m→∞} \frac{F_{2m+2}}{F_{m+2}^{2}} = lim_{m→∞} \frac{F_{m+2}^{2} − F_{m}^{2}}{F_{m+2}^{2}}

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

= 1 − (\frac{1}{φ^{2}} )^{2}

= \frac{φ^{4} − 1}{φ^{4}}

= \frac{(1 + φ^{2}) φ}{φ^{4}}

= \frac{1 + φ^{2}}{φ^{3}} .

Finally, we use Identity 13 from the book [3] (F_{2m+1} = F_{m}^{2} + F_{m+1}^{2}) to see

lim_{m→∞} \frac{L_{2m}}{F_{m+2}^{2}} = lim_{m→∞} \frac{F_{2m−1} + F_{2m+1}}{F_{m+2}^{2}}

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

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

= (\frac{1}{φ^{3}} )^{2} + 2 (\frac{1}{φ^{2}} )^{2} + (\frac{1}{φ})^{2}

= \frac{1 + 2φ^{2} + φ^{4}}{φ^{6}}

= \frac{(φ^{2} + 1)^{2}}{φ^{6}} .

9.3 Fixing k and l

In this section, we fix k and l and let m vary and investigate the asymptotic behavior of the resulting sequence X_{k,m,l}. We will need to know limits of ratios of the terms a_{m,l}, b_{m,l}, c_{m,l} and d_{m,l} as m approaches infinity. Lemma 22. Let G_{l} = \frac{(1+φ^{2})F_{l−1}+φ^{3}F_{l}}{(1+φ^{2})F_{l−2}+φ^{3}F_{l−1}} . Then for l ≥ 1,

1. lim_{m→∞} \frac{a_{m+1,l}}{a_{m,l}} = φ^{2}

2. lim_{m→∞} \frac{b_{m+1,l}}{a_{m,l}} = φ^{2}G_{l}

3. lim_{m→∞} \frac{b_{m,l}}{a_{m,l}} = G_{l}

4. lim_{m→∞} \frac{c_{m,l}}{a_{m,l}} = \frac{φ^{3}}{1 + φ^{2}}

5. lim_{m→∞} \frac{c_{m+1,l}}{a_{m,l}} = \frac{φ^{5}}{1 + φ^{2}}

6. lim_{m→∞} \frac{d_{m,l}}{a_{m,l}} = (\frac{φ^{3}}{1 + φ^{2}} ) G_{l}.

7. lim_{m→∞} \frac{d_{m+1,l}}{a_{m,l}} = (\frac{φ^{5}}{1 + φ^{2}} ) G_{l}.

Proof. We prove 5, the others are similar:

lim_{m→∞} \frac{c_{m+1,l}}{a_{m,l}} = lim_{m→∞} \frac{F_{2m+4}F_{l−2} + F_{m+3}^{2}F_{l−1}}{L_{2m}F_{l−2} + F_{2m+2}F_{l−1}}

= lim_{m→∞} \frac{(\frac{F_{2m+4}}{F_{2m+2}} ) F_{l−2} + (\frac{F_{m+3}^{2}}{F_{2m+2}} ) F_{l−1}}{(\frac{L_{2m}}{F_{2m+2}} ) F_{l−2} + F_{l−1}}

= \frac{(φ^{2}) F_{l−2} + (\frac{φ^{5}}{φ^{2}+1}) F_{l−1}}{(\frac{1+φ^{2}}{φ^{3}} ) F_{l−2} + F_{l−1}}

= (\frac{φ^{5}}{1 + φ^{2}} ) (\frac{(\frac{1+φ^{2}}{φ^{3}} ) F_{l−2} + F_{l−1}}{(\frac{1+φ^{2}}{φ^{3}} ) F_{l−2} + F_{l−1}} )

= \frac{φ^{5}}{1 + φ^{2}} .

Before we can analyze the asymptotic behavior of the polygonal chain sequence, we need to understand how the sequences {Y_{k,m,l}} and {X_{k,m,l}} are related as m varies.

Lemma 23. For k ≥ 1,

lim_{m→∞} \frac{Y_{k,m,l}}{X_{k,m,l}} = \frac{φ^{3}}{1 + φ^{2}} .

Proof. When k = 1 we have lim_{m→∞} \frac{Y_{1,m,l}}{X_{1,m,l}} = lim_{m→∞} \frac{F_{2m+2}}{L_{2m}} = \frac{1}{\frac{1}{φ^{3}} + \frac{1}{φ}} = \frac{φ^{3}}{1 + φ^{2}} . So the claim is

true for k = 1. We proceed by induction and assume the claim is true for some k ≥ 1. Then (1) shows

lim_{m→∞} \frac{Y_{k+1,m,l}}{X_{k+1,m,l}} = lim_{m→∞} \frac{c_{m,l}X_{k,m,l} + d_{m,l}Y_{k,m,l}}{a_{m,l}X_{k,m,l} + b_{m,l}Y_{k,m,l}}

= lim_{m→∞} \frac{(\frac{c_{m,l}}{a_{m,l}} ) + (\frac{d_{m,l}}{a_{m,l}} ) (\frac{Y_{k,m,l}}{X_{k,m,l}} )}{1 + (\frac{b_{m,l}}{a_{m,l}} ) (\frac{Y_{k,m,l}}{X_{k,m,l}} )}

= \frac{(\frac{φ^{3}}{1+φ^{2}} ) + (\frac{φ^{3}}{1+φ^{2}} ) G_{l} (\frac{φ^{3}}{1+φ^{2}} )}{1 + G_{l} (\frac{φ^{3}}{φ^{2}+1})}

= \frac{φ^{3}}{1 + φ^{2}} .

Now we can identify the asymptotic behavior of the polygonal chain sequence when m varies.

Theorem 24. For k ≥ 1 and l ≥ 1,

lim_{m→∞} \frac{X_{k,m+1,l}}{X_{k,m,l}} = φ^{2k} and lim_{m→∞} \frac{Y_{k,m+1,l}}{X_{k,m,l}} = \frac{φ^{2k+3}}{1 + φ^{2}} .

Proof. The proof will be by induction on k. Now X_{1,m,l} = L_{2m} and lim_{m→∞} \frac{X_{1,m+1,l}}{X_{1,m,l}} =

lim_{m→∞} \frac{L_{2m+2}}{L_{2m}} = φ^{2}. Also, Y_{1,m,l} = F_{2m+2} and lim_{m→∞} \frac{Y_{1,m+1,l}}{X_{1,m,l}} = lim_{m→∞} \frac{F_{2m+4}}{L_{2m}} = \frac{1}{\frac{1}{φ^{5}} + \frac{1}{φ^{3}}} =

\frac{φ^{5}}{1 + φ^{2}} . Thus, our theorem is true when k = 1. Assume the theorem is true for some k ≥ 1.

Then

lim_{m→∞} \frac{X_{k+1,m+1,l}}{X_{k+1,m,l}} = lim_{m→∞} \frac{a_{m+1,l}X_{k,m+1,l} + b_{m+1,l}Y_{k,m+1,l}}{a_{m,l}X_{k,m,l} + b_{m,l}Y_{k,m,l}}

= lim_{m→∞} \frac{(\frac{a_{m+1,l}}{a_{m,1}} ) (\frac{X_{k,m+1,l}}{X_{k,m,l}} ) + (\frac{b_{m+1,l}}{a_{m,l}} ) (\frac{Y_{k,m+1,l}}{X_{k,m,l}} )}{1 + (\frac{b_{m,l}}{a_{m,1}} ) (\frac{Y_{k,m,l}}{X_{k,m,l}} )}

= \frac{(φ^{2}) (φ^{2k}) + (φ^{2}G_{l}) (\frac{φ^{2k+3}}{1+φ^{2}} )}{1 + (G_{l}) (\frac{φ^{3}}{1+φ^{2}} )}

= φ^{2k+2}

and

lim_{m→∞} \frac{Y_{k+1,m+1,l}}{X_{k+1,m,l}} = lim_{m→∞} \frac{c_{m+1,l}X_{k,m+1,l} + d_{m+1,l}Y_{k,m+1,l}}{a_{m,l}X_{k,m,l} + b_{m,l}Y_{k,m,l}}

= lim_{m→∞} \frac{(\frac{c_{m+1,l}}{a_{m,l}} ) (\frac{X_{k,m+1,l}}{X_{k,m,l}} ) + (\frac{d_{m+1,l}}{a_{m,l}} ) (\frac{Y_{k,m+1,l}}{X_{k,m,l}} )}{1 + (\frac{b_{m,l}}{a_{m,l}} ) (\frac{Y_{k,m,l}}{X_{k,m,l}} )}

= \frac{(\frac{φ^{5}}{1+φ^{2}} ) (φ^{2k}) + (\frac{φ^{5}}{1+φ^{2}} ) G_{l} (\frac{φ^{2k+3}}{1+φ^{2}} )}{1 + (G_{l}) (\frac{φ^{3}}{1+φ^{2}} )}

= \frac{φ^{2k+5}}{1 + φ^{2}} .

So the sequence of polygonal chain numbers as m varies for fixed k and l behaves asymptotically as the exponential sequence with ratio φ^{2k}. For example, φ^{4} ≈ 6.854101954 and φ^{6} ≈ 17.94427186 (compare to the ratios in Table 2). Note that the limits in these cases are independent of the value of l.

9.4 Fixing k and m

In this section, we fix k and m and let l vary and investigate the asymptotic behavior of the resulting sequence X_{k,m,l}. Again, we begin with limits of sequences of ratios of a_{m,l}, b_{m,l}, c_{m,l}, and d_{m,l}, this time as l goes to infinity.

Lemma 25. Let H_{m} = \frac{F_{2m+2}+F_{m+2}^{2}φ}{L_{2m}+F_{2m+2}φ}. Then for m ≥ 2,

1. lim_{l→∞} \frac{a_{m,l+1}}{a_{m,l}} = φ

2. lim_{l→∞} \frac{b_{m,l}}{a_{m,l}} = φ

3. lim_{l→∞} \frac{b_{m,l+1}}{a_{m,l}} = φ^{2}

4. lim_{l→∞} \frac{c_{m,l}}{a_{m,l}} = H_{m}

5. lim_{l→∞} \frac{c_{m,l+1}}{a_{m,l}} = (φ) H_{m}

6. lim_{l→∞} \frac{d_{m,l+1}}{a_{m,l}} = (φ^{2}) H_{m}.

Proof. We verify 5 and leave the others for the reader:

lim_{l→∞} \frac{c_{m,l+1}}{a_{m,l}} = lim_{l→∞} \frac{F_{2m+2}F_{l−1} + F_{m+2}^{2}F_{l}}{L_{2m}F_{l−2} + F_{2m+2}F_{l−1}}

= lim_{l→∞} \frac{F_{2m+2} + F_{m+2}^{2} (\frac{F_{l}}{F_{l−1}} )}{L_{2m} (\frac{F_{l−2}}{F_{l−1}} ) + F_{2m+2}}

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

= (φ) (\frac{F_{2m+2} + F_{m+2}^{2}φ}{L_{2m} + F_{2m+2}φ}) .

Now we need to understand the relationship between the sequence {Y_{k,m,l}} and the sequence {X_{k,m,l}} as l goes to infinity.

Lemma 26. For k ≥ 2, m ≥ 2,

lim_{l→∞} \frac{Y_{k,m,l}}{X_{k,m,l}} = H_{m}.

Proof. When k = 2 we have

lim_{l→∞} \frac{Y_{2,m,l}}{X_{2,m,l}} = lim_{l→∞} \frac{c_{m,l}X_{1,m,l} + d_{m,l}Y_{1,m,l}}{a_{m,l}X_{1,m,l} + b_{m,l}Y_{1,m,l}}

= lim_{l→∞} \frac{(\frac{c_{m,l}}{a_{m,l}} ) X_{1,m,l} + (\frac{d_{m,l}}{a_{m,l}} ) Y_{1,m,l}}{X_{1,m,l} + (\frac{b_{m,l}}{a_{m,l}} ) Y_{1,m,l}}

= \frac{(H_{m}) L_{2m} + (φH_{m}) F_{2m+2}}{L_{2m} + φF_{2m+2}}

= H_{m}.

So the lemma is true for k = 2. We proceed by induction and assume the lemma is true for some k ≥ 2. Then (1) shows

lim_{l→∞} \frac{Y_{k+1,m,l+1}}{X_{k+1,m,l+1}} = lim_{l→∞} \frac{c_{m,l}X_{k,m,l} + d_{m,l}Y_{k,m,l}}{a_{m,l}X_{k,m,l} + b_{m,l}Y_{k,m,l}}

= lim_{l→∞} \frac{(\frac{c_{m,l}}{a_{m,l}} ) + (\frac{d_{m,l}}{a_{m,l}} ) (\frac{Y_{k,m,l}}{X_{k,m,l}} )}{1 + (\frac{b_{m,l}}{a_{m,l}} ) (\frac{Y_{k,m,l}}{X_{k,m,l}} )}

= \frac{(H_{m}) + (φH_{m}) (H_{m})}{1 + (φ) (H_{m})}

= H_{m}.

Now we determine the asymptotic behavior of the polygonal chain sequences if we allow l to vary.

Theorem 27. For k ≥ 2 and m ≥ 2,

lim_{l→∞} \frac{X_{k,m,l+1}}{X_{k,m,l}} = φ^{k−1} and lim_{l→∞} \frac{Y_{k,m,l+1}}{X_{k,m,l}} = φ^{k−1} (H_{m}) .

Proof. The proof will be by induction on k. Recall that X_{1,m,l} = L_{2m} and Y_{1,m,l} = F_{2m+2} We first verify the k = 2 case. Equation (1) shows

lim_{l→∞} \frac{X_{2,m,l+1}}{X_{2,m,l}} = lim_{l→∞} \frac{a_{m,l+1}X_{1,m,l+1} + b_{m,l+1}Y_{1,m,l+1}}{a_{m,l}X_{1,m,l} + b_{m,l}Y_{1,m,l}}

= lim_{l→∞} \frac{(\frac{a_{m,l+1}}{a_{m,l}} ) X_{1,m,l+1} + (\frac{b_{m,l+1}}{a_{m,l}} ) Y_{1,m,l+1}}{X_{1,m,l} + (\frac{b_{m,l}}{a_{m,l}} ) Y_{1,m,l}}

= \frac{φL_{2m} + φ^{2}F_{2m+2}}{L_{2m} + φF_{2m+2}}

= φ and

lim_{l→∞} \frac{Y_{2,m,l+1}}{X_{2,m,l}} = lim_{l→∞} \frac{c_{m,l+1}X_{1,m,l+1} + d_{m,l+1}Y_{1,m,l+1}}{a_{m,l}X_{1,m,l} + b_{m,l}Y_{1,m,l}}

= lim_{l→∞} \frac{(\frac{c_{m,l+1}}{a_{m,l}} ) X_{1,m,l+1} + (\frac{d_{m,l+1}}{a_{m,l}} ) Y_{1,m,l+1}}{X_{1,m,l} + (\frac{b_{m,l}}{a_{m,l}} ) Y_{1,m,l}}

= \frac{(φ) (H_{m}) L_{2m} + (φ^{2}H_{m}) F_{2m+2}}{L_{2m} + φF_{2m+2}}

= φH_{m}.

Now the general cases:

lim_{l→∞} \frac{X_{k+1,m,l+1}}{X_{k+1,m,l}} = lim_{l→∞} \frac{a_{m,l+1}X_{k,m,l+1} + b_{m,l+1}Y_{k,m,l+1}}{a_{m,l}X_{k,m,l} + b_{m,l}Y_{k,m,l}}

= lim_{l→∞} \frac{(\frac{a_{m,l+1}}{a_{m,l}} ) (\frac{X_{k,m,l+1}}{X_{k,m,l}} ) + (\frac{b_{m,l+1}}{a_{m,l}} ) (\frac{Y_{k,m,l+1}}{X_{k,m,l}} )}{1 + (\frac{b_{m,l}}{a_{m,l}} ) (\frac{Y_{k,m,l}}{X_{k,m,l}} )}

= \frac{(φ) (φ^{k−1}) + (φ^{2}) (φ^{k−1}H_{m})}{1 + (φ) (H_{m})}

= φ^{k}

and

lim_{l→∞} \frac{Y_{k+1,m,l+1}}{X_{k+1,m,l}} = lim_{l→∞} \frac{c_{m,l+1}X_{k,m,l+1} + d_{m,l+1}Y_{k,m,l+1}}{a_{m,l}X_{k,m,l} + b_{m,l}Y_{k,m,l}}

= lim_{l→∞} \frac{(\frac{c_{m,l+1}}{a_{m,l}} ) (\frac{X_{k,m,l+1}}{X_{k,m,l}} ) + (\frac{d_{m,l+1}}{a_{m,l}} ) (\frac{Y_{k,m,l+1}}{X_{k,m,l}} )}{1 + (\frac{b_{m,l}}{a_{m,l}} ) (\frac{Y_{k,m,l}}{X_{k,m,l}} )}

= \frac{(φH_{m}) (φ^{k−1}) + (φ^{2}H_{m}) (φ^{k−1}H_{m})}{1 + (φ) (H_{m})}

= φ^{k}H_{m}.

So the sequence of polygonal chain numbers as l varies for fixed k and m behaves asymptotically as the exponential sequence with ratio φ^{k−1}. For example, φ ≈ 1.618033988 and φ^{2} ≈ 2.618033986 (compare to the ratios in Table 2). Note that the limits in these cases are independent of the value of m.

10 Conclusion

The asymptotic growth rates of polygonal chain sequences are functions of the golden ratio φ. Since polygonal chains are constructed from string and polygonal configurations and

lim_{l→∞} \frac{#(S_{l+1})}{#(S_{l})} = φ and lim_{m→∞} \frac{#(P_{m+1})}{#(P_{m})} = φ^{2}, this should not be surprising in hindsight.

That the asymptotic ratios of the polygonal chain sequences have such nice closed forms is, however, somewhat surprising given the complex nature of betweenness in this geometry.

Polygonal chain sequences provide a three parameter family of integer sequences previously unidentified in The On-Line Encyclopedia of Integer Sequences [10]. These sequences have interesting geometric interpretations as the number of compact sets at each location between the component sets that make up the polygonal chain. We suspect that there are many other similar families of unknown sequences just waiting to be found.

11 Acknowledgements

This work was supported by National Science Foundation grant DMS-0451254. The authors also thank Grand Valley State University for hosting and supporting a Research Experiences for Undergraduates program.

References

[1] M. Barnsley, Fractals Everywhere, Second Edition, Academic Press Professional, 1998.

[2] C. Bay, A. Lembcke, and S. Schlicker, When lines go bad in hyperspace, Demonstratio Math., 38 (2005), 689–701.

[3] A. T. Benjamin and J. J. Quinn, Proofs That Really Count, Mathematical Association of America, 2003.

[4] C. Blackburn, K. Lund, S. Schlicker, P. Sigmon, and A. Zupan, A missing prime configuration in the Hausdorff metric geometry, to appear, J. Geom.

[5] L. M. Blumenthal, Theory and Applications of Distance Geometry, Oxford University Press, 1953.

[6] D. Braun, J. Mayberry, A. Powers, and S. Schlicker, A singular introduction to the Hausdorff metric geometry, Pi Mu Epsilon J., 12 No. 3, (2005), 129–138.

[7] T. Koshy, Fibonacci and Luca Numbers with Applications, John Wiley & Sons, 2001.

[8] E. Lucas, Théorie des fonctions numériques simplement périodiques, Amer. J. Math. 1 (1878), 184–240, 289–321.

[9] K. Lund, P. Sigmon, and S. Schlicker, Fibonacci sequences in the space of compact sets, Involve, 1 No. 2 (2008), 197–215.

[10] N. J. A. Sloane, (2007), The On-Line Encyclopedia of Integer Sequences, published

   electronically at http://www.research.att.com/~njas/sequences/

2000 Mathematics Subject Classification: Primary 51F99; Secondary 11B83. Keywords: Hausdorff metric, configuration, metric geometry, polygonal chains, Fibonacci numbers, Lucas numbers.

(Concerned with sequences \underline{A000032}, \underline{A000045}, \underline{A152927}, \underline{A152928}, \underline{A152929}, \underline{A152930}, \underline{A152931}, and \underline{A152932}.)

Received August 22 2008; revised version received December 22 2008. Published in Journal of Integer Sequences, December 22 2008.

Return to Journal of Integer Sequences home page.