Below is a problem, from an old Silk Road olympiad.
Define an infinite sequence, $a(n)$, such that, $a(1)=a(2)=1$; $$ a(n)=a(a(n-1))+a(n-a(n-1)),\forall n\geq 3. $$ Show that, for every $n\geq 1$, $a(2n)\leq 2a(n)$.
$\begingroup$
$\endgroup$
15
-
1$\begingroup$ Then this context should be included, if you want to convince people here that this does not belong on another site as it is at first sight. Also, when you define something as definition by induction, but it's not clear that this is well-defined, writing explicitly that it's indeed well-defined (if so) would show that you have thought about the problem, and not just copying the statement of an exercise as it regularly occurs here. $\endgroup$– YCorCommented Jan 14, 2018 at 4:02
-
1$\begingroup$ It is obviously well defined because $a(n+1)$ is either equal to $a(n)$ or to $a(n)+1$ for every $n$, so $a(n)< n$ for $n\ge 2$. But this site is not for olympiad problems. $\endgroup$– user6976Commented Jan 14, 2018 at 4:05
-
2$\begingroup$ Wikipedia (en.wikipedia.org/wiki/Hofstadter_sequence) calls this the Hofstadter–Conway \$10,000 sequence. $\endgroup$– Gerry MyersonCommented Jan 14, 2018 at 5:16
-
1$\begingroup$ See also OEIS sequence A004001. $\endgroup$– Robert IsraelCommented Jan 14, 2018 at 5:22
-
1$\begingroup$ That gives some justification of the existence of this question on mathoverflow. $\endgroup$– Fan ZhengCommented Jan 14, 2018 at 5:45
|
Show 10 more comments
1 Answer
$\begingroup$
$\endgroup$
1
This is too long for a remark, but if you look at $N_m=\#\{n:a_n=m\}$, the sequence $\{N_m\}$ is
2
2
1 3
1 1 2 4
1 1 1 2 1 2 3 5
1 1 1 1 2 1 1 2 1 2 3 1 2 3 4 6 ...
To get each line from the line above it, replace each term $N$ by $1,2,\dots,N$, and then add 1 to the final term.
Not sure if this observation helps in any way.
-
$\begingroup$ Yes, it is page 18 in MR1083608 . $\endgroup$– user6976Commented Jan 14, 2018 at 8:31