Golomb non decreasing sequence 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.
 A: 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.
A: 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)
