Show that $u_1^3+u_2^3+\cdots+u_n^3$ is a multiple of $u_1+u_2+\cdots+u_n$

It appears that $$y_n = \dfrac{u_1^3 + \ldots u_n^3}{u_1 + \ldots + u_n}$$ satisfies the recurrence relation $$ y_n = (k^2+k-1)(y_{n-1} - k y_{n-2} + k y_{n-3} - y_{n-4}) + y_{n-5} \ \text{for}\ n \ge 6$$ Given that $y_1, \ldots, y_5$ are integers, this would imply that all $y_n$ are integers.

EDIT: Writing $\cos(\theta) = k/2$, we have $$ u_n = \frac{\sin(n\theta)}{\sin(\theta)}$$ which can be verified by induction. Don't worry about $\theta$ being real only for $|k|\le 2$.

Using this we can obtain closed-form formulas for $u_1 + \ldots + u_n$ and $u_n^3 + \ldots + u_n$, and $y_n$ (it's rather tedious if working by hand, but elementary)

$$ y_n = \frac{-\cos((2n+1)\theta) + 2 \cos(\theta) - \cos((n+1)\theta) - \cos(n\theta) + 1}{\cos(\theta) - \cos(3\theta) - \cos(2\theta)+1} $$

and it can be verified directly that this satisfies the recurrence above.

Given the equation $$ u_n=ku_{n-1}-u_{n-2}\tag{1} $$ where $u_0=0$ and $u_1=1$, we get the solution $$ u_n=\frac{\alpha^n-\alpha^{-n}}{\alpha-\alpha^{-1}}\tag{2} $$ where $$ \alpha=\frac{k+\sqrt{k^2-4}}2\tag{3} $$ except when $k=2$ where the solution is $$ u_n=n\tag{4} $$ and the result for $k=2$ follows from the fact that the sum of the cubes of the first $n$ consecutive integers is the square of the sum of the first $n$ consecutive integers. A proof without words is given in this answer.

For the solution $(2)$, we get $\alpha^2+\alpha+1=(k+1)\alpha$ and $$ \begin{align} &\sum_{j=0}^{n-1}\left(\frac{\alpha^j-\alpha^{-j}}{\alpha-\alpha^{-1}}\right)^3\\ &=\sum_{j=0}^{n-1}\frac{\alpha^{3j}-3\alpha^j+3\alpha^{-j}-\alpha^{-3j}}{\alpha^3-3\alpha+3\alpha^{-1}-\alpha^{-3}}\\ &=\frac1{\alpha^3-3\alpha+3\alpha^{-1}-\alpha^{-3}}\left(\frac{\alpha^{3n}-1}{\alpha^3-1}-3\frac{\alpha^n-1}{\alpha-1}+3\frac{\alpha^{-n}-1}{\alpha^{-1}-1}-\frac{\alpha^{-3n}-1}{\alpha^{-3}-1}\right)\\ &=\frac1{\alpha^3-3\alpha+3\alpha^{-1}-\alpha^{-3}}\left(\frac{\left(\alpha^{3n}-1\right)\left(1-\alpha^{3-3n}\right)}{\alpha^3-1}-\frac{3\left(\alpha^n-1\right)\left(1-\alpha^{1-n}\right)}{\alpha-1}\right)\tag{5} \end{align} $$ and $$ \begin{align} &\sum_{j=0}^{n-1}\frac{\alpha^j-\alpha^{-j}}{\alpha-\alpha^{-1}}\\ &=\frac1{\alpha-\alpha^{-1}}\left(\frac{\alpha^{n}-1}{\alpha-1}-\frac{\alpha^{-n}-1}{\alpha^{-1}-1}\right)\\ &=\frac1{\alpha-\alpha^{-1}}\left(\frac{\left(\alpha^{n}-1\right)\left(1-\alpha^{1-n}\right)}{\alpha-1}\right)\tag{6} \end{align} $$ Therefore, we can compute the ratios $$ \begin{align} r_{n-1} &=\left.\sum_{j=0}^{n-1}u_j^3\middle/\sum_{j=0}^{n-1}u_j\right.\\ &=\left.\sum_{j=0}^{n-1}\left(\frac{\alpha^j-\alpha^{-j}}{\alpha-\alpha^{-1}}\right)^3\middle/\sum_{j=0}^{n-1}\frac{\alpha^j-\alpha^{-j}}{\alpha-\alpha^{-1}}\right.\\ &=\frac1{\alpha^2-2+\alpha^{-2}}\left(\frac{\left(\alpha^{2n}+\alpha^n+1\right)\left(\alpha^{2-2n}+\alpha^{1-n}+1\right)}{(k+1)\alpha}-3\right)\\ &=\frac1{k^2-4}\left(\frac{\left(\alpha^{2n}+\alpha^n+1\right)\left(\alpha^{2n-2}+\alpha^{n-1}+1\right)}{(k+1)\alpha^{2n-1}}-3\right)\\ &=\frac1{k^2-4}\left(\frac{\alpha^{2n-1}+\alpha^{n}+\alpha^{n-1}+\alpha^{1}+1+\alpha^{-1}+\alpha^{1-n}+\alpha^{-n}+\alpha^{1-2n}}{k+1}-3\right)\\ &=\frac1{k^2-4}\left(\frac{\alpha^{2n-1}+\alpha^{n}+\alpha^{n-1}+\alpha^{1-n}+\alpha^{-n}+\alpha^{1-2n}}{k+1}-2\right)\tag{7} \end{align} $$ Due to the equation $$ \begin{align} &(x-1)\left(x-\alpha\right)\left(x-\alpha^{-1}\right)\left(x-\alpha^2\right)\left(x-\alpha^{-2}\right)\\ &=(x-1)\left(x^2-kx+1\right)\left(x^2-\left(k^2-2\right)x+1\right)\\ &=x^5-mx^4+kmx^3-kmx^2+mx-1\tag{8} \end{align} $$ where $m=k^2+k-1$, the ratios $r_n$ in $(7)$ satisfy the relation $$ r_n=mr_{n-1}-kmr_{n-2}+kmr_{n-3}-mr_{n-4}+r_{n-5}\tag{9} $$ Computing the first few values of $r_{n-1}$ yields $$ \begin{align} r_{-2} &=\frac1{k^2-4}\left(\frac{\alpha^{-3}+\alpha^{-1}+\alpha^{-2}+\alpha^2+\alpha^1+\alpha^3}{k+1}-2\right)\\ &=1\\ r_{-1} &=\frac1{k^2-4}\left(\frac{\alpha^{-1}+\alpha^0+\alpha^{-1}+\alpha^1+\alpha^0+\alpha^1}{k+1}-2\right)\\ &=0\\ r_{0} &=\frac1{k^2-4}\left(\frac{\alpha^1+\alpha^1+\alpha^0+\alpha^0+\alpha^{-1}+\alpha^{-1}}{k+1}-2\right)\\ &=0\\ r_{1} &=\frac1{k^2-4}\left(\frac{\alpha^3+\alpha^2+\alpha^1+\alpha^{-1}+\alpha^{-2}+\alpha^{-3}}{k+1}-2\right)\\ &=1\\ r_{2} &=\frac1{k^2-4}\left(\frac{\alpha^5+\alpha^3+\alpha^2+\alpha^{-2}+\alpha^{-3}+\alpha^{-5}}{k+1}-2\right)\\ &=k^2-k+1 \end{align}\tag{10} $$ The recurrence $(9)$ and the computations $(10)$ ensure that for all $n$, $r_n\in\mathbb{Z}$.