Given a graph $G$ and its adjacency matrix $A$. The $(i,j)$-th element of $A^r$ gives the number of ways to get from vertex $i$ to $j$ in $r$ steps (including backtracking).
Now, the number of reduced paths on cubic graphs of length $n$ (without backtracking) may be written as $p_n(x) =2^{n/2}U_n(\sqrt{2}x)$, where $U_n(x)$ is a Chebyshev Polynomial of the Second Kind.
The linked MathWorld page also says that
The polynomials can also be defined in terms of the sums $$ U_n(x)= \sum_{r=0}^{\lfloor n/2 \rfloor} (-1)^r \binom{n-r}{r}(2x)^{n-2r}\tag{16} $$
My question is:
What is the combinatorial interpretation of this relation?
$$ p_n(A/\sqrt{2})=2^{n/2}\sum_{r=0}^{\lfloor n/2 \rfloor} (-1)^r \binom{n-r}{r}(2A)^{n-2r} $$
Why do alternating signs, binomial coefficients and powers of $2$ come into play while you're summing powers of $A$, i.e. number of ways with $r$ steps including backtracking, to finally get something without backtracking?