Two sequences of integers, and , satisfy the equation
for each integer greater than . Prove that there is a positive integer such that .
Solutions — 2
Solution 1
Define . Notice that
and
Adding these two equations and using the given implies that
hence
where equality holds if and only if and . Therefore, the sequence
is nonincreasing. Since all the terms of this sequence are nonnegative integers, the sequence must eventually become constant: for all sufficiently large , which in particular implies for all sufficiently large . So whenever is large enough, we have
Solution 2
(Based on work by Palmer Mebane) Let and . Then the given equation reads
To see this, note that , with equality if and only if and . Expanding and using the given equation we obtain
or
with equality if and only if and . Thus we have the claim.
Therefore, because is an integer, by the well-ordering principle, can only hold finitely many times. Thus there is a such that for all , and . This gives us the desired such that .