Let $a_n$ be the number of ways to do it for a $2 \times n.$ By casework on whether or not the last $2 \times 1$ is composed of two black squares, it's easy to obtain the recursion $a_n = a_{n-1} + a_{n-2}$ for $n \ge 3.$ It's easy to see that $a_1 = 4, a_2 = 15.$ Now, let's define $(b_{2k}, b_{2k+1}) = \left(\frac{a_{2k}}{3^k}, \frac{a_{2k+1}}{3^k}\right)$ for each $k \in \mathbb{N}.$ We get that $(b_{2i+2}, b_{2i+3}) = (b_i + b_{i+1}, 3b_i + 4b_{i+1})$ for each $i \in \mathbb{N}.$ Looking at the sequence $\{b_i\}$ modulo $9$, it's easy to obtain that it is periodic with period $18$: $$b_1 = 4, b_2 = 5, b_3 = 1, b_4 = 6, b_5 = 1, b_6 = 7, b_7 = 4, b_8 = 2, b_9 = 1, b_{10} = 3, b_{11} = 1, b_{12} = 4, b_{13} = 4, b_{14} = 8, b_{15} = 1, b_{16} = 0, b_{17} = 1, b_{18} = 1, b_{18} = 4, b_{19} = 5, b_{20} = 1, \cdots$$ Thus, we get that $b_{2018} \equiv b_2 \equiv 5$ (mod $9$), and so $a_{2018} = 3^{1009} \cdot b^{2018}$ clearly has a $v_3$ of $\boxed{1009}.$ $\square$

Maybe I'm wrong, but I think you've chosen the wrong recursion. Indeed, from a 2*(n+1) grid, we part an 2*n grid and the last two cells, for each of the four combination for the last two cells, we have a_n combinations for the 2*n grid UNLESS the last two cells of the 2*n grid are black and thus subtracting a_(n-1) from 4*a_n Thus the sequence is a_(n+1)= 4*a_n - a_(n-1),( by the way you can easily check a_3 =57=15*4-3) Then again, by an easy induction, every term is going to be either 3 or 6 (mod 9) and we get k=1. Please comment if I didn't notice something

Let $P_n$ be the number of colourings of a $2\times n$ grid, $A_n$ be the number of colourings in which the first two sqaures are coloured black and $B_n$ be the number of colourings in which at least one of the first two squares is coloured white. Then $P_1=4$, $P_2=15$, and for $n\geq 3$, \begin{align*} P_n &= A_n + B_n \\ A_n &= B_{n-1} \\ B_n &= 3(B_{n-1}+A_{n-1}) \\ \therefore \qquad A_n &= 3(B_{n-2}+A_{n-2}) \\ \therefore \qquad B_n &= 3(B_{n-1}+B_{n-2}) \\ \therefore \qquad P_n &= 3(P_{n-1}+P_{n-2}) \end{align*}Let $v(n)$ denote the highest power of 3 that divides $P_n$. We have that $v(1)=0$, $v(2)=1$, $v(3)=1$, $v(4)=3$, $v(5)=2$, $v(6)=3$, etc. It is easy to see by induction that $v(2k-1) \geq k-1$, $v(2k)\geq k$. That is, $v(n)\geq \lfloor \frac{n}{2}\rfloor$. Let $Q_n=\frac{P}{3^{\lfloor n/2\rfloor}}$. Then $Q_n$ saitisfies the recurrence relations: \begin{align*} Q_{2k} &= Q_{2k-1}+Q_{2k-2} \\ Q_{2k-1} &= 3Q_{2k-2}+Q_{2k-3} \end{align*}From this, we have $Q_1=4$, $Q_2=5$, $Q_3=19$, $Q_4=24$, $Q_5=91$, etc. Taking mod 3 of the above relations, we have \begin{align*} Q_{2k} &= Q_{2k-1}+Q_{2k-2}\pmod{3} \\ Q_{2k-1} &= Q_{2k-3} \pmod{3}. \end{align*}The second equation gives $Q_n\equiv Q_1\equiv 1\pmod{3}$ for all $n$ odd. Therefore, $Q_{2k}\equiv 1+Q_{2k-2}\pmod{3}$. Inductively, $Q_{2k}\equiv k-1+Q_2 \pmod{3}$. Since $Q_2=5$, we have $Q_{2k}\equiv k+1\pmod{3}$. Thus, \[Q_{2018}\equiv 1010\equiv 2\pmod{3}.\]Therefore, $P_{2018}/3^{1009}=Q_{2018}$ is not divisible by 3. In other words, $v(2018)=1009$.