[seqfan] Re: Interesting sequence

[Andrew Weimholt]

On 1/19/10, John W. Layman <layman at math.vt.edu> wrote:
> I came up with the following sequence recently and found it rather
>  interesting.
>
>  Number of subsets S of {1,2,3,...,n} with the property that if x is a
>  member of S then at least one of x-2 and x+2 is also a member of S:
>  {a(n)}={1, 1, 2, 4, 8, 16, 28, 49, 84, 144, 252, 441, 777, 1369, 2405,
>  4225, 7410, 12996, 22800, 40000, 70200, 123201, 216216, 379456, 665896,
>  1168561, 2050657, 3598609, 6315113, 11082241, 19448018, 34128964,...},
>  for n=1,2,3,...
>
>  Note the even-index bisection:  {1, 4, 16, 49, 144, 441, 1369, ...},
>  which gives the SQUARES of:
>  A005251 = {0, 1, 1, 1, 2, 4, 7, 12, 21, 37, ...}, n=0,1,2,..., beginning
>  with A005251(3).
[...]
>  It would be nice to have proofs of the "squares" observations pointed
>  out above.  Also formula or recurrence, etc. of {a(n)}.
>


The first comment for A005251 is
 a(n+3) = number of n-bit sequences that avoid 010.

It is also true that

 A005251(n+2) = number of n-bit sequences that avoid isolated 1's
 (including the ends of the sequence). For example, not only do we
 exclude sequences with "010", but we also exclude sequences
 begining with "10" or ending with "01".

Proof:

 Let a(n) = number of n-bit sequences that avoid isolated 1's.

 There is only 1 zero length sequence, and it meets our criteria,
therefore a(0)=1.
 The only 1-bit sequence that meets our criteria is "0", therefore a(1)=1.
 The only 2-bit sequences that meet our criteria are "00" and "11",
therefore a(2)=2.

 For n>2, to construct the sequences that meet our criteria, we can
 add a leading 0 to all of the (n-1)-length sequences, or we can add a
leading 1 to
 all of the (n-1)-length sequences which begin with 1, or we can add a
leading "11"
 to all the (n-2)-length sequences which begin with 0.

 As we can add a leading 0 to any (n-1)-length sequence, the number of
n-bit sequences
 beginning with 0 is simply a(n-1), and the number of n-bit sequences
beginning with 1
 is a(n)-a(n-1).

 So the formula for a(n), n>2 is
 a(n) = a(n-1) + (a(n-1)-a(n-2)) + a(n-3)

 rearranging...

 a(n) = 2a(n-1) - a(n-2) + a(n-3)

 equivalently, for n>3,
 a(n-1) = 2a(n-2) - a(n-3) + a(n-4)

 substituting the above for one of the a(n-1) terms in the formula for
a(n), we get

 a(n) = a(n-1) + a(n-2) + a(n-4)

Therefore

 a(n) = A005251(n+2)

-------------------------------------------

Now notice that our definition,

"number of n-bit sequences that avoid isolated 1's"

is equivalent to...

"number of subsets of {1,2,...,n} such that if the subset includes x,
then it includes at least one of x-1,x+1".

Just think of the bits in the binary strings as representing
the elements of {1,2,...,n}. Each binary string represents a
subset of {1,2,...,n}, and avoiding isolated 1's is equivalent
to avoiding subsets which include x without includign x-1 or x+1.

Now look at your sequence definition...

"number of subsets of {1,2,...,n} such that if the subset includes x,
then it includes at least one of x-2,x+2".

It is clear that no combination of odd members of the subset do not
affect even members nor visa versa, so we can redefine it as...

a(n)=b*c, where b=number of subsets of {1,3,5,...,2*floor((n-1)/2)+1}
which meet the x+-2 criteria
and c=number of subsets of {2,4,6,...,2*floor(n/2)} which meet
the x+-2 criteria

Clearly, these are equivalent to subsets of
{1,2,3...,floor((n-1)/2)+1} and {1,2,3,...,floor(n/2)}
which meet the x+-1 criteria.

So your sequence is given by

a(2*n)   = A005251(n+2) ^ 2
a(2*n+1) = A005251(n+2) * A005251(n+3)

Andrew