MathDB

Let

x_1,\ldots,x_n

be a sequence with each term equal to

0

1

. Form a triangle as follows: its first row is

x_1,\ldots,x_n

and if a row if

a_1, a_2, \ldots, a_m

, then the next row is

a_1 + a_2, a_2 + a_3, \ldots, a_{m-1} + a_m

where the addition is performed modulo

2

(so

1+1=0

). For example, starting from

1

0

1

0

, the second row is

1

1

1

, the third one is

0

0

and the fourth one is

0

.
A sequence is called good it is the same as the sequence formed by taking the last element of each row, starting from the last row (so in the above example, the sequence is

1010

and the corresponding sequence from last terms is

0010

and they are not equal in this case). How many possibilities are there for the sequence formed by taking the first element of each row, starting from the last row, which arise from a good sequence?

Problem Statement