A000120; another recurrence?

[FJ]

I'll get some notation out of the way first.
For any two sequences X={x_0,x_1,...} and Y={y_0,y_1,...}, let

X || Y={x_0,x_1,...,y_0,y_1,...},

the concatentation of sequence X onto the left of sequence Y.

Also let S(X)={x_i+1}, the shifting of a sequence.  So S^0(X)=X, and in general, S^p(X)={x_i+p}.  Note that S(X || Y) = S(X) || S(Y).

Okay, now that that is out of the way, we have the important bit.
Let L_k, for positive integers k, be a finite sequence such that

L_1 = {0,1} and L_{k+1} = L_k || S(L_k).

For example,

L_3 = L_2 || S(L_2)
= L_1 || S(L_1) || S(L_1 || S(L_1))
= L_1 || S(L_1) || S(L_1) || S^2(L_1)
= {0,1,1,2,1,2,2,3}.

L_k seems to be the first 2^k terms of sequence A000120.  The question is, how can I go about proving this?

-Francois.

_______________________________________________
No banners. No pop-ups. No kidding.
Make My Way  your home on the Web - http://www.myway.com