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.
 A: 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.
A: 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.$
