Problem about T9 Keyboard and Knight Movement I am solving a problem about T9 Keyboard and knight movement: 
We have found a device which have a classic keyboard like below.

|1|2|3|
|4|5|6|
|7|8|9|
|*|0|#|

This device is protected by a secret password. We don't know what the password is,
but after several hours of reversing we know that the password was generated by
following the rules:
1, The password has length of n, and contains characters as shown on the keyboard.
2, The password must end with either *, 8 or #.
3, After one character, the character which is on the knight move pattern (as the
knight in chess) can be the next character. For example, if the current character
is 3, then the next character can be either 4 or 8.

We really want to know how many passwords can be generated given length n, so that
we can know whether to give up brute-force or not. Ah, because that number may be
very large so you just need to give us the answer modulo 1e39.

These are something I calculated:
We can create password from the last character, which are *, # and 8.
nAsterisk(x), nSharp(x), nEight(x) will be the number of possible x-length passwords
I used brute-force to calculate several cases and receive a table like this:




x
fAsterisk
fSharp
fEight




0
1
1
1


1
2
2
2


2
5
5
4


3
11
11
10


4
28
28
22


5
65
65
56


6
163
163
130


7
388
388
326


8
961
961
776


9
2315
2315
1922




I saw several patterns:
fAsterisk = fSharp for every x, and also 
fEight(x) = fAsterisk(x-1)*2

The thing I am very struggle is the last pattern I found:
fAsterisk(x) = fAsterisk(x-1)*2+numberOfChildNodeThatHaveThreeAdjacentButton

For example:
   *
 /   \
 5    9
/ \ / | \
* # 2 4 7

fAsterisk(2) here is 5, and it equals fAsterisk(1)*2 + 1 because we only have 9 as a node that have 3 adjacents. After calculate, I have a serie for this number: 
0,1,1,6,9,33,62,185,393,1062,...

I am wonder that if there is a way to calculate the number of nodes have 3 adjacents or not. Or is there any better way or pattern to solve this problems. I tried brute-force way but the number is too big that I can't calculated for x = 88.
 A: You need to find a recurrence relation that computes the number of passwords of length $n$ from the number of shorter lengths.  If you color the keys like a checkerboard there are six of each color.  A knight move takes you from one color to the other.  $8, *, \#$ are all of the same color.  By symmetry there are only four types of keys, which are $1,5,7,0$ in one color.
You should look at the passwords in reverse, so they start with $8,*,\#$.  Make four recurrences, one for the number of passwords of length $n$ with each type of ending key.  For example, a password ending in $1$ must have ended in $6$ or $8$ the time before, which are equivalent by symmetry to ending in $7$ or $5$.  You should get four coupled recurrences, which you can view as multiplying a length $4$ vector of numbers of passwords by a $4 \times 4$ matrix to get the number of passwords of one more character.
A: For a character set $S$, let $f_S(n)$ be the number of passwords of length $n$ ending in character $x$ when $x\in S$.
Let $A=\{1,3,*,\#\}$, $B=\{2,0\}$, $C=\{4,6,7,9\}$, $D=\{5,8\}$. We are looking for $g(n):=2f_A(n)+f_D(n)$.
By inspection, we find recurrence relations such as
$$ f_A(n)=f_C(n-1)+f_D(n-1)$$
and
$$ f_C(n)=f_A(n-1)+f_B(n-1)+f_C(n-1)$$
and similar equations for $f_B(n)$ and $f_D(n)$. Then solve these linear recurrences (noting that $f_S(0)=1$ for all $S$).

To elaborate, with $\mathbf f(n)=(f_A(n),f_B(n),f_C(n),f_D(n))^T$, we find
$$ \mathbf f(n)=M\cdot\mathbf f(n-1)$$
with the matrix
$$ M=\begin{pmatrix}0&0&1&1\\
0&0&2&0\\
1&1&1&0\\
2&0&0&0
\end{pmatrix}.$$
Note that this in particular contains your observation that $f_D(n)=2f_A(n-1)$.
Now one way to solve the original problem is to compute $M^n\bmod 10 ^{39}$ by the well-known square-and-multiply method in $O(\log n)$ time (and using non-negative integers $<10^{78}$ as intermediate results) and multiplying it with $\mathbf f(0)=(1,1,1,1)^T$.
Given that one only wants to find one value instead of four, one may alternatively want to get rid of the additional three variables. But at best, this will take you to a four-term linear recursion. Of course, we may readily find a good approximation $g(n)\approx c\lambda_\max^n$ where $c$ is some constant and $\lambda_\max$ the greatest eigenvalue of $M$ (for the record, $\lambda_\max\approx 2.438283239$). However, this won't help for the original problem of finding $g(n)$ exactly modulo some integer.
