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$

closed as off-topic by Mark Sapir, Anthony Quas, YCor, David Handelman, Alexey Ustinov Jan 14 '18 at 9:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – YCor, David Handelman, Alexey Ustinov
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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.