If $$ax + by = 7$$ $$ax^2 + by^2 = 49$$ $$ax^3 + by^3 = 133$$ $$ax^4 + by^4 = 406$$find the value of $$2014(x+y-xy) - 100(a+b)$$

I came across this question in a Math Olympiad Competition and I am not sure how to solve it. Can anyone help? Thanks.

-
$a,b,x,y \in \mathbb{R}$ , right, or are they integers? – cirpis Jun 5 '14 at 12:57
Should be an integer. – snivysteel Jun 5 '14 at 13:11
I tried $a^2x^2 + 2axby + b^2y^2 = ax^2 + by^2$ but I am not sure on how to carry on from this step – snivysteel Jun 5 '14 at 13:18
You have posted quite a number of contest math questions recently, do you have a link to this problem set? – dtldarek Jun 5 '14 at 13:28
theres a contradiction, i belive, $ax+by$ is odd, thus one of the summands is odd, the other is even. suppose $ax$ is odd without loss of generality, thus $by$ is even. If $ax$ odd, then both $a$ and $x$ are odd, thus $ax^4$ is also odd. Either one or both $b$ and $y$ are even, either way $by^4$ is also even, so $ax^4+by^4$ should be odd, thus we may be dealing with real numbers, not integers. – cirpis Jun 5 '14 at 13:29

From $ax+by=7$, we have $ax=7-by, by=7-ax$. Noting $$ax^2+by^2=x\cdot ax+y\cdot by=x(7-by)+y(7-ax)=7(x+y)-(a+b)xy,$$ from $ax^2+by^2=49$, we obtain $$\tag{*} 7(x+y)-(a+b)xy=49.$$ Similarly, $$ax^2=49-by^2,by^2=49-ax^2, ax^3=133-by^3,by^3=133-ax^3,$$ from which, we have $$ax^3+by^3=x\cdot ax^2+y\cdot by^2=x(49-by^2)+y(49-ax^2)=49(x+y)-(ax+by)xy$$ and hence $49(x+y)-7xy=133$ or $$\tag{**} 7(x+y)-xy=19.$$ Finally, $$ax^4+by^4=x\cdot ax^3+y\cdot by^3=x(133-by^3)+y(133-ax^3)=133(x+y)-(ax^2+by^2)xy=133(x+y)-49xy$$ and hence $133(x+y)-49xy=406$ or $$\tag{***}\quad\quad\quad 19(x+y)-7xy=58.$$ From $(*), (**), (***)$, it is easy to see $$x+y=\frac{5}{2},xy=-\frac{3}{2},a+b=21$$ and hence $$2014(x+y-xy)-100(a+b)=5956.$$

-
Is $v=xy$? ${}{}{}{}$ – Américo Tavares Jun 5 '14 at 13:56
What is v? Why is it that it suddenly appears at the bottom. – snivysteel Jun 5 '14 at 14:09
@AméricoTavares, yes. Thank you for pointing this typo and I corrected it already. – xpaul Jun 5 '14 at 14:09
@snivysteel, this is a typo and I already corrected it. Thank you for telling me this. – xpaul Jun 5 '14 at 14:10

These equations are in the form of the first term of the general solution of a linear recurrence with constant coefficients of order $2$. The general term of the solution is $$u_n=ax^n+by^n$$ and the recurrence is $$u_{n+1}=cu_n+du_{n-1}$$ Knowing two triples from the four terms $(u_1,u_2,u_3,u_4)=(7,49,133,406)=7\cdot(1,7,19,58)$ of the sequence allows to establish equations for $c$ and $d$ \begin{align} 19&=7c+d\\ 58&=19c+7d\\ \text{and consequently}&\\ 75&=30c\\ c&=\frac52\\ d&=19-7c=\frac32 \end{align} so that $$2u_{n+2}-5u_{n+1}-3u_n=0$$ For the roots $x$ and $y$ of the characteristic equation we get $x+y=\frac52$ and $xy=-\frac32$. The expression $a+b=u_0$ is the term of the sequence before the given ones, $$a+b=\frac13(2u_2-5u_1)=\frac13(98-35)=21$$ This is sufficient to compute the crazy combination that is requested as answer.

-
I like your answer, particularly because it aligns with my intuitions. Using asymptotical approach one can guess that the maximum of $|x|$ and $|y|$ is approximated by $\frac{406}{133}\simeq 3.05 \approx 3$ and its coefficient by $\frac{406}{3^4}\simeq 5.01 \approx 5$. – dtldarek Jun 5 '14 at 15:37
But you can also solve $0=2x^2-5x-3=2((x-\frac54)^2-\frac32-\frac{25}{16})$ to get the solutions $x=\frac54\pm\frac74=\{3,-\frac12\}$. – LutzL Jun 5 '14 at 15:45
It is worth noting that the reason why the expression $ax^n + by^n$ satisfies such a linear recurrence relation is because of the identity $$ax^{n+1} + by^{n+1} = (x+y)(ax^n + by^n) - (xy)(ax^{n-1} + by^{n-1}).$$ – heropup Jun 5 '14 at 19:44
Yes, this is one formulation of it. Using generating functions and partial fraction decomposition gives another derivation of this identity. – LutzL Jun 5 '14 at 20:34