Let be a regular hexagon of side length , and be the centre of the hexagon. In addition to the sides of the hexagon, line segments are drawn from to each vertex, making a total of twelve unit line segments. Find the number of paths of length along these line segments that start at and terminate at .
Solution
The answer is .
For each integer , let be the number of paths of length starting at and terminating at . Also, let be the number of paths of length starting at and terminating at . By symmetry, is also the number of those paths terminating at any of .
To count for , the step must terminate at one of . For each of these points, there are paths terminating at that point. This gives a total of paths. In other words, we have
To count for , suppose the step terminates at . Then the step may terminate at or . If it is or , then there are paths. If it is , then there are paths. Therefore, we have
Combining (1) and (2), we obtain
This can be rewritten as for . The roots of the characteristic equation are . Suppose . Using the initial conditions and , we solve
This yields and . Therefore, the answer is