Permutation and Combination Puzzle - Spy Keypad Keypad
1 2 3
4 5 6
7 8 9

J. Bond has to break into the headquarters of an evil organization
and steal important documents. The documents are in a safe that
can only be opened by entering the correct code into the keypad,
which is a 3 × 3 grid as shown on the right.
Bond has been told that every two consecutive digits in the code will
always be adjacent keys on the keypad. For example, the digit 1 will
only be followed by a 2 or 4, the digit 5 will only be followed by a
2, 4, 6 or 8, and so on. So 3252 and 12369 are valid codes, but 1234
is not (3 is not adjacent to 4 on the keypad) and 55 is not (5 is not
adjacent to 5 on the keypad).
Bond also knows the ﬁrst digit of the code and the length of the code. From this, he
would like to compute the number of possible codes he has to try. For instance, if the
ﬁrst digit is 4 and the length of the code is 3, then there are 8 possible codes, namely
{412, 414, 452, 454, 456, 458, 474, 478}.
In each of the following cases, given the ﬁrst digit of the code and the number of digits
in the code, help Bond compute the total number of possible secret codes. 
(a) First digit 2, number of digits 8.
(b) First digit 5, number of digits 10.
(c) First digit 9, number of digits 13.

This was a real tough one that I simply cannot get through.
Help please?

First of all, note that there are $3$ classes of numbers: corner ($1,3,7,9$), edge ($2,4,6,8$) and centre ($5$). Now clearly a corner number can be followed by any $1$ of $2$ edge numbers. An edge number can be followed by any $1$ of $2$ corner numbers or a centre number. And a centre number can only be followed by $1$ of $4$ edge numbers. Using these relations, define $3$ functions $C(n)$,$E(n)$ and $Cen(n)$ where $C(n)$ represents the total possible number of strings of length $n$ starting with a corner number. Likewise for the other 2 functions. Now we have $$C(n)=2\cdot E(n-1)$$ $$E(n)=2\cdot C(n-1)+Cen(n-1)$$ $$Cen(n)=4 \cdot E(n-1)$$ Also you can determine the initial values for the $3$ functions $$C(1)=E(1)=Cen(1)=1$$ Using these and the recurrence relations you're good to go.  
