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.