Suppose $\{a(n) \}_{n=1}^{\infty}$ is a sequence that: \[ a(n) =a(a(n-1))+a(n-a(n-1)) \ \ \ \forall \ n \geq 3\] and $a(1)=a(2)=1$. Prove that for each $n \geq 1$ , $a(2n) \leq 2a(n)$.
Problem
Source: SRMO 2005
Tags: inequalities, induction, algebra proposed, algebra
11.04.2005 11:49
Only one of the participants in Iran solved this go on people, Solve this
12.05.2005 09:18
$a(n)$ is the Conway $10000 sequence. The problem seems extremely hard for a competition, and it is amazing that even one person solved it. It would be very interesting to see the solution! Also, which competition is SRMO?
14.05.2005 11:07
SRMO= Silk Road Mathematical Olympiad P.S. I'll send the solution soon.
16.05.2005 18:43
Omid, can you send your solution please? I'd like to see it very much as the problem is wonderful.
20.05.2005 15:14
Official solution: We first prove that \[a(n+1)-a(n)=1 \mbox\ \ \ \ {or } \ \ 0 \ \ \ \ \ (*)\] For $n\geq 1$. This is true when $n=1,2$ as $a(3)=2$. Let $n\geq3$ and assume that $(*)$ is true for all $k\leq n$. In particular $a(k) \leq k$ so the recursion formula is meaningful. Then: $a(n + 1) - a(n) = a(a(n)) - a(a(n - 1)) + a(n + 1 - a(n)) - a(n - a(n - 1)) \\ =a(n - a(n) + 1) - a(n - a(n))\ \mbox{if}\ \ a(n) = a(n - 1) \\ =a(a(n - 1) + 1) - a(a(n - 1))\ \mbox{if}\ \ a(n) = a(n - 1) + 1$ Now assume that $a(2n) \leq2a(n)$ is not true for all $n$ and let $m$ be the smallest integer for which this inequality is false. Hence $a(2m) > 2a(m)$ and $a(2(m - 1))\leq2a(m - 1)$. Moreover, if $a(m) = a(m - 1) + 1$, then $a(2m) > 2a(m) = 2(a(m-1)+1)\geq a(2(m-1))+2$ and we get a contradiction to $(*)$. Therefore $a(m) = a(m - 1)$ Let$ M = a(m) = a(m - 1)$. Since $a(2m) > 2M$ and $a(2m - 2) \geq 2M$, we have $a(2m - 1) = 2M$ or $2M + 1$. If $a(2m-1) = 2M$, then $a(2m) = a(2M)+a(2m-2M)\leq 2a(M)+2a(m- M) = 2a(m) $which contradicts with our assumption $a(2m) > 2a(m)$. If $a(2m - 1) = 2M + 1$, then $a(2m - 2) = 2M$, and $a(2m - 1) = a(2M) + a(2m - 1 - 2M) \leq a(2M) + a(2m - 2M) \leq 2a(M) + 2a(m - M) = 2a(m)$ which means $2M + 1 \leq 2M$, a contradiction. I hope I have no errors in typing it.
20.05.2005 21:49
Quote: We first prove that \[a(n+1)-a(n)=1 \ (*)\] This should say "$a(n+1) - a(n) = 0$ or $1$". Omid, thanks for the solution. Was it the same as the solution of student who solved the problem in SRMO? The only published proof of this inequality that I know, first constructs the sequence $a(n)$ combinatorially (!) and then gives the inequality as a consequence. It is interesting that there is a simple induction argument.
22.05.2005 12:43
Yes I corrected it
11.06.2005 16:02
Omid hagve you got another solution? If you have , please send me
12.06.2005 12:34
No It is the only solution I know
12.10.2019 06:18