Number of length-n paths in a graph with a fixed start vertex So I was looking at a few past-years' papers from the ZIO (an IOI qualifier held here in India), and I found this question:
I think this is the same as finding the number of paths of (let's take (a)) length 8 starting at vertex 4 on this graph:

1 ---- 2 ---- 3
|    |    |
4 ---- 5 ---- 6
|    |    |
7 ---- 8 ---- 9

How can this be done systematically, and (more importantly) on pen and paper?
(I have an extremely inelegant answer which I don't like. I'll post it below.)
 A: To do (a), you can start with $$\pmatrix{0&1&0\cr0&0&0\cr0&0&0\cr}$$ Then replace each entry with the sum of all its neighbors, $$\pmatrix{1&0&1\cr0&1&0\cr0&0&0\cr}$$ Do it again; $$\pmatrix{0&3&0\cr2&0&2\cr0&1&0\cr}$$ The eighth matrix you get this way will tell you, for each digit $d$, how many codes of length 8 there are starting with 2 and ending with $d$. So you just have to add up all the entries in the 8th matrix to get the answer. 
A: You can get exact formula with a little effort:
Let $a_n$ be the number of $n$ digit codes starting from corners, that is, from $1$, $3$, $7$ and $9$.
Let $b_n$ be the number of $n$ digit codes starting from sides, that is, from $2$, $4$, $6$ and $8$.
Let $c_n$ be the number of $n$ digit codes starting from center, that is, from $5$.
Note the recursing formulas for $n\geq2$:

$$
\begin{align}
a_{n+1}&=2b_n\\
b_{n+1}&=2a_n+c_n\\
c_{n+1}&=4b_n
\end{align}
$$

Also note that $a_2=2$, $b_2=3$ and $c_2=4$; and from above formulas we get $a_3=6$, $b_3=8$ and $c_3=12$.
Therefore we get $2a_n=c_n$ and $b_{n+1}=4a_n$ for all $n\geq2$.
Finally we reach a nice recursion formula: 
$$
\begin{align}
a_{n+2}&=2b_{n+1}=8a_n\\
b_{n+2}&=4a_{n+1}=8b_n\\
c_{n+2}&=2a_{n+2}=16a_n=8c_n
\end{align}
$$
It is easy to reach exact formulas from this:

$$
\begin{align}
&a_{2n}=2.8^{n-1}\\
&b_{2n}=3.8^{n-1}\\
&c_{2n}=4.8^{n-1}\\
&a_{2n+1}=6.8^{n-1}\\
&b_{2n+1}=8.8^{n-1}\\
&c_{2n+1}=12.8^{n-1}
\end{align}
$$

This may be written more compactly depending on your preference. Let me know if there's a need for clarification.
