2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Apr 28 at 20:58
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 28 at 21:03

2 Answers 2

3
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ Interesting approach, it is one method among many. I gave indications to help LearningCHelpMeV2 to complete its beginning of solution. $\endgroup$ Apr 28 at 21:08
  • $\begingroup$ @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 $\endgroup$
    – Gareth Ma
    Apr 28 at 21:10
1
+50
$\begingroup$

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

$\endgroup$

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.