12
$\begingroup$
  1. Let $k$ be a positive integer.
  2. Define $u_0 = 0\,,\ u_1 = 1\ $ and $\ u_n = k\,u_{n-1}\ -\ u_{n-2}\,,\ n \geq 2$.
  3. 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.

$\endgroup$
  • $\begingroup$ $u_3 = k^2 - 1$, not $k^2 - k$. $\endgroup$ – Robert Israel Jul 15 '16 at 17:55
  • $\begingroup$ @RobertIsrael Thanks, fixed. $\endgroup$ – user19405892 Jul 15 '16 at 18:04
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ How did you find out $y_n$ satisfied the recurrence? $\endgroup$ – user19405892 Jul 15 '16 at 18:12
  • $\begingroup$ Using the gfun package in Maple. $\endgroup$ – Robert Israel Jul 15 '16 at 18:12
  • $\begingroup$ I am looking for an elementary way of solving this question. $\endgroup$ – user19405892 Jul 15 '16 at 18:13
  • $\begingroup$ @lhf: Sorry, that was $u_n$ not $a_n$. $\endgroup$ – Robert Israel Jul 15 '16 at 20:59
2
$\begingroup$

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}$.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ It's not too hard to show that $u_n = \frac{\left(\frac{1}{a}\right)^n-a^n}{\frac{1}{a}-a}$ where $a$ satisfy $a = \frac{1}{k-a}$ and from this the formula you put up is easily checked to be true. $\endgroup$ – Winther Jul 15 '16 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.