From our previous work, we shouldn't have had too much trouble finding the first few terms of \(C_n\) to be \[ C_n = \{ 1, 1, 2, 5, \dots \} \] and if you were successful in the more difficult exercises, you may have even found that \[ C_n = \{ 1, 1, 2, 5, 14, 42, \dots \} \]
Another way that we can think about this is similarly to how we would construct Pascal's Triangle. The number of paths leading to a given point is given by the sum of the number of paths from the prior adjacent vertices. Consider the following figure constructed from this premise:
To find these numbers of paths it would be particularly useful to have an algorithm that helped us generate the number of paths a given number of steps away. Bartschi and Martin (2020) describe a method of finding these paths by brute force, using an algorithm to iteratively calculate the number of paths based on an array where the \(i^\text{th}\) element are calculated as shown below:
First, note that \(c_0(1)=1\) since there is 1 possible way to start at our initial location, and that \(c_1(1)=c_1(2)=1\) since there is only one path to each location.
Now consider two general recursive cases: First, if \(j=1\), then the only paths spots adjacent to it previously were the locations of \(j=1\) and \(k=2\). Since the number of paths will be the sum of the two prior adjacent spots, then \(c_{k+1}(1) = c_k(1)+c_k(2)\). Next consider all other spots. They have two adjacency's in the half increments (having taken \(2k-1\) steps of \(2k\)). Let us denote these half steps from row \(n\) as \(c_{k+\frac{1}{2}}\left(j-\frac{1}{2}\right)\) and \(c_{k+\frac{1}{2}}\left(j+\frac{1}{2}\right)\). Using the same logic as the first case, we can express \(c_k(j)\) as the sum of these two half steps, and similarly, we can express each of the half steps in terms of the number of paths to the half steps prior, thus:
\begin{align*} c_{k+1}(j) &= c_{k+\frac{1}{2}}\left(j-\frac{1}{2}\right) + c_{k+\frac{1}{2}}\left(j+\frac{1}{2}\right)\\ &= \left(c_k(j-1) + c_k(j)\right) + \left(c_k(j) + c_k(j+1)\right)\\ &= c_k(j-1) + 2\cdot c_{k}(j) +c_{k}(j+1) \end{align*}From this process, they generated the following sequence of integers: \[ C_n = \{1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, \dots \} \] We now have more than enough information to discover if this sequence has a pattern, with a little bit of help. Visit the On-line Encyclopedia of Integer Sequence © at oeis.org, and in the search bar input the sequence found above.