A Restricted Random Walk defined via a Fibonacci Process

Martin Griffiths School of Education University of Manchester Manchester M13 9PL United Kingdom

               martin.griffiths@manchester.ac.uk

Abstract In this article we study a random walk on a particularly simple graph. This walk is determined by a probabilistic process associated with the Fibonacci sequence. Exact formulas are derived for the expected proportions of time spent on each arc of the graph for a walk of length n, giving rise to sequences that do not appear in Sloane’s On-Line Encyclopedia of Integer Sequences. We also obtain asymptotic relations for these expected proportions.

1 Introduction

A one-dimensional random walk on the integers ℤ might typically be regarded as a process defined by a sequence of random variables {U_{n}}, the nth term of which is given by

U_{n} = U_{0} + ∑_{k=1}^{n} V_{k},

where U_{0} ∈ ℤ is the starting position and {V_{n}} is a sequence of independent random variables, each term of which takes only values in {1, −1}. If the terms in {V_{n}} are also identically distributed, so that P (V_{k} = 1) = p and P (V_{k} = −1) = 1 − p for each k ∈ ℕ, where p is a fixed number satisfying 0 < p < 1, then {U_{n}} is termed a simple random walk. The mathematics of simple random walks on ℤ has been studied extensively, and further details are to be found in [3, 6].

It is also possible to consider one-dimensional random walks having either absorbing or retaining barriers. An example of the former is known as ‘gamblers ruin’; see [6]. In this case the random walk would start at a point m, where 0 < m < N for some N ≥ 2, and at each stage the outcome of tossing a fair coin would decide whether the walk proceeded to the left or to the right. The walk would terminate if it reached either 0 or N. If, on the other hand, the random walk has retaining barriers, then instead of stopping once 0 or N is reached, the next point on the walk would be 1 or N − 1, respectively (the barriers might thus also be thought of as ‘reflecting’ in this case). Note that those having either absorbing or retaining barriers might be regarded as restricted random walks. Furthermore, other than at the barriers, these behave as simple random walks.

The particular random walks we consider here have retaining barriers but are not, in the sense described in the opening paragraph, simple. As opposed to the act of tossing a fair coin at each stage, the walks are determined by a probabilistic process associated with the Fibonacci sequence in which the probabilities do not remain constant. The reason for this will become apparent in due course. Also, since we are interested in the paths generated by the walks, we consider them to take place on a graph.

Consider the graph below, which we denote by G. A walk 𝔚 of length n on G comprises an ordered sequence of n + 1 adjacent nodes, starting at node 1. The ordered sequence of n arcs traversed whilst undertaking 𝔚 is called a path in G of length n. To take an example, the walk (1, 2, 3, 2, 3, 4, 3, 2, 1, 2) gives rise to the path ABBBCCBAA of length 9.

[figure: 1; A; 2; B; 3; C; 4]

Since the Fibonacci numbers play a major role in our work here, before describing how they are used to generate random walks on G we provide a definition of the Fibonacci sequence.

Definition 1. The nth term of the Fibonacci sequence F_{n} is defined by the recurrence relation F_{n} = F_{n−1} + F_{n−2}, n ∈ ℕ, where F_{−1} = 1 and F_{0} = 0; note that we index the Fibonacci numbers here from −1 simply out of mathematical convenience (the need for this will become apparent in later sections of this paper). The sequence {F_{n}} appears in Sloane’s On-Line Encyclopedia of Integer Sequences as \underline{A000045} [8]. For further details regarding the Fibonacci numbers, see [1, 2, 7].

We start the random walk at node 1 with F_{n+1} green discs, and carry them with us to node 2. Once at node 2, F_{n−1} of these discs are painted red. A disc is then chosen at random. If the disc is red we proceed to node 1, carrying the F_{n−1} red discs with us. Otherwise, we take the F_{n+1} − F_{n−1} = F_{n} green discs with us to node 3. In the former case we continue simply by carrying the F_{n−1} red discs to node 2, while in the latter case we paint F_{n−2} of the green discs red, and choose one of the discs at random. If the disc is green we proceed to node 2 but if it is red we go to node 4. This process continues until a path of length n has been achieved, and may be formalized as follows:

(i) If at node 1 or node 4 then carry the discs to the next node.

(ii) If at node 2(3) with F_{k} green discs then paint F_{k−2} of them red and choose one at random. If the disc is green then take the F_{k−1} green discs to node 3(2). Otherwise, take the F_{k−2} red discs to node 1(4).

(iii) If at node 2(3) with F_{k} red discs then paint F_{k−1} of them green and choose one at random. If the disc is green then take the F_{k−1} green discs to node 3(2). Otherwise, take the F_{k−2} red discs to node 1(4).

(iv) The process stops once the path length has reached n.

We see, in Figure 1, the probability tree that results on considering this process for the case n = 4.

[figure: 1; 2; 1; 3; 2; 2; 4; 1; 3; 1; 3; 3; \frac{5}{5}; \frac{2}{5}; \frac{3}{5}; \frac{2}{2}; \frac{2}{3}; \frac{1}{3}; \frac{1}{2}; \frac{1}{2}; \frac{1}{2}; \frac{1}{2}; \frac{1}{1}]

Figure 1: A probability tree for the case n = 4.

The aim of this paper is to determine, for any given n ∈ ℕ, the expected proportions of time spent on each of the three arcs during a random walk of length n on G, where it is to be assumed that the time taken to get from one node to the next remains constant during the walk. The scenario considered here is related to one given in [5], although the resulting mathematics turns out to be considerably more complicated. Furthermore, no probabilistic aspects were taken account of in [5].

Before obtaining several useful results in connection with our problem, we define some notation that will be used in due course. Let S(n) be the set of all possible paths in G of length n. Suppose all the elements of S(n) are placed in lexicographical order. Then P_{j}(n) represents the jth path, 1 ≤ j ≤ |S(n)|, under this ordering. We use M_{n} to denote the |S(n)| × n matrix, the element m_{i,j}(n) of which is defined to be the jth letter of P_{i}(n). Two examples, M_{5} and M_{6}, are shown in Table 1. In addition, we use r_{j}(n) and c_{k}(n) to refer to the jth row and kth column of M_{n}, respectively.

M_{5} = ( \begin{matrix}A & A & A & A & A \\ A & A & A & B & B \\ A & A & A & B & C \\ A & B & B & A & A \\ A & B & B & B & B \\ A & B & B & B & C \\ A & B & C & C & B \\ A & B & C & C & C \end{matrix} ) , M_{6} = ( \begin{matrix}A & A & A & A & A & A \\ A & A & A & A & A & B \\ A & A & A & B & B & A \\ A & A & A & B & B & B \\ A & A & A & B & C & C \\ A & B & B & A & A & A \\ A & B & B & A & A & B \\ A & B & B & B & B & A \\ A & B & B & B & B & B \\ A & B & B & B & C & C \\ A & B & C & C & B & A \\ A & B & C & C & B & B \\ A & B & C & C & C & C \end{matrix} ) .

Table 1: The matrices M_{5} and M_{6}.

2 Some structural results concerning M_{n}

Definition 2. Let P be a path in G having length n and ending in A. If P arises from the walk 𝔚 then s(A, n) denotes the set of arcs emanating from the final node of 𝔚. We term s(A, n) the successor set of P since it provides us with information on how P may be extended by one arc. Corresponding definitions follow for paths ending in B and C, respectively.

Note that s(A, n), s(B, n) and s(C, n) are each well-defined since n will always be even if 𝔚 finishes at node 1 or node 3, but odd if 𝔚 finishes at node 2 or node 4. It is in fact clear that s(A, 2k − 1) = {a, b}, s(A, 2k) = {a}, s(B, 2k − 1) = {a, b}, s(B, 2k) = {b, c}, s(C, 2k − 1) = {c} and s(C, 2k) = {b, c}.

As was alluded to earlier, it transpires that the Fibonacci numbers feature strongly in both the structural and combinatorial aspects of M_{n}. In connection with this, it is, as we shall see, judicious to consider particular sections of the columns of M_{n}, defined as follows:

Definition 3. A block of As of length q ≥ 1 in the kth column of M_{n} is defined to be a series of entries such that m_{p,k}(n) = m_{p+1,k}(n) = … = m_{p+q−1,k}(n) = A for some p, q ∈ ℕ such that either p = 1 or m_{p−1,k}(n) ≠ A and either p + q − 1 = |S(n)| or m_{p+q,k}(n) ≠ A. Corresponding definitions apply for blocks consisting of Bs and Cs.

In the lemma below it is shown that for each block in M_{n} the corresponding series of entries in c_{n}(n) consist of singleton blocks of As, Bs and Cs. The following definition eases the notation somewhat in this regard.

Definition 4. For any block X in M_{n}, X [p, q, r] denotes that the corresponding section of c_{n}(n) comprises p, q and r singleton blocks of As, Bs and Cs respectively.

Lemma 5. For any k with 1 ≤ k ≤ n there are F_{k+1} blocks in c_{k}(n). The length of any block Y of Bs is of the form F_{j}, j ≥ 2. If n is odd then Y [F_{j−3}, F_{j−2}, F_{j−2}], while if n is even then Y [F_{j−2}, F_{j−2}, F_{j−3}].

If n is odd then the length of any block X of As is of the form F_{2j}, j ≥ 1. In this case X [F_{2j−3}, F_{2j−2}, F_{2j−2}]. On the other hand, if n is even then the length of any block X of As is of the form F_{2j−1}, j ≥ 2, and X [F_{2j−3}, F_{2j−3}, F_{2j−4}] so long as X is not in c_{n}(n). If X is in c_{n}(n) then X[1, 0, 0].

Finally, if n is odd then the length of any block Z of Cs is of the form F_{2j−1}, j ≥ 2, and Z [F_{2j−4}, F_{2j−3}, F_{2j−3}] so long as X is not in c_{n}(n). If Z is in c_{n}(n) then Z[0, 0, 1]. If n is even then the length of any block Z of Cs is of the form F_{2j}, j ≥ 1, and Z [F_{2j−2}, F_{2j−2}, F_{2j−3}].

Proof. Let T (n) denote the statement of the lemma. We proceed by induction on n. It is easily checked that both T (1) and T (2) are true. Now assume that T (n) is true for some n ≥ 2. Let us consider a particular block X of As in c_{k}(n) for some k such that 1 ≤ k ≤ n. Suppose first that n is odd. By the inductive hypothesis X has length F_{2j} for some j ∈ ℕ, and X [F_{2j−3}, F_{2j−2}, F_{2j−2}]. It is clear, on considering both the lexicographical ordering and the successor sets when n is odd, that X gives rise to a corresponding block W in c_{k}(n + 1) of length F_{2j} + F_{2j−3} + F_{2j−2} = F_{2j+1}; the number of blocks in c_{k}(n + 1) is therefore F_{k+1}, the same number as in c_{k}(n). Furthermore, the section corresponding to W in c_{n+1}(n + 1) comprises F_{2j−3} + F_{2j−2} = F_{2j−1} singleton blocks of As, F_{2j−3} + F_{2j−2} = F_{2j−1} singleton blocks of Bs and F_{2j−2} singleton blocks of Cs.

Suppose now that n is even. Using the inductive hypothesis once more, X has length F_{2j−1} for some j ∈ ℕ, and X [F_{2j−3}, F_{2j−3}, F_{2j−4}] unless X is in c_{n}(n). If X is not in c_{n}(n) then, by considering both the lexicographical ordering and the successor sets when n is even, we see that X gives rise to a corresponding block W in c_{k}(n+1) of length F_{2j−1}+F_{2j−3}+F_{2j−4} = F_{2j}. Also, the section corresponding to W in c_{n+1}(n + 1) comprises F_{2j−3} singleton blocks of As, F_{2j−3} + F_{2j−4} = F_{2j−2} singleton blocks of Bs and F_{2j−3} + F_{2j−4} = F_{2j−2} singleton blocks of Cs. If, on the other hand, X is in c_{n}(n) then X[1, 0, 0]. Note that, since n is even, X gives rise to a corresponding block W in c_{n+1}(n + 1) consisting simply of one A. As a block in M_{n+1} this may be written as W [F_{−1}, F_{0}, F_{0}], which is equal to W [F_{2j−3}, F_{2j−2}, F_{2j−2}] for j = 1.

By continuing in this manner for all the remaining cases, the proof of the lemma follows by the principle of mathematical induction.

Corollary 6.

|S(n)| = F_{n+1}.

Proof. First, it is clear that c_{1}(n) comprises simply a block of As. Thus, from Lemma 5, we know that c_{n}(n) consists solely of singletons. However, Lemma 5 also tells us that there are F_{n+1} blocks in c_{n}(n), thereby proving the corollary.

Lemma 7. In c_{k}(n), 1 ≤ k ≤ n, there are

(i) F_{2⌊\frac{k}{2}⌋−1} blocks of A of length F_{n+1−2⌊\frac{k}{2}⌋} for k ≥ 1,

(ii) F_{k−1} blocks of B of length F_{n+2−k} for k ≥ 2, (iii) F_{2⌊\frac{k−1}{2}⌋} blocks of C of length F_{n−2⌊\frac{k−1}{2}⌋} for k ≥ 3,

where ⌊x⌋ is the floor function, denoting the largest integer not exceeding x.

Proof. Each of these results may be proved by induction on n. First, it is a straightforward matter to show that (i) is true when n = 1. Now assume that this result is true for all k such that 1 ≤ k ≤ n for some n ≥ 1. Let us consider M_{n+1}. We know, from Lemma 5, that the number of blocks of A in c_{k}(n+1) is, for any fixed k with 1 ≤ k ≤ n, the same as the number of blocks of A in c_{k}(n). Lemma 5 also tells us that any block of As of length F_{m} in c_{k}(n) has a corresponding block of length F_{m+1} in c_{k}(n + 1). It just remains therefore to show that (i) is true for c_{n+1}(n + 1). Suppose that n + 1 is odd. We know both that c_{n+1}(n + 1) consists solely of singletons and that, taking X as c_{1}(n + 1), X [F_{2j−3}, F_{2j−2}, F_{2j−2}] for some j ∈ ℕ. Since c_{n+1}(n + 1) has F_{n+2} singletons, the number of blocks of A in c_{n+1}(n + 1) must be F_{n−1}. When n + 1 is odd then

2 ⌊\frac{n + 1}{2}⌋ = n,

in which case, with k = n + 1,

F_{2⌊\frac{k}{2}⌋−1} = F_{n−1}

and

F_{(n+1)+1−2⌊\frac{k}{2}⌋} = F_{2} = 1,

thereby showing that (i) is true in this case. The argument for when n + 1 is even proceeds in a similar manner. It is possible also to show, adopting the above approach, that both (ii) and (iii) are true.

3 Exact formulas

We utilize here results from Section 2 in order to determine, for any given n ∈ ℕ, the expected proportions of time spent on each of the three arcs during a random walk of length n on G. Before doing so, however, let us consider what might be regarded as the most obvious way to define a random walk on G. Note first that when at node 1 we are forced next to visit node 2. Similarly, when at node 4 then 3 is necessarily the next node in the walk. Suppose, however, that when we are at node 2 or node 3, the next node to be visited is decided by the outcome of tossing a fair coin. Thus, with P(2 → 1) denoting the probability that the next node will be 1 given that we are currently at node 2, it is the case that P(2 → 1) = \frac{1}{2}. In fact, on extending this notation in an obvious way, we have

P(2 → 1) = P(2 → 3) = P(3 → 2) = P(3 → 4) = \frac{1}{2}.

Thus, other than at the barriers, this might be regarded as a simple random walk. An important point to make here with respect to this scenario is that, for a particular choice of n, it is not necessarily the case that all paths of length n are equally likely. When n = 3, for example,

P(AAA) = P(1 → 2)P(2 → 1)P(1 → 2) = 1 × \frac{1}{2} × 1 = \frac{1}{2},

while

P(ABB) = P(1 → 2)P(2 → 3)P(3 → 2) = 1 × \frac{1}{2} × \frac{1}{2} = \frac{1}{4}.

This means, in general, that the proportion of As in M_{n} does not give the expected proportion of time spent on As during a random walk of length n, and similarly for Bs and Cs.

However, for the Fibonacci process described in Section 1 it is in fact true that all possible paths of length n are equally likely, and we have

P (P_{j}(n)) = \frac{1}{F_{n+1}}

for each j with 1 ≤ j ≤ F_{n+1}. To see that this is indeed true, we may consider the resulting probability tree for some fixed value of n. Choose any set of n branches that form a connected path through the tree. From the way that the tree is constructed, it follows that the product of the probabilities on the leftmost k branches is, for k ≥ 2, given by

\frac{F_{n+1−k}}{F_{n+1}}  or  \frac{F_{n+2−k}}{F_{n+1}} .

This means that in order to obtain the expected proportions of time spent on each of the three arcs during a random walk of length n on G, it remains to calculate the number of As, Bs and Cs in M_{n}.

Definition 8. We use N_{n}(A), N_{n}(B) and N_{n}(C) to denote the multiplicities of As, Bs and Cs in M_{n}, respectively. Furthermore, let N_{n} = N_{n}(A) + N_{n}(B) + N_{n}(C), the total number of entries in M_{n}. Corollary 6 implies that N_{n} = nF_{n+1}. The sequence {nF_{n+1}} appears in [8] as \underline{A023607}.

Theorem 9.

N_{n}(B) = \frac{1}{5} (nF_{n+1} + (2n − 3)F_{n}) .

Proof. From Lemma 7, we know that

N_{n}(B) = ∑_{k=2}^{n} F_{k−1}F_{n+2−k}

= ∑_{k=0}^{n+1} F_{k}F_{n+1−k} − F_{n}.

The sum on the right is the well-known Fibonacci convolution, which, using a result from [4, 7], gives

N_{n}(B) = \frac{1}{5} (nF_{n+1} + 2(n + 1)F_{n}) − F_{n}

= \frac{1}{5} (nF_{n+1} + (2n − 3)F_{n}) .

Theorem 10.

N_{n}(A) = \frac{1}{5} ((n + 4)F_{n} + 2nF_{n−1} + 5F_{2⌊\frac{n}{2}⌋}) .

Proof. By Lemma 7 the total number of As in M_{n} is given by

∑_{k=1}^{n} F_{2⌊\frac{k}{2}⌋−1}F_{n+1−2⌊\frac{k}{2}⌋}.  (1)

For even n this may be written as

F_{−1}F_{n+1} + 2F_{1}F_{n−1}+2F_{3}F_{n−3} + … + 2F_{n−3}F_{3} + F_{n−1}F_{1}

= F_{n+1} + 2 (F_{1}F_{n−1} + F_{3}F_{n−3} + … + F_{n−1}F_{1}) − F_{n−1}

= F_{n} + 2 (F_{1}F_{n−1} + F_{3}F_{n−3} + … + F_{n−1}F_{1}) .  (2)

We now calculate the generating function U_{even}(x) for the sum

F_{1}F_{n−1} + F_{3}F_{n−3} + … + F_{n−1}F_{1},

which might be regarded as a ‘stretched’ convolution.

First, let G(x) be the ordinary generating function for the Fibonacci numbers. Then from [7] we know that

G(x) = F_{1}x + F_{2}x^{2} + F_{3}x^{3} + …

= \frac{x}{1 − x − x^{2}}

= \frac{1}{\sqrt{5}} (\frac{1}{1 − ϕx} − \frac{1}{1 − ϕ̂x}) ,

where

ϕ = \frac{1 + \sqrt{5}}{2} and ϕ̂ = \frac{1 − \sqrt{5}}{2}.

Now, noting that

F_{1}x + F_{3}x^{3} + F_{5}x^{5} + … = \frac{1}{2} (G(x) − G(−x))

= \frac{1}{2\sqrt{5}} (\frac{1}{1 − ϕx} − \frac{1}{1 − ϕ̂x}) − \frac{1}{2\sqrt{5}} (\frac{1}{1 + ϕx} − \frac{1}{1 + ϕ̂x})

= \frac{x}{\sqrt{5}} (\frac{ϕ}{1 − ϕ^{2}x^{2}} − \frac{ϕ̂}{1 − ϕ̂^{2}x^{2}} ) ,

we see that

U_{even}(x) = (F_{1} + F_{3}x + F_{5}x^{2} + …)^{2}
= \frac{1}{5} (\frac{ϕ}{1 − ϕ^{2}x} − \frac{ϕ̂}{1 − ϕ̂^{2}x})^{2} .  (3)

The right-hand side of (3) is multiplied out and then, employing the method of partial fractions, written as

U_{even}(x) = \frac{1}{5} [(\frac{ϕ}{1 − ϕ^{2}x})^{2} + (\frac{ϕ̂}{1 − ϕ̂^{2}x})^{2}] + \frac{2}{5\sqrt{5}} [\frac{ϕ^{2}}{1 − ϕ^{2}x} − \frac{ϕ̂^{2}}{1 − ϕ̂^{2}x}] .  (4)

This may be expanded as a power series in x. Subsequently, on comparing coefficients on both sides of (4) and using the well-known results

F_{n} = \frac{1}{\sqrt{5}} (ϕ^{n} − ϕ̂^{n}) and F_{n} + 2F_{n−1} = ϕ^{n} + ϕ̂^{n},

which may be found in [1, 7], it can be shown that

F_{1}F_{n−1} + F_{3}F_{n−3} + … + F_{n−1}F_{1} = \frac{1}{10} (4(n + 2)F_{n−2} + (3n + 4)F_{n−3}) .

Then, on setting n = 2m and using (2), we obtain

N_{2m}(A) = \frac{1}{5} ((2m + 9)F_{2m} + 4mF_{2m−1}) .  (5)

For odd n we can write (1) as

F_{−1}F_{n+1} + 2F_{1}F_{n−1}+2F_{3}F_{n−3} + … + 2F_{n−2}F_{2}
= F_{n+1} + 2 (F_{1}F_{n−1} + F_{3}F_{n−3} + … + F_{n−2}F_{2})

and then calculate the generating function

U_{odd}(x) = (F_{1} + F_{3}x + F_{5}x^{2} + …) (F_{0} + F_{2}x + F_{4}x^{2} + …)

for the sum

F_{1}F_{n−1} + F_{3}F_{n−3} + … + F_{n−2}F_{2},

which is another ‘stretched’ convolution. This leads, on using the result

F_{0} + F_{2}x^{2} + F_{4}x^{4} + … = \frac{1}{2} (G(x) + G(−x)) ,

to

N_{2m−1}(A) = \frac{1}{5} ((4m + 3)F_{2m} − 2mF_{2m−1}) ,

which can be rearranged to give

N_{2m−1}(A) = \frac{1}{5} (((2m − 1) + 4)F_{2m−1} + (2(2m − 1) + 5)F_{(2m−1)−1}) .  (6)

From (5) and (6) we see that

N_{n}(A) = \frac{1}{5} ((n + 9)F_{n} + 2nF_{n−1}) .

and

N_{n}(A) = \frac{1}{5} ((n + 4)F_{n} + (2n + 5)F_{n−1})

for n even and odd, respectively, thereby completing the proof of the theorem.

Now, since N_{n} = N_{n}(A)+N_{n}(B)+N_{n}(C) = nF_{n+1}, we may easily obtain, using Theorems 9 and 10, the results

N_{2m−1}(C) = \frac{1}{5} (((2m − 1) − 1)F_{2m−1} − (2(2m − 1) − 5)F_{(2m−1)−1})

and

N_{2m}(C) = \frac{1}{5} ((2m − 6)F_{2m} + 4mF_{2m−1}) .

From this it may be seen that

N_{n}(C) = \frac{1}{5} ((n − 1)F_{n} + 2nF_{n−1} − 5F_{2⌊\frac{n}{2}⌋}) .

Thus, for a path of length n, exact formulas for the expected proportions of time spent traveling along arcs A, B and C are given by

\frac{(n + 4)F_{n} + 2nF_{n−1} + 5F_{2⌊\frac{n}{2}⌋}}{5nF_{n+1}} ,

\frac{nF_{n+1} + (2n − 3)F_{n}}{5nF_{n+1}}

and

\frac{(n − 1)F_{n} + 2nF_{n−1} − 5F_{2⌊\frac{n}{2}⌋}}{5nF_{n+1}} ,

respectively. We note that neither {N_{n}(A)} nor {N_{n}(C)} appears in [8]. However, {N_{n}(B)} is to be found there as \underline{A023610}, a Fibonacci convolution.

4 Asymptotic results

Using the fact that F_{n} is equal to the nearest integer to ϕ^{n}/\sqrt{5} (see [7]), we have

N_{n}(A) = \frac{1}{5} ((n + 4)F_{n} + 2nF_{n−1} + 5F_{2⌊\frac{n}{2}⌋})

∼ \frac{1}{5} (\frac{nϕ^{n}}{\sqrt{5}} + \frac{2nϕ^{n−1}}{\sqrt{5}} )

= \frac{nϕ^{n−1}}{5\sqrt{5}} (ϕ + 2) .

Likewise, it is straightforward to show that

N_{n}(B) ∼ \frac{nϕ^{n}}{5\sqrt{5}} (ϕ + 2) and N_{n}(C) ∼ \frac{nϕ^{n−1}}{5\sqrt{5}} (ϕ + 2) .

Therefore

lim_{n→∞} \frac{N_{n}(A)}{N_{n}(B)} = lim_{n→∞} \frac{N_{n}(C)}{N_{n}(B)} = \frac{1}{ϕ} = ϕ − 1,

from which we see that

lim_{n→∞} \frac{N_{n}(B)}{N_{n}} = \frac{1}{2ϕ − 1}

and

lim_{n→∞} \frac{N_{n}(A)}{N_{n}} = lim_{n→∞} \frac{N_{n}(C)}{N_{n}} = \frac{ϕ − 1}{2ϕ − 1} = \frac{1}{ϕ + 2}.

References

[1] D. M. Burton. Elementary Number Theory. McGraw-Hill, 1998.

[2] P. J. Cameron. Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, 1994.

[3] W. Feller. An Introduction to Probability Theory and its Applications Volume 1. Wiley, 1968.

[4] R. L. Graham, D. E. Knuth and O. Patashnik. Concrete Mathematics. Addison-Wesley, 1990.

[5] M. Griffiths. Learning Russian. Mathematical Gazette, 92 (2008), 551–555.

[6] G. Grimmett and D. Stirzaker. Probability and Random Processes. Oxford University Press, 2001.

[7] D. E. Knuth, D. E. The Art of Computer Programming Volume 1. Addison-Wesley, 1968.

[8] N. Sloane, The On-Line Encyclopedia of Integer Sequences, 2010.

    http://www.research.att.com/^{∼}njas/sequences

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A16, 05C81, 11B39. Keywords: Random walks, Fibonacci numbers, generating functions, probabilities.

(Concerned with sequences \underline{A000045}, \underline{A023607}, and \underline{A023610}.)

Received October 10 2010; revised version received April 24 2011. Published in Journal of Integer Sequences, May 2 2011.

Return to Journal of Integer Sequences home page.