# Show that, if $t_{3n}=x$, $t_{3n+1} = y$ and $t_{3n+2} = z$ for all values of $n$, then $p^3+q^3+3pq-1=0$

A sequence of numbers $$t_0,t_1,t_2,...$$ satisfies $$t_{n+2} = pt_{n+1} + qt_n, ~~~n\geq0$$ where $$p$$ and $$q$$ are real. Throughout this question, $$x,y,z$$ are non-zero real numbers.

Show that, if $$t_{3n}=x$$, $$t_{3n+1} = y$$ and $$t_{3n+2} = z$$ for all values of $$n$$, then $$p^3+q^3+3pq-1=0~~~~~~(*)$$ Deduce that either either $$p+q+1=0$$ or $$(p-q)^2+(p+1)^2+(q+1)^2=0$$. Hence show that either $$x=y=z$$ or $$x+y+z=0$$

I have attempted this question, but despite arriving at (*), I don't believe I did it in the correct way.

Here are my workings:

When $$n+2 = 3p, 3p+1, 3p+2$$ we get three equations.

$$\ z=py+qx\\ x=pz+qy \\ y=px+qz$$

Adding all three equations, we get, $$x+y+z = p(x+y+z) + q(x+y+z) \\ \therefore x+y+z \not=0 \implies p+q=1$$

I then cubed both sides of this equation resulting in $$p^3+q^3+3p^2+3pq^2=1 \implies p^3+q^3+3pq(p+q)-1=0 \implies p^3+q^3+3pq-1=0$$

then we can proceed to factor this expression to get $$p+q=1$$ or the sum of the squared terms.

I suspect this approach is incorrect, but not entirely sure why it's incorrect. I would appreciate an explanation on the matter.

• The argument is correct until the implication ∴𝑥+𝑦+𝑧≠0⟹𝑝+𝑞=1, but very incomplete after that point. You have: 1. to find what happens for x,y,z when their sum is not 0 (prove that they are equal); 2. to find what happens if x+y+z = 0. Apr 28 at 20:58
• Indication: once you get the homogeneous linear system in x,y,z, with parameters p and q you wonder what is the set of all solutions (x,y,z) : R^3 ? A plane? A line ? Only (0,0,0) ? This depends on the rank of the matrix of the system. Apr 28 at 21:03

The approach looks correct to me, since all the steps either follow from previous step or from given information in the question. Here I provide another solution which might be of interest for you based on linear algebra.

(FYI I am currently revising for my linear algebra exam in a few weeks, so it is a cool revision exercise for me too ;)

Firstly, we can write the linear recurrence in matrix form:

$$\begin{pmatrix} t_{n+2} \\ t_{n+1} \end{pmatrix} = \begin{pmatrix} p&q\\1&0 \end{pmatrix}\begin{pmatrix}t_{n+1}\\t_n\end{pmatrix}$$

This is usually enough. However, in this question we want to analyse the terms of period $$3$$, so let's extend the vectors:

$$\underbrace{\begin{pmatrix}t_{n+3}\\ t_{n+2}\\ t_{n+1}\end{pmatrix}}_{\vec{v_{n+1}}}=\underbrace{\begin{pmatrix}p&q&0\\1&0&0\\0&1&0\end{pmatrix}}_A\underbrace{\begin{pmatrix}t_{n+2}\\t_{n+1}\\t_n\end{pmatrix}}_{\vec{v_n}}$$

(Notice how the third column is all $$0$$, showing how useless it is.)

Now, let's look at the recurrence every $$3$$ terms:

$$\vec{v_{n+3}}=A^3\vec{v_n}=\begin{pmatrix} p^3+2pq& p^2q+q^2& 0\\p^2+q&pq&0\\p&q&0\end{pmatrix}\vec{v_n}$$

Since we're given $$(t_{3n},t_{3n+1},t_{3n+2})=(x,y,z)$$ is constant, it means that the vector $$\vec{v}=\begin{pmatrix}z\\y\\x\end{pmatrix}$$ satisfies

$$\vec{v} = A\vec{v}$$

What does this remind you of? Eigenvalues! This equation precisely tells us that $$1$$ is a eigenvalue of $$A$$ (and $$\vec{v}$$ is the corresponding eigenvector), since $$\vec{v}\neq\vec{0}$$.

This means that

\begin{align*} \det(A - I_3) &= \begin{vmatrix}p^3+2pq-1&p^2q+q^2&0\\p^2+q&pq-1&0\\p&q&-1\end{vmatrix}\\&=-\begin{vmatrix}p^3+2pq-1&p^2q+q^2\\p^2+q&pq-1\end{vmatrix} \\&= \cdots \\&= p^3+q^3-3pq-1 \\&= 0&(\text{eigenvalue})\end{align*}

As desired, and the rest follows.

Hope this helps!

• Interesting approach, it is one method among many. I gave indications to help LearningCHelpMeV2 to complete its beginning of solution. Apr 28 at 21:08
• @ChristopheLeuridan I believe all your guiding questions can be answered by analysing the equation $\vec{v} = A\vec{v}$ :D it's just the most general form and also (linear algebra) a powerful tool Apr 28 at 21:10

For a shortcut, note that the characteristic polynomial of the linear recurrence is $$\,x^2-px-q\,$$, but the additional conditions also require $$\,t_{n+3}=t_n\,$$ with characteristic polynomial $$\,x^3-1\,$$. It follows that they must have a common root, so $$\,0 = \text{res}(x^3-1, x^2 - p x - q)=-p^3 - 3 p q - q^3 + 1\,$$.

Now back to OP's actual question.

I suspect this approach is incorrect, but not entirely sure why it's incorrect.

It is incorrect because of the assumption $$x+y+z \ne 0$$ made earlier, which is not given in the problem. This does not render the attempt useless, but leaves it incomplete. Going back to what's being asked:

\begin{align} p^3+q^3+3pq-1=0 \\ \iff \quad\quad\quad\quad\; (p + q - 1) (p^2 - p q + p + q^2 + q + 1) = 0 \\ \iff \quad\quad (p + q - 1)\big((p-q)^2+(p+1)^2+(q+1)^2\big) = 0\tag{*} \end{align}

You proved that if $$\,x+y+z \ne 0\,$$ then $$\,p+q-1=0\,$$, which is sufficient for $$\,(*)\,$$ to hold. However, what remains to still be proved is that if $$\,x+y+z = 0\,$$ then either factor of $$\,(*)\,$$ is zero.

For that, substitute $$\,z=-x-y\,$$ $$\, \iff t_2 = -t_1 - t_0\,$$ in the recurrence relations for $$\,n=0, 1\,$$:

\begin{cases} \begin{align} -t_1 - t_0 = t_2 &= pt_1 +q t_0 \\ \iff \quad\quad (p+1)t_1+(q+1)t_0 &= 0 \tag{1} \\ t_0 = t_3 &= pt_2 +q t_1 = p (pt_1 +q t_0 ) + q t_1 \\ \iff \quad (p^2+q)t_1+(pq-1)t_0 &= 0 \tag{2} \end{align} \end{cases}

Regarding $$\,(1),(2)\,$$ as a homogeneous linear system in $$\,t_0,t_1\,$$ which is known to have non-trivial solutions since $$\,x,y,z \ne 0\,$$, then it follows its determinant must be zero, proving $$\,(*)\,$$:

$$0 = \begin{vmatrix} p+1 & q+1 \\ p^2 + q & pq -1 \end{vmatrix} = -\big(p^2 - p q + p + q^2 + q + 1\big)$$