Golomb sequence is a non-decreasing integer sequence where n-th term is equal to number of times n appears in the sequence. It's recursive formula is given by :
G(1) = 1
G(n+1) = 1 + G(n + 1 - G(G(n)))
It will be very helpful if someone can just explain this recursion and not any kind of closed form solution. I am stuck on this for a few days but still nothing comes to my mind that will explain this recursive formula.
On
Let $N=\{1,2,\ldots\}$ be the set of natural numbers.
$G$ is non-decreasing and $G(1)=1$ by definition, so $G(i)\geq 1$ for all $i\in N$. Now, by definition $G(i)$ is the number of times that $i$ appears in $G$, so the fact that $G(i)\geq 1$ implies that every positive integer $i$ appears in the sequence.
The fact that $G$ is non-decreasing and the fact that all natural numbers appear in $G$ together imply that either $G(n+1)=G(n)$ or $G(n+1)=1 + G(n)$ for all $n\in N$. Assume that $n>1$. There are two cases.
Case 1: $G(n+1)=1+G(n)$.
Let $i=G(n)$. Then $i$ appears in $G$ $G(i)$ times. The last time that $i$ appears in $G$ is the $n$th entry in the sequence. More formally $\max\{k|G(k)=i\}=n$. Also, we know that the first time $i$ appears in G is at $n-G(i)+1$. More specifically, $i=G(n)=G(n-1)=\cdots=G(n-(G(i)-1))$ and $G(n-G(i))=i-1$. Note that $$ G(n)=G(n-(G(i)-1)) = G(n+1-G(i)) = G(n+1-G(G(n))). $$ So, we can conclude that $$ G(n+1) = 1+G(n) = 1+ G(n+1-G(G(n))). $$
Case 2: $G(n+1)=G(n)$.
Case 2 seems to be a bit longer, so, if I have time, I will try to write a proof later. (Sorry)
Let's look at the first few terms, step-by-step:
$G(1) = 1$
$G(2) = 1 + G(2 - G(G(1))) = 1 + G(2 - G(1)) = 1 + G(2-1)=1+G(1)=1+1=2$
$G(3) = 1 + G(3-G(G(2)) = 1+G(3-G(2))=1+G(3-2) = 1+G(1)=1+1=2$
$G(4) = 1+G(4-G(G(3))=1+G(4-G(2))=1+G(4-2)=1+G(2)=1+2=3$
$G(5) = 1+G(5-G(G(4))=1+G(5-G(3))=1+G(5-2)=1+G(3) = 1+2 = 3$
$G(6) = 1+G(6-G(G(5))=1+G(6-G(3))=1+G(6-2)=1+G(4) = 1+3 = 4$
etc.