<s>[INST] Show that $u_1^3+u_2^3+\cdots+u_n^3$ is a multiple of $u_1+u_2+\cdots+u_n$ 
  
*
  
*Let $k$ be a positive integer.
  
*Define $u_0 = 0\,,\ u_1 = 1\ $ and $\ u_n = k\,u_{n-1}\ -\ u_{n-2}\,,\
n \geq 2$.
  
*Show that for each integer $n$, the number
  $u_{1}^{3} + u_{2}^{3} + \cdots + u_{n}^{3}\ $ is a multiple of
  $\ u_{1} + u_{2} + \cdots + u_{n}$.
  

Computing a few terms I found 
\begin{align*}u_0 &= 0\\u_1 &= 1\\u_2 &= k\\u_3 &= k^2-1\\u_4 &= k(k^2-1)-k = k^3-2k\\u_5 &= k(k^3-2k)-(k^2-1) = k^4-3k^2+1\\u_6 &= k(k^4-3k^2+1)-(k^3-2k) = k^5-4k^3+3k.\end{align*}
I am not sure how we can use this to solve the question, but I think it may help. Cubing these expressions seems very computational so there must be an easier way.
 [/INST] fiddling with small $k.$ Take $x = \Sigma u_j, \; \; y = \Sigma u_j^3.$
CONCLUSION: for $k \geq 2,$
$$ \color{blue}{ y = \frac{x^2 ((k-2) x + 3)}{k+1},}  $$
while $\color{blue}{x \equiv 0,1 \pmod {k+1}}.$
When  $k=2,$ $$ y = x^2. $$ This comes up pretty often, the sum of the consecutive cubes (starting with $1$) is the square of the sum of the consecutive numbers.
When $k=3,$ $$ y = \frac{x^2 (x + 3)}{4}. $$
For this one, you need to know that $x \equiv 0,1 \pmod 4.$
This already suggests that $k=4$ gives $y = a x^4 + b x^3 + c x^2 + d x,$ with rational coefficients, and some restrictions on $x$ that make $y$ an integer. If true, the coefficients can be found by taking four $x$ points, then making and inverting a certain four by four rational matrix. NOPE, not that much effort required. Stays cubic, a three by three matrix would have been enough...
Not quite what I expected: for $k=4,$
$$  y = \frac{x^2 (2 x + 3)}{5},  $$
while $x \equiv 0,1 \pmod 5.$
For $k=5,$
$$  y = \frac{x^2 (3 x + 3)}{6},  $$
while $x \equiv 0,1 \pmod 6.$
For $k=6,$
$$  y = \frac{x^2 (4 x + 3)}{7},  $$
while $x \equiv 0,1 \pmod 7.$
Apparently, for $k \geq 2,$
$$ \color{red}{ y = \frac{x^2 ((k-2) x + 3)}{k+1},}  $$
while $x \equiv 0,1 \pmod {k+1}.$
Recall  $x = \Sigma u_j, \; \; y = \Sigma u_j^3.$
</s>