Problem 1432

Let $a_{i}, b_{i}, c_{i}, d_{i}$ be the number of paths that end by $1, 2, 3, 4$ respectively and have the sum equal to $i$. These paths all start from $1$. So it is easy to check that
$$\begin{aligned} & a_{1}=1,\ b_{1}=c_{1}=d_{1}=0,\ a_{2}=b_{2}=c_{2}=d_{2}=0 \\ & a_{3}=0,\ b_{3}=1,\ c_{3}=d_{3}=0,\ a_{4}=1,\ b_{4}=c_{4}=d_{4}=0 \end{aligned}$$
We can visit $1$ from $2$ or $4$, visit $2$ from $1$ or $3$, visit $3$ from $2$ or $4$, visit $4$ from $3$ or $1$ then we have the following relations
$$\left\{ \begin{array}{l} a_{n}=b_{n-1}+d_{n-1} \\ b_{n}=a_{n-2}+c_{n-2} \\ c_{n}=b_{n-3}+d_{n-3} \\ d_{n}=c_{n-4}+a_{n-4} \end{array} \right.$$
We have to calculate $a_{21}+b_{21}+c_{21}+d_{21}$. Denote $u_{n}=a_{n}+c_{n}$ and $v_{n}=b_{n}+d_{n}$ for $n \geq 1$ then we come to another relation
$$\left\{ \begin{array}{l} u_{n}=v_{n-1}+v_{n-3} \\ v_{n}=u_{n-2}+u_{n-4} \end{array} \right.$$
We also have $u_{1}=1,\ u_{2}=0,\ u_{3}=0,\ u_{4}=1$ and $v_{1}=0,\ v_{2}=0,\ v_{3}=1,\ v_{4}=0$. Then $v_{n}=v_{n-3}+2v_{n-5}+v_{n-7}$ and $u_{n}=u_{n-3}+2u_{n-5}+u_{n-7}$.

By putting $s_{n}=u_{n}+v_{n}$, we get
$$s_{n}=s_{n-3}+2s_{n-5}+s_{n-7}$$
with $s_{1}=1,\ s_{2}=0,\ s_{3}=1,\ s_{4}=1,\ s_{5}=1,\ s_{6}=3,\ s_{7}=1$. By direct calculation, we have
$$\begin{aligned} & s_{8}=4,\ s_{9}=5,\ s_{10}=4,\ s_{11}=11 \\ & s_{12}=8,\ s_{13}=15,\ s_{14}=22,\ s_{15}=20 \\ & s_{16}=42,\ s_{17}=42,\ s_{18}=61,\ s_{19}=94 \\ & s_{20}=97,\ s_{21}=167 \end{aligned}$$
Therefore, we have $167$ paths such that the sum of numbers on these paths is equal to $21$.