Let $\phi=\frac{1+\sqrt{5}}{2}$ and $\psi=\frac{1-\sqrt{5}}{2}=-\phi^{-1}$. Then $\sqrt{5}F_n=\phi^n-\psi^n$. $ \begin{align} F_n^k & = 5^{-k/2}(\phi^n-\psi^n)^k\\ & = 5^{-k/2}\sum_{j=0}^k\binom{k}{j}\phi^{n(k-j)}(-\psi^n)^j \\ & = 5^{-k/2}\sum_{j=0}^k\binom{k}{j}(-1)^{j(n+1)}\phi^{n(k-2j)} \end{align} $ and $ \begin{align} F_n^{k+2} & = 5^{-(k+2)/2}(\phi^n-\psi^n)^{k+2}\\ & = 5^{-(k+2)/2}\sum_{j=0}^{k+2}\binom{k+2}{j}(-1)^{j(n+1)}\phi^{n(k+2-2j)} \\ & = 5^{-(k+2)/2}\left(\phi^{n(k+2)}+\sum_{j=1}^{k+1}\binom{k+2}{j}(-1)^{j(n+1)}\phi^{n(k+2-2j)}+(-1)^{k+2}\psi^{n(k+2)}\right) \end{align} $ When $k$ is odd we can rewrite the above as $ \begin{align} F_n^{k+2} - 5^{-(k+1)/2}F_{n(k+2)} & = 5^{-(k+2)/2}\sum_{j=0}^{k}\binom{k+2}{j+1}(-1)^{(j+1)(n+1)}\phi^{n(k-2j)} \end{align} $
Then consider the generating function $ \begin{align} f(x) & = \sum_{n=0}^\infty F_n^kx^n \\ & = 5^{-k/2}\sum_{n=0}^\infty\sum_{j=0}^k\binom kj (-1)^j((-1)^j\phi^{k-2j})^nx^n \\ & = 5^{-k/2}\sum_{j=0}^k \binom kj \frac{(-1)^j}{1-(-1)^j\phi^{k-2j}x}\\ & = \frac{P(x)}{\prod_{j=0}^k (1-(-1)^j\phi^{k-2j}x)} \\ & = \frac{P(x)}{1+a_1x+a_2x^2+\cdots+x^k} \end{align} $ for some polynomial $P(x)$, which indicates that $F_n^k$ obeys the recurrence relation $F_n^k+a_1F_{n-1}^k+a_2F_{n-2}^k+\cdots+F_{n-k}^k=0$.
Now let $G_n = F_n^{k+2}-5^{-(k+1)/2}F_{n(k+2)}$ and consider the generating function for $G_n$ using the form we established above $ \begin{align} g(x) & = \sum_{x=0}^\infty G_n x^n \\ & = 5^{-(k+2)/2}\sum_{n=0}^\infty\sum_{j=0}^k\binom{k+2}{j+1} (-1)^{j+1}((-1)^{j+1}\phi^{k-2j})^nx^n \\ & = \frac{Q(x)}{\prod_{j=0}^k (1-(-1)^{j+1}\phi^{k-2j}x)} \\ & = \frac{Q(x)}{1+b_1x+b_2x^2+\cdots+x^k} \end{align} $ for some polynomial $Q(x)$. From the second last line it is clear that the roots of the polynomial in the denominator are the negatives of the roots of the denominator in the expression for $f(x)$ above, so $b_i=(-1)^ia_i$, and so $G_n$ obeys the recurrence relation $G_{n+h}-a_1G_{n+h-1}+a_2G_{n+h-2}-\cdots+G_{n-h}=0 \\ F_{n+h}^{k+2}-a_1F_{n+h-1}^{k+2}+a_2F_{n+h-2}^{k+2}-\cdots+F_{n-h}^{k+2}=\pm 5^{-(k+1)/2}\sum_{i=-h}^{h}(-1)^ia_iF_{(k+2)(n+i)} $ where $h=(k-1)/2$. There's a bit more work to verify that the right side is a multiple of $F_{n(k+2)}$, but this gives an answer to the question about why the coefficients are recycled. They are the coefficients of the polynomial with roots $\phi,\psi,-\phi^3,-\psi^3,\phi^5,\psi^5,\ldots$.
We can generalize further by moving four terms to the left side: $ F_n^{k+4}-5^{-(k+3)/2}\left(F_{n(k+4)}-(-1)^n(k+4)F_{n(k+2)}\right) = \\ 5^{-(k+4)/2}\sum_{j=0}^{k}\binom{k+4}{j+2}(-1)^{(j+2)(n+1)}\phi^{n(k-2j)} $ to get additional identities like these: $ \begin{align} F_{n+2}^7-3F_{n+1}^7-6&F_n^7+3F_{n-1}^7+F_{n-2}^7 &= 6F_{7n}-(-1)^n\frac{42}{5}F_{5n}\\ F_{n+3}^9-8F_{n+2}^9-40F_{n+1}^9+60&F_n^9+40F_{n-1}^9-8F_{n-2}^9-F_{n-3}^9 &= 624 F_{9n}+(-1)^n 432 F_{7n}\\ \end{align} $