It's easy by operator algebra. The Shift and Triple $\mathbb C$-linear operators $\rm\ S\,n\, :=\, n+1,\ \ T\,n\, :=\, 3\,n\, $ act on fibonacci's numbers by $\rm\ S\,f(a\,n+b) = f(a\,(n\!+\!1)+b)\ $ and $\rm\ T\,f(a\,n+b) = f(3a\,n+b).\,$ Below I show a general method that works for any Lucas sequence $\rm\,f(n)\,$ that involves only simple high-school polynomial arithmetic (albeit noncommutative). Namely, we employ a commutation rule $\rm\, TS\,\to\, (a\ S + b)\ T\ $ to shift $\rm\,T\,$ past powers of $\rm\,S,\,$ in order to transmute the known recurrence $\rm\ q(S)\, f(n) = 0\ $ into $\rm\ \bar{q}(S)\,T\,f(n)=0,\ $ the sought recurrence for $\rm\ T\,f(n) = f(3\,n).\,$
We know $\rm\ q(S)\ f(n) := (S^2 - S - 1)\ f(n)\, =\, f(n+2) - f(n+1) - f(n)\, =\, 0.\, $ We seek an analogous recurrence $\rm\ \bar{q}(S)\ T\, f(n)\, =\, 0\ $ for $\rm\ T\,f(n) = f(3\,n),\,$ and some polynomial $\rm\,\bar{q}(S).\, $ Since clearly we have that $\rm\ T\,q(S)\ f(n)\, =\, 0,\, $ it suffices to somehow transmute this equation by shifting $\rm\,T\,$ past $\rm\,q(S)\,$ to yield $\rm\,\bar{q}(S)\,T\,f(n)\,=\,0.\,$ To do this, it suffices to find some commutation identity $\rm T\,S\, =\, r(S)\, T\ $ to enable us to shift $\rm\,T\,$ past $\rm\,S$'s in each monomial $\rm\ S^{\,i}\, f(n)\, =\, f(n+i)\,$ from $\rm\,q(S).\,$ The sought commutation identity arises very simply: iterate the recurrence for $\rm\,f(n)\,$ so to rewrite
$\rm\ ST\, f(n)\ =\ f(3\,n+3)\ $ as a linear combination of $\rm\ f(3\,n+1) = TS\ f(n),\, $ $\rm\ f(3\,n) = T\ f(n),\,$ viz.
$\rm ST\ f(n+i)\ =\ f(3n+3+i)\ =\ f(3n+2+i) + f(3n+1+i)\ =\ 2\ f(3n+1+i) + f(3n+i) $
$\rm \phantom{ST\ f(n+i)}\ =\ (2\,TS+T)\ f(n+i)\quad$ for all $\rm\,i\in \mathbb Z\,$
$\rm\ 2\,TS\ f(n+i)\ =\ (S-1)\,T\ f(n+i),\ $ i.e. $\rm\ \bbox[6px,border:1px solid red]{2\,TS\ =\ (S-1)\,T} = $ sought commutation identity.
Thus $\rm\qquad\qquad\ \ 0\ =\ 4\, T\, (S^2 - S - 1)\ f(n)\ $
$\rm\qquad\qquad\qquad\quad\ \ =\ (2\,(2TS)S - 2\,(2TS) - 4\,T)\ f(n) $
$\rm\qquad\qquad\qquad\quad\ \ =\ ((S-1)\,2TS - 2\,(S-1)\,T - 4\,T)\ f(n)$
$\rm\qquad\qquad\qquad\quad\ \ =\ ((S-1)^2 - 2\,(S-1)\, - 4)\ T\, f(n)$
$\rm\qquad\qquad\qquad\quad\ \ =\ (S^2 - 4\ S - 1)\ T\, f(n)$
$\quad$ i.e. $\rm\qquad\qquad 0\ =\ f(3(n+2)) - 4\ f(3(n+1)) - f(3\,n)\qquad $ QED
Note $\ $ Precisely the same method works for any Lucas sequence $\rm\,f(n),\,$ i.e. any solution of $\rm\ 0\ =\ (S^2 + b\ S + c)\ f(n)\ =\ f(n+2) + b\ f(n+1) + c\ f(n)\ $ for constants $\rm\,b,\,c,\,$ and for any multiplication operator $\rm\,T\,n = k\ n\,$ for $\rm\,k\in \mathbb N.\,$ As above, we obtain a commutation identity by iterating the recurrence (or powering its companion matrix), in order to rewrite
$\rm\ ST\ f(n)\ =\ f(k\,n+k)\ $ as a $\rm\,\mathbb C$-linear combination of $\rm\ f(kn+1) = TS\ f(n)\ $ and $\rm\ f(kn) = T\ f(n)\,$
say $\rm\ \ ST\ f(n)= f(k\,n+k) = a\ f(k\,n+1) + d\ f(k\,n) = (a\ TS + d\ T)\ f(n)\ \ $ for some $\rm\,a,d\in \mathbb C$
$\rm\,\Rightarrow\ a\, TS\ f(n) = (S-d)\ T\ f(n)\ \Rightarrow\ a\, TS = (S-d)\, T\ $ on $\rm\ S^{\,i}\, f(n)\ $ as above.
Again, this enables us to transmute the recurrence for $\rm\,f(n)\,$ into one for $\rm\,T\,f(n) = f(k\,n)\,$ by simply commuting $\rm\,T\,$ past all $\rm\,S^i\,$ terms. Hence the solution involves only simple polynomial arithmetic (but, alas, the notation obscures the utter simplicity of the method).