## Saturday, May 16, 2015

### IMO problem that could be solved easily by the linear homogeneous recursion method

If $a,\,b,\,x,\,y\in R$ such that

$ax +by =7$

$ax^2+by^2=49$

$ax^3+by^3=133$

$ax^4+by^4=406$

Evaluate $ax^5+by^5$.

For those who have knowledge about linear homogeneous recursion, this problem is a straightforward genre material that is use for practice to further promote grasping of a fuller understanding of the method of solving linear homogeneous recursion problem.

This is a solution provided by Mark, another math contributor at this blog:

From the form of the given expressions, we may use an auxiliary equation of:

$(r-x)(r-y)=r^2-(x+y)r+xy=0$

to determine the linear homogeneous recursion:

$S_{n+2}=(x+y)S_{n+1}-xyS_{n}$

where we are given:

$S_1=7,\,S_2=49,\,S_3=133,\,S_4=406$

Using the recursive definition and the given values, we may write:

$S_3=49(x+y)-7xy=133$

$S_4=133(x+y)-49xy=406$

Solving this system, we find:

$x+y=2.5,\,xy=-1.5$ hence, we have:

$S_{n+2}=2.5S_{n+1}+1.5S_{n}$

Thus, we may compute:

$S_5=2.5(406)+1.5(133)=1214.5$

Despite of how simple this problem that it could be solved even without breaking a sweat, it deserves a place and is considered one of the best quality of IMO contest problem because it could stretch our imagination as there is one other method that one could use to tackle it. It is nevertheless the most creative and elegant way to tackle this problem and the solver is from the U.K.

Therefore, I hope you would take up the challenge and let's see if you could solve this problem using another methods that I have shown you in this post and  evaluate-ax^5+by^5. I will post back soon to reveal of how the solver from the U.K. approached this problem.