In this chapter we study the (half) infinite path, finite paths, and various graphs that can be constructed from paths. Since these graphs are all symmetric, we can do away with the left and right adjectives for the various mathematical objects. A family of polynomials will play a central role.
Define the family of polynomials \(\{P_n: n \in \N\}\) by the following initial conditions and recursion relation: \begin{align} & P_0(t) = 1, \; P_1(t) = t, \quad t \in \R \\ & P_{n+1}(t) = t P_n(t) - P_{n-1}(t), \quad n \in \N_+, \, t \in \R \end{align}
The first few members of the family are \begin{align*} P_0(t) & = 1 \\ P_1(t) & = t \\ P_2(t) & = t^2 - 1 \\ P_3(t) & = t^3 - 2 t \\ P_4(t) & = t^4 - 3 t^2 + 1 \end{align*} This family of polynomials is closely related to a family of Chebyshev polynomials, and with this connection, the important properties follow easily.
\(P_n(t) = U_n(t / 2)\) for \(n \in \N\) and \(t \in \R\) where \(U_n\) is the Chebyshev polynomial of the second kind with degree \(n\).
This follows directly from the defining conditions for \(\{U_n: n \in \N\}\): \begin{align*} & U_0(t) = 1, \; U_1(t) = 2 t, \quad t \in \R \\ & U_{n+1}(t) = 2 t U_n(t) - U_{n-1}(t), \quad n \in \N_+, \, t \in \R \end{align*}
For \(n \in \N_+\), the roots of \(P_n\) are \[2 \cos\left(\frac{k}{n + 1} \pi\right), \quad k \in \{1, 2, \ldots, n\}\]
Note that \(P_n\) has \(n\) distinct (and hence simple) roots in the interval \((-2, 2)\).