$$u + v = 2$$ $$ux + vy = 1$$ $$ux^2 + vy^2 = - 1$$ $$ux^3 + vy^3 = -5$$
Can anyone give me a hint for solving this ? I'm kinda stuck.
$$u + v = 2$$ $$ux + vy = 1$$ $$ux^2 + vy^2 = - 1$$ $$ux^3 + vy^3 = -5$$
Can anyone give me a hint for solving this ? I'm kinda stuck.
HINT $\ \ $ Exploit the innate symmetry:
$\rm\quad\quad\quad\quad u x^2 + v y^2\ =\ (x+y)\ (ux\ +\ vy)\ -\ xy\ (u+v)$
$\rm\quad\quad\quad\quad u x^3 + v y^3\ =\ (x+y)\ (ux^2+vy^2) -\: xy\ (ux+vy)$
yields $\rm\quad\quad\quad\quad\:\ \ -1 \ =\ \ x+y\ -\ 2\ xy $
$\rm\quad\quad\quad\quad\quad\quad\quad\quad\quad\ 5\ =\ \ x+y\ \:\ +\:\ \ xy$
Solving yields $\rm\quad\quad\ \ x+y = 3,\ \ \ xy = 2\ \ \Rightarrow\ \ \{x,\:y\}\ =\ \{1,\:2\}$
REMARK $\ $ Readers familiar with the theory of Lucas-Lehmer sequences may recognize this recursion as one of many useful identities satisfied by sums of powers. Such identities arise in many diverse contexts. Here is another example: Capdegelle's work on FLT (Fermat's Last Theorem) employed the recursion $\rm\ F_{n+3} + S_2\: F_{n+2} + S_1\: F_{n+1} + S_0\: F_n = 0\ $ where $\rm\ F_n = X^n + Y^n - Z^n\ $ is the Fermat polynomial and the polynomials $\rm\ S_k\ $ are the elementary symmetric polynomials $\rm\ S_0 = -XYZ,$ $\rm\ S_1 = XY + XZ + YZ,\ $ $\rm S_2 = -(X+Y+Z)\:.\ $
One way to do this is using Groebner basis (which is implemented in most serious computer algebra systems, and which you can learn to do by hand in many places, like the amazing book by Cox et al. called Ideals, Varieties and Algorithms). For example, using Mathematica you can compute:
In[1]:= GroebnerBasis[{
u + v - 2,
u x + v y - 1,
u x^2 + v y^2 + 1,
u x^3 + v y^3 + 5
}, {u, v, x, y}
]
2
Out[1]= {2 - 3 y + y , -3 + x + y, -7 + v + 4 y, 5 + u - 4 y}
The result is an equivalent system of equations. You'll notice that the first equation depends only on $y$, and that the other three allow you to determine $x$, $v$ and $u$, respectively, in terms of $y$.
The book I mentioned explains why this works.
Alternatively, you can use the (freely available, great) Macaulay2:
Macaulay2, version 1.3.1
with packages: ConwayPolynomials, Elimination, IntegralClosure, LLLBases, PrimaryDecomposition,
ReesAlgebra, SchurRings, TangentCone
i1 : R = QQ[u,v,x,y,z];
i2 : I = ideal (u + v - 2, u*x + v*y-1, u*x^2+v*y^2+1, u*x^3+v*y^3+5);
o2 : Ideal of R
i3 : gens gb I
o3 = | x+y-3 v+4y-7 u-4y+5 y2-3y+2 |
1 4
o3 : Matrix R <--- R
The polynomials listed in the o3
line are a Groebner basis, i.e., an equivalent system of equations, and it allows you to solve it at once.
An elementary way would be:
Suppose $\displaystyle x$ and $\displaystyle y$ are roots of $\displaystyle z^2 + az + b = 0$.
Thus we have that $\displaystyle x^2 + ax + b = 0$ and $\displaystyle y^2 + ay + b= 0$.
Multiply the first by $\displaystyle u$, the second by $\displaystyle v$ and adding we get
$$-1 +a + 2b = 0$$
Mutiplying the first $ux$ and second by $vy$ and adding we get
$$-5 - a + b = 0$$
We can easily find $\displaystyle a$ and $\displaystyle b$ now and so can find the possibilities for $\displaystyle x$ and $\displaystyle y$.
It should be easy to solve the whole system now.
Looking for linear terms suggests we write the system as
$$\begin{pmatrix} 1 & 1 \cr x & y \cr x^2 & y^2 \cr x^3 & y^3\end{pmatrix} \begin{pmatrix} u \cr v\end{pmatrix} =\begin{pmatrix} 2 \cr 1 \cr -1 \cr -5 \end{pmatrix}.$$
Row-reduction has to give two entirely zero rows of coefficients,yielding two equations for $x$ and $y$, one of which is linear in $y$. (It will help to recognize that $x-y$ is a factor of $x^2 - y^2$ and of $x^3 - y^3$.) That makes it straightforward to find $x$, from which you obtain $y$. With $x$ and $y$ in hand the coefficients are completely determined, allowing you to solve for $(u, v)$ in the usual ways.
Actually, this problem reminds me of linear recurrences that are based on the previous 2 terms (since that is how a linear recurrence is represented): in the form $ax^k+by^k$.
So basically the linear recurrence is in the form $a_n=pa_{n-1}+qa_{n-1}$ with set values at $a_0$ and $a_1$.
Here, $a_0=2$, $a_1=1$, $a_2=-1$, $a_3=-5$. $a_2=pa_1+qa_0 \rightarrow -1=p+2q$. $a_3=pa_2+qa_1=-5=-p+q$.$5=p-q$ Then solve them to get $q=-2$ and $p=3$.
Thus the recurrence is $a_n=3a_{n-1}-2a_{n-2}$.
but I'm not really sure if method will work.