extending A005269

[Emeric Deutsch]

Dear seqfans,
a(n) is the number of sequences b_1,b_2,...b_n of length n 
such that b_1=b_2=1 and b_j <= b_{j-2}+b_{j-1} for all j>2.
They are called sub-Fibonacci sequences.
The A005269 entry in OEIS is given below.
With a Maple program I get very fast the first 10 terms of 
the sequence, relatively fast the 11th term 1067599 but 
the next term eludes me even after several hours of computer 
time.
I am not familiar with other programs like Mathematica, PARI, 
etc. I wonder if somebody is interested to work on this.

For the purpose of counting, it is sufficient to construct only 
the pair of the last two entries of a sub-Fibonacci sequence. Thus,
F_2 = [1,1];
F_3 = [1,1],[1,2];
F_4 = [1,1],[1,2],[2,2],[2,3];
F_5 = [1,1],[1,2],[2,2],[2,3],[2,2],[2,3],[2,4],[3,3],[3,4],[3,5];
(incidentally, offset should be 2 and first term in the present 
sequence should be dropped).
F_j contains the "mutilated" sub-Fibonacci sequences of length j.
Obviously, a pair can occur several times in F_j.
A pair p=[a,b] in F_j generates the following pairs in F_{j+1}:
[b,b],[b,b+1],...,[b,b+a].
For this, I am using in Maple the function 
f:=p->seq([p[2],p[2]+i],i=0..p[1]);
Then:
> F[2]:=[1,1]; a[2]:=nops([F[2]]); # initialization
yielding a[2]=1 and then
> for n from 3 to 10 do F[n]:=seq(f([F[n-1]][i]),i=1..a[n-1]):
a[n]:=nops([F[n]]): print(a[n]) od:
yielding very fast 2,4,10,31,127,711,5621,64049.

Emeric

ID Number: A005269 (Formerly M1234)
URL:       http://www.research.att.com/projects/OEIS?Anum=A005269
Sequence:  1,1,2,4,10,31,127,711,5621,64049,1067599
Name:      Number of sub-Fibonacci sequences of length n.
References Fishburn, Peter C.; Roberts, Fred S.; Elementary sequences,
           sub-Fibonacci sequences. Discrete Appl. Math. 44 (1993), no.
1-3, 261-281.
See also:  Adjacent sequences: A005266 A005267 A005268 this_sequence
A005270 A005271 A005272
           Sequence in context: A001647 A007177 A005268 this_sequence
A070900 A071954 A000736
Keywords:  nonn
Offset:    1
Author(s): njas