Consider the graph $P\_3$ : $n\_1$$ \rightarrow$ $n\_2$$\rightarrow$ $n\_3$$\rightarrow$ $n\_4$

we count 6 paths of length k=1, namely: 

$n\_1$ $\rightarrow$ $n\_2$ 

$n\_2$ $\rightarrow$ $n\_3$

$n\_3$$\rightarrow$ $n\_4$

$n\_4$$\rightarrow$ $n\_3$

$n\_3$$\rightarrow$ $n\_2$

we count 10 for k=2, and we define the Fibonacci sequence $f$ for k $\geqslant$ 3: 

$f\_1$ = 6, $f\_2$ = 10

$f\_k$ := $f\_{k-1}$ + $f\_{k-2}$

with that we see that $f\_3$ = 16, $f\_4$ = 26, $f\_5$ = 42, etc

... that's as far as i've gotten and now i'm stuck.