so what i'm thinking is that you let
x_n+3 + x_n+2<=x_n+2 + x_n+1 <= x_2 + x_1
then show that the first term can eventually go to the last term
squeezing the term into the middle
but the problem with this is i dont see where the 1/3 comes from
The way to do simple linear recursions is to try . This is very much analogous to ODEs, where you'd try , seeing what f must be, and then using superposition to add together the different possibilities for f.
Solution: Try for some constants
From get , so .
Solving that gives or . Now just like with ODEs, put them together to get the general form of the solution:
Note the required 2 unknown constants for a degree 2 linear recursion.
When you plug that in to the recursion equation, it works. It's just algebra - I won't work it out here. Thus we have the generic solution to that recursion.
Just like with ODEs, we use the initial conditions to get the specific solution:
, and . Thus
, and , which add to give , so .
To solve the problem, we don't even need to bother to find , though it would be simple to do.