This is a question that i saw in one of the textbooks that i am doing exercise on and i am unable to solve it. I am not sure which method to use. Please help.
Consider the following $n × n$ $(n ≥ 1)$ grid. John needs to go from the point $S$ (upper left corner) to the point $T$ (lower right corner). At each step, he has 3 choices: (i) go right two vertices, then go down two vertices; (ii) go down two vertices, then go right two vertices; or (iii) go along the diagonal to the next vertex (see the following figures). Let $X(n)$ be the number of ways John can go from $S$ to $T$
Prove that $X(k) = X(k-1) + 2X(k-2)$ for $k ≥ 3$
Hint: Consider the $X(k)$ ways to traverse the $k \times k$ grid, and divide them into three categories based on the first move he takes. How many are in each category?
Edit: Consider the $X(k)$ ways to traverse the $k \times k$ grid. If he choose choice (i) for the first step, then after that step he will have to traverse a $(n-2) \times (n-2)$ grid, so there are $X(k-2)$ paths that start with choice (i). The same holds for choice (ii). If he chooses choice (iii) as the first step, then after that step he will have to traverse a $(n-1) \times (n-1)$ grid, so there are $X(k-1)$ paths that start with choice (iii).