We establish the recursion for all $n$ by writing the rank-2 theta series $A(n)$ in terms of the rank-1 thetas $$ S(q) := \sum_{m \in \bf Z} q^{m^2} = 1 + 2q + 2q^4 + 2q^9 + \cdots, $$ $$ T(q) := \sum_{m \in \bf Z} q^{(m+\frac12)^2} = 2q^{1/4} + 2q^{9/4} + 2q^{25/4} + \cdots. $$ The lattice corresponding to the principal positive binary form of discriminant $-s = -3^{2n+1}$ is the union of the rectangular lattice ${\bf Z} \oplus {\bf Z}\langle s \rangle$ and its translate by $(1/2, 1/2)$. The quadratic form is a multiple of $3$ iff the ${\bf Z}$ or ${\bf Z} + \frac12$ term is a multiple of $3$. Hence $$ A(n) = (S(q)-S(q^9)) \, S(q^s) + (T(q)-T(q^9)) \, T(q^s). $$ Because $9$ and $s$ are powers of $3$, an equivalent formula in characerstic $3$ is $$ A(n) = (S-S^9) S^s + (T-T^9) T^s $$ where $S=S(q)$, $T=T(q)$. We claim that the recursion is already satisfied by $A_1(n) := S^s$ and $A_2(n) := T^s$ separately, from which it will follow by linearity for $A(n) = (S-S^9) A_1(n) + (T-T^9) A_2(n)$. For both $i=1$ and $i=2$ each side of the recursion $$ A_i(n+2) = (A^{3s} + A^{2s} + 1) A(n+1) - A^{2s} A(n) $$ is the ($3^{2n}$)-th power of its $n=0$ case $$ A_i(2) = (A^3 + A^2 + 1) A_i(1) - A^2 A_i(0), $$ so we need only verify this last identity for both $i$.
Now $S$ and $T$ are related by $S^4 + T^4 = 1$, because in characteristic zero $S^4 + T^4$ is the theta series of the $D_4$ lattice, whose automorphism group contains a $3$-cycle that acts freely on nonzero vectors. [Check: $A(0)$ vanishes because it equals $$ S^4-S^{12} + T^4-T^{12} = (S^4+T^4) - (S^4+T^4)^3 = 1 - 1^3 = 0.] $$ Thus $$ A(1) = S^{28} - S^{36} + T^{28} - T^{36} = S^{28} - S^{36} + (1-S^4)^7 - (1-S^4)^9, $$ which comes to $S^{24} - S^{16} + S^{12} - S^4$, and by symmetry also $A(1) = T^{24} - T^{16} + T^{12} - T^4$. Then $A_i(2) = (A^3 + A^2 + 1) A_i(1) - A^2 A_i(0)$ is just an identity in $({\bf Z}/3{\bf Z})[S]$ or $({\bf Z}/3{\bf Z})[T]$, which we verify by direct computation to complete the proof.