# reference request: variations on Pascal's triangle

Define Pascal's triangle as follows: it is an array $(T_{m,n})_{m, n \in \mathbf{Z}}$ of integers, satisfying

• if $m<0$, then $T_{m,n}=0$.

• $T_{0,0}=1$ and if $n \neq 0$, then $T_{0,n}=0$.

• if $m>0$, then $T_{m,j} = T_{m-1,j-1} + T_{m-1,j+1}$.

The last item makes the indexing perhaps a little unusual, but if you ignore entries $T_{i,j}$ where $i$ and $j$ have different parity (because those entries are always zero), you get Pascal's triangle.

Now consider a variation on this by truncating it to the left of column 0 and to the right of some column $N$: fix $N$ and replace the last condition with:

• if $m>0$, then for $0 \leq j \leq N$, $T_{m,j} = T_{m-1,j-1} + T_{m-1,j+1}$. If $j<0$ or $j>N$, then $T_{m,j}=0$.

For example, if $N=3$, we get this:

1
1
1   1
2   1
2   3
5   3
5   8
13  8


The entries are Fibonacci numbers, and the sums of the rows give the Fibonacci sequence.

If $N=5$, we get this:

1
1
1   1
2   1
2   3   1
5   4   1
5   9   5
14  14  5
14  28  19


The row sums are 1, 1, 2, 3, 6, 10, 19, 33, 61, 108, 197, ... (presumably this sequence).

I'm interested in what happens as $N$ varies, and in particular when $N$ is two less than a prime. For example, what are the sums of the rows? What is the limit of the $n$th root of the $n$th row? Has anyone seen this sort of thing in the literature?

You are just counting walks of various lengths starting from the leftmost vertex of a path graph $P_{N+1}$ with $N+1$ vertices. It is possible to explicitly write down the eigenvectors and eigenvalues of the adjacency matrix of a path graph: namely, the eigenvectors are $$v_i = \left( \sin \frac{\pi i}{N+2}, \sin \frac{2 \pi i}{N+2}, ... \sin \frac{(N+1) \pi i}{N+2} \right)$$
with eigenvalues $2 \cos \frac{i \pi}{N+2}$. An exact formula for the row sums can be extracted from the above information; see this blog post for a more thorough discussion, and I can write down the formula in an edit if you want. In any case, the $n^{th}$ row sum is $\Theta((2 \cos \frac{\pi}{N+2})^n)$.