A directed graph $G_n = \langle V_n, E_n \rangle$ is defined as follows: \begin{array}{r c l} V_n &=& \{ x_i : i=0, \dots, n \} \cup \{ y_i, z_i : i=1, \dots, n \}, \\ E_n &=& \{ x_i \to x_{i+1}, x_i \to y_{i+1}, x_i \to z_{i+1} : i=0, \dots, n-1 \} \cup \\\ & & \{ y_i \to x_i : z_i \to x_i : i=1, \dots, n \} \cup \\&& \{ y_i \to y_{i+1}, z_i \to z_{i+1} : i=1, \dots, n-1 \}. \end{array} Let $a_n$ denote the number of directed paths from $x_0$ to $x_n$. Find $\lim_{n \to \infty} (a_n)^{1/n}$.
Graph for $n=4$:
My Solution:
Let $b_n$ denote the number of directed paths from $x_0$ to $y_n$, and $c_n$ the directed paths from $x_0$ to $z_n$.
We have $a_n = a_{n-1} + b_n + c_n$, (since you can reach $x_n$ from $x_{n-1}$, $y_n$ or $z_n$), and since $b_n$ and $c_n$ are the same we have $a_n = a_{n-1} + 2b_{n}$. Then $b_n = b_{n-1} + a_{n-1}$ (since you can reach $y_n$ from $y_{n-1}$ or $x_{n-1}$).
So finally we have the system of equations \begin{eqnarray*} a_n = a_{n-1}+2b_{n}+\color{black}{[n=0]}\\ b_n=b_{n-1}+a_{n-1} \end{eqnarray*} where $a_0 = 1$ and $b_0 = 0$. $[n=0]$ is an Iverson bracket.
However, in the answers, there is the system of equations:
$$ \begin{array}{c}{{a_{n}=a_{n-1}+2b_{\color{blue}{n-1}}+\color{black}{[n=0]}}}\\ {{b_{n}=a_{n-1}+\color{blue}{3b_{n-1}}}}\end{array} $$
Why is my answer wrong? Where do these differences come from?
Using Mike's definition of $a_n$ being the number of paths from $x_0$ to $x_n$ and $b_n$ being the number from $x_0$ to $y_n$, the recursion is $$ \begin{align} b_0 &= 0,\\ a_0 &= 1,\\ b_n &= b_{n-1}+a_{n-1} \; \text{for}\; n \ge 2, \; \text{and}\\ a_n &= a_{n-1}+2 b_n \;\text{for}\; n \ge 2. \end{align} $$ To operate at the degenerate $n=0$ level, we may imagine virtual $y_0$ and $z_0$ nodes with appropriate arrows leaving them to mimic the other levels. We may then delete these arrows because $b_0 = 0$ makes no contribution.
We may reduce the above to the single second-order recursion $$ \begin{align} a_0 &= 1,\\ a_1 &= 3,\; \text{and}\\ a_n &= 4a_{n-1}-a_{n-2} \;\text{for}\; n \ge 2. \end{align} $$ This is sequence A001835 in the OEIS (offset by 1). The characteristic equation of this recursion is $r^2-4r+1 = 0$, which has roots $2\pm \sqrt{3}$. Thus the limiting value of $(a_n)^{1/n}$ is $2+\sqrt{3}$. We can also write the full solution for $a_n$ for completeness: $$ a_n = \frac{3+\sqrt{3}}{6} (2+\sqrt{3})^n + \frac{3-\sqrt{3}}{6} (2-\sqrt{3})^n. $$