How many 5-digit numbers such that the sum of their digits is a multiple of 4? My textbook has the same problem, except for 5-digit numbers the sum of whose digits is a multiple of 5. The general approach is:
Select the first 4 digits. Number of possible ways of doing this = $9\times 10 \times 10 \times 10$ since the ten thousands-place digit cannot be zero. The sum of these 4 digits is $5k$, $5k+1$, $5k+2$, $5k+3$, or $5k+4$. If it's $5k$, the last digit may only be $0$ or $5$. Sum is $5k+1 \implies$ last digit is $4$ or $9$, and so on. In each case, there are only $2$ possible last digits.
Therefore the total number of such 5-digit numbers is $9\times 10 \times 10 \times 10 \times 2 = 18000$.

When we apply this approach to the "sum of digits is a multiple of 4" problem, we get,
Sum of first 4 digits is $4k \implies$ last digit is $0$, $4$, or $8$.
Sum of first 4 digits is $4k+1 \implies$ last digit is $3$ or $7$.
Sum of first 4 digits is $4k+2 \implies$ last digit is $2$ or $6$.
Sum of first 4 digits is $4k+3 \implies$ last digit is $1$, $5$ or $9$.
In two of these cases, we get three possible last digits and in the other two, we get two possible last digits. Our general approach clearly breaks down here. One way to go around this would be to ask ourselves, "how many ways can we select four digits such their sum is $4k$ or $4k+3$", and multiply that number by 3; repeat for $4k+2$ and $4k+1$ but multiply by 2. Add both these numbers to get the answer.
This seems too long. Is there a simpler way to do this?

Denote by $a_i(n)$ $\>(0\leq i\leq3)$ the number of $n$-digit decimal strings having a digit sum leaving remainder $i$ modulo $4$, and collect the $a_i(n)$ into $a(n):=\bigl(a_0(n), a_1(n), a_2(n), a_3(n)\bigr)$, the latter considered as a column vector. We then have $$a(1)=(2,3,2,2)\ .$$ For the latter digits the multiplicities of the possible remainders are $(3,3,2,2)$, since the digit ${\tt 0}$ with remainder $0$ is allowed.
What we have written already allows to compute $$a_0(2)=3\cdot2+2\cdot3+2\cdot2+3\cdot2=22\ .$$
Indeed, when the first digit has remainder $0$ the second also has to have remainder $0$, and when the first digit has remainder $1$ the second has to have remainder $3$, etcetera. This idea, used for all possible remainders, leads to the recursion
$$ a(n+1)=A\ a(n)\qquad(n\geq1),\qquad A:=\left[\matrix{3&2&2&3\cr3&3&2&2\cr2&3&3&2\cr2&2&3&3\cr}\right]\ .$$
In this way we obtain
$$a(5)=A^4\ a(1)=\bigl(22500, 22498, 22500, 22502\bigr)\ ,$$
so that the number we are looking for is $22\,500$. In order to compute, e.g., $a(23)$ we better find a scheme for computing the higher powers of the "cyclic" matrix $A$.
