<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] 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.
</s>