Problem:
For a positive integer n≥3 plot n equally spaced points around a circle. Label one of them A, and place a marker at A. One may move the marker forward in a clockwise direction to either the next point or the point after that. Hence there are a total of 2n distinct moves available; two from each point. Let an​ count the number the number of ways to advance around the circle exactly twice, beginning and ending at A, without repeating a move. Prove that an−1​+an​=2n for all n≥4.
Solution:
First Solution. We will show that an​=31​(2n+1+(−1)n). This would be sufficient, since then we would have
an−1​+an​=31​(2n+(−1)n−1)+31​(2n+1+(−1)n)=31​(2n+2⋅2n)=2n
We will need the fact that for all positive integers n
k=0∑⌊n/2⌋​(kn−k​)2k=31​(2n+1+(−1)n)
This may be established by strong induction. To begin, the cases n=1 and n=2 are quickly verified. Now suppose that n≥3 is odd, say n=2m+1. We find that
k=0∑m​(k2m+1−k​)2k​=1+k=1∑m​(k2m−k​)2k+k=1∑m​(k−12m−k​)2k=k=0∑m​(k2m−k​)2k+2k=0∑m−1​(k2m−1−k​)2k=31​(22m+1+1)+32​(22m−1)=31​(22m+2−1)​
using the induction hypothesis for n=2m and n=2m−1. For even n the computation is similar, so we omit the steps. This proves the claim.
We now determine the number of ways to advance around the circle twice, organizing our count according to the points visited both times around the circle. It is straight-forward to check that no two such points may be adjacent, and that there are exactly two sequences of moves leading from any such point to the next. (These sequences involve only moves of length two except possibly at the endpoints.) Hence given k≥1 points around the circle, no two adjacent and not including point A, there would appear to be 2k ways to traverse the circle twice without repeating a move. However, half of these options lead to repeating the same route twice, giving 2k−1 ways in actuality. There are (kn−k​) ways to select k nonadjacent points on the circle not including A (add an extra point behind each of k chosen points), for a total contribution of
k=1∑⌊n/2⌋​(kn−k​)2k−1=21​⎣⎢⎡​−1+k=0∑⌊n/2⌋​(kn−k​)2k⎦⎥⎤​=61​(2n+1+(−1)n)−21​
On the other hand, if the k≥1 nonadjacent points do include point A then there are (k−1n−k−1​) ways to choose them around the circle. (Select A but not the next point, then add an extra point after each of k−1 selected points.) But now there are actually 2k ways to circle twice, since we can choose either move at A and the subsequent points, then select the other options the second time around. Hence the contribution in this case is
k=1∑⌊n/2⌋​(k−1n−k−1​)2k=2k=0∑⌊(n−2)/2⌋​(kn−2−k​)2k=32​(2n−1+(−1)n)
Finally, if n is odd then there is one additional way to circle in which no point is visited twice by using only steps of length two, giving a contribution of 21​(1−(−1)n). Therefore the total number of paths is
61​(2n+1+(−1)n)−21​+32​(2n−1+(−1)n)+21​(1−(−1)n)
which simplifies to 31​(2n+1+(−1)n), as desired.
This problem and solution were suggested by Sam Vandervelde.
Second Solution: We give a bijective proof of the identity
an​=an−1​+2an−2​
which immediately implies that an​+an−1​=2(an−1​+an−2​). Since trivially a0​=a1​=1 (or alternatively a1​=1,a2​=3 ), the desired identity will then follow by induction on n.
To construct the bijection, it is convenient to introduce some alternate representations for the sequences we are counting. Label the points P0​,…,Pn−1​ in order, and define Pi+n​=Pi​. One can then represent the sequences to be counted by listing the sequence of vertices Pi0​​Pi1​​…Pim​​ visited by the marker, with the conventions that i0​=0,im​=2n, and ij+1​−ij​∈{1,2} for j=0,…,m−1. One can represent such sequences of vertices in turn by 2×(n+1) matrices A by setting
Aij​={10​Pni+j​ is visited Pni+j​ is not visited ​(i=0,1;j=0,…,n)
Such a matrix A corresponds to a valid sequence if and only if A00​=A1n​=1 (so the sequence of steps starts and ends at P0​ ), A0n​=An0​ (so the sequence of steps is well-defined at Pn​ ), and there are no submatrices of any of the forms
(0​0​),(00​),(11​11​)
(to exclude steps of length greater than 2 , duplication of a length 2 step, and duplication of a length 1 step). For example, the valid sequences for n=3 are represented by the matrices
(10​01​10​01​),(10​01​11​01​),(11​10​01​11​),(10​11​10​01​),(11​01​10​11​).
Let Sn​ be the set of valid 2×(n+1) matrices. The correspondence Sn−2​⊔Sn−2​⊔Sn−1​≅Sn​ can then be described by replacing the right end of the matrix in the following fashion, where ⋯ represents any row of length n−2.
​(⋯⋯​11​)∣∣∣∣∣​(⋯⋯​11​10​11​),(⋯⋯​11​01​11​)(⋯⋯​01​)(⋯⋯​01​10​01​),(⋯⋯​01​11​01​)​
From this description, it is easy to see that passing from one side to the other preserves the boundary condition and the excluded submatrix conditions (because every submatrix whose entries are not all shown remains unchanged). We thus have the claimed bijection. This solution was suggested by Kiran Kedlaya.
Third Solution: This solution uses some of the same notation as the second solution.
We first solve a related but simpler counting problem. Let Sn​ be the set of sequences of steps of lengths 1 or 2 of total length n. For each sequence s∈Sn​, let b(s) be the number of steps of length 2 in s and define fn​=∑s∈Sn​​2b(s). It is clear that f0​=f1​=1. For n≥2, we also have
fn​=fn−1​+2fn−2​
by counting sequences of length n according to whether they end in a step of length 1 or 2. Thus
fn​+fn−1​=2(fn−1​+fn−2​)
from which it follows by induction on n that fn​+fn−1​=2n for n≥1. By induction on n, we also have
fn​=32n+(−1)n​
We now write an​ in terms of fn​. Label the points of the circle as in the previous solution. We may separate sequences of moves into three types.
- Sequences that visit Pn​ but not Pn−1​. Such a sequence starts with some s∈Sn−2​ followed by a step of length 2 . The number of complements for s (i.e., the number of ways to complete it to a full sequence) can be seen to be 2b(s) as follows. If we decide in order whether to skip each of Pn+1​,…,P2n​, then the choice for Pn+i​ is uniquely forced if A0(i−1)​=1 and unrestricted if A0(i−1)​=0. In the notation of the previous solution, we may see this by noting that
(A0(i−1)​A1(i−1)​​A0i​A1i​​)∈{(10​11​),(11​10​),(10​01​),(11​01​),(01​10​),(01​11​)}
(This logic does not apply to P2n​ : we have A0(n−1)​=0 but must take A1(2n)​=1.) We thus get fn−2​ sequences of this type.
-
Sequences that visit Pn−1​ but not Pn​. Such a sequence starts with some s∈Sn−1​ followed by a step of length 2 . There are fn−1​ sequences of this type.
-
Sequences that visit both Pn−1​ and Pn​. Such a sequence starts with some s∈Sn−1​ followed by a step of length 1. Here the count is complicated by the constraint that we must skip P2n−1​, so the final step of length 2 does not create an option. Therefore, s contributes 2b(s)−1 complements if b(s)>0. The only case where b(s)=0 is when s consists of only steps of length 1 , in which case we get 1 complement if n is even and 0 complements if n is odd.
Putting this together, we get
an​​=fn−2​+fn−1​+21​(fn−1​+(−1)n)=32n−2+(−1)n−2​+32n−1+(−1)n−1​+62n−1+(−1)n−1​+2(−1)n​=32n+(−1)n​​
and so an−1​+an​=2n as desired.
Remark. The sequence an​ is known as the Jacobsthal sequence and has many other combinatorial interpretations. See sequence A001045 in the Online Encyclopedia of Integer Sequences: http://oeis.org
This solution was suggested by Kiran Kedlaya.
The problems on this page are the property of the MAA's American Mathematics Competitions