Solution:
For the first several values of $k$ it is straightforward to find solutions $x_{k}$ and $y_{k}$ satisfying $x_{k}^{2} + 2y_{k}^{2} = 3^{k}$, leading to this table of solutions.

The key is to realize that negating any value of $x_{k}$ or $y_{k}$ also yields a solution, so we may recast the table as follows.

It is now apparent that we should take $x_{k+1} = x_{k} - 2y_{k}$ and $y_{k+1} = x_{k} + y_{k}$. One then confirms that
$$\begin{aligned} x_{k+1}^{2} + 2y_{k+1}^{2} &= (x_{k}^{2} - 4x_{k}y_{k} + 4y_{k}^{2}) + 2(x_{k}^{2} + 2x_{k}y_{k} + y_{k}^{2}) \\ &= 3(x_{k}^{2} + 2y_{k}^{2}), \end{aligned}$$
from which it easily follows by induction that $x_{k}^{2} + 2y_{k}^{2} = 3^{k}$ for all $k \geq 1$. Finally, one can also show by induction that $x_{k} \equiv y_{k} \equiv (-1)^{k} \bmod 3$, hence none of the $x_{k}$ or $y_{k}$ are divisible by $3$.