1
$\begingroup$

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)$.

$\endgroup$
  • 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$ – YCor Jan 14 '18 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$ – Mark Sapir Jan 14 '18 at 4:05
  • 2
    $\begingroup$ Wikipedia (en.wikipedia.org/wiki/Hofstadter_sequence) calls this the Hofstadter–Conway \$10,000 sequence. $\endgroup$ – Gerry Myerson Jan 14 '18 at 5:16
  • 1
    $\begingroup$ See also OEIS sequence A004001. $\endgroup$ – Robert Israel Jan 14 '18 at 5:22
  • 1
    $\begingroup$ That gives some justification of the existence of this question on mathoverflow. $\endgroup$ – Fan Zheng Jan 14 '18 at 5:45
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, it is page 18 in MR1083608 . $\endgroup$ – Mark Sapir Jan 14 '18 at 8:31

Not the answer you're looking for? Browse other questions tagged or ask your own question.