Question about recursive relations between number of elements in residue classes of 3 with n digits The purpose of this 3 part question is to find an explicit formula (i.e. not a recursive one) for the number of numbers in An , Bn , Cn which are defined as the sets of n-digit natural numbers equal to 0,1,2 modulo 3 respectively. [For example |A1|=4 since A1={0,3,6,9} , |B2|=30 since B2={10,13...97} |C1|=3 since C1 ={2,5,8} etc.]
The parts (stages) in solving this question are as follows:

*

*Write |An| as an expression of |Bn-1|,|Cn-1|, write|Bn| as an expression of |An-1|,|Cn-1| and
write |Cn| as an expression of |An-1|,|Bn-1|.


*Use 1 to find a recursive relation for |An|,|Bn|,|Cn|.
3."Solve" the recursive relations to find an explicit formula for |An|,|Bn|,|Cn|
My problem is actually stage 1 since I think that from there it should be easy.
Will be grateful for any thoughts and suggestions on this. Been stuck on this for a few hours
 A: For this problem I suspect that you’re not intended to consider $0$ a natural number: if you include it, the natural recurrence breaks down between $n=1$ and $n=2$.
Each $n$-digit number is obtained from an $(n-1)$-digit number by multiplying it by $10$ and adding a one-digit integer (including $0$). Note that $10k\equiv k\pmod3$ (why?), so $10k+d\equiv k+d\pmod3$. For instance, $54=10\cdot 5+4\equiv5+4\equiv0\pmod 3$. So where do the members of $A_n$ come from? They are the numbers $10k+d$ such that $k$ is an $(n-1)$-digit number, $d$ is a digit, and $k+d\equiv0\pmod3$. That means that either $k\equiv d\equiv0\pmod3$, or $k\equiv 1\pmod3$ and $d\equiv2\pmod3$, or $k\equiv2\pmod3$ and $d\equiv1\pmod3$.

*

*If $k\equiv0\pmod3$, there are $4$ choices for $d$ — $0,3,6$, and $9$ — and there are $|A_{n-1}|$ choices for $k$; these account for $4|A_{n-1}|$ $n$-digit multiples of $3$.

*If $k\equiv1\pmod3$, there are $3$ choices for $d$ — $2,5$, and $8$ — and there are $|B_{n-1}|$ choices for $k$; these account for $3|B_{n-1}|$ $n$-digit multiples of $3$.

*And if $k\equiv2\pmod3$, there are $3$ choices for $d$ — $1,4$, and $7$ — and there are $|C_{n-1}|$ choices for $k$; these account for $3|C_{n-1}|$ $n$-digit multiples of $3$.

Thus, $|A_n|=4|A_{n-1}|+3|B_{n-1}|+3|C_{n-1}|$. Unfortunately, you’re asked to find $|A_n|$ just in terms of $|B_{n-1}|$ and $|C_{n-1}|$. Fortunately, it’s not too hard to get rid of the $A_{n-1}$ if you see that there are
$$(10^n-1)-(10^{n-1}-1)=10^n-10^{n-1}=9\cdot10^{n-1}$$
$n$-digit positive integers: that implies that $$|A_n|+|B_n|+|C_n|=9\cdot10^{n-1}$$ for each $n$. In particular, $|A_{n-1}|=9\cdot10^{n-2}-|B_{n-1}|-|C_{n-1}|$, so
$$\begin{align*}
|A_n|&=4|A_{n-1}|+3|B_{n-1}|+3|C_{n-1}|\\
&=4\big(9\cdot10^{n-2}-|B_{n-1}|-|C_{n-1}|\big)+3|B_{n-1}|+3|C_{n-1}|\\
&=36\cdot10^{n-2}-|B_{n-1}|-|C_{n-1}|\,.
\end{align*}$$
You can use the same kind of reasoning to get the other two recurrences.
I will note, however, that this is not really a very good problem, since it’s actually easier to derive the closed forms of $|A_n|,|B_n|$, and $|C_n|$ directly by observing that since $9\cdot10^{n-1}$ is a multiple of $3$, the $9\cdot10^{n-1}$ $n$-digit numbers can be divided into $3\cdot10^{n-1}$ blocks of $3$ consecutive integers, and each of these blocks contains one member of $A_n$, one member of $B_n$, and one member of $C_n$.
