Question

Find the first four terms of the sequence (an)n≥1 with the given definition. Determine if they are potentially arithmetic or geometric.

(a) an is the number of n-bit strings which have more 1’s than 0’s. (Also, write down the strings for n ≤ 4.)

(b) an is the number of n-bit strings in which the number of 1’s is greater than or equal to the number of 0’s in every prefix. For example, 010111 would not qualify, since the prefix 010 has more 0’s than 1’s. (Also, write down the strings for n ≤ 4.)

(c) an is the number of lattice paths from (0, 0) to (n, n). (Refer to Section 1.2 if you need a refresher on lattice paths.)

Answer 1

a) as 1 is the only such string

as 11, 10, 01 are the only such strings

as 111, 110, 011, 101 are the only such strings

as 1111, 1110 etc are the only such strings

This seems potentially geometric as half the number of bit-strings of length n are of the type that the required property holds

b) as 1 is the only such string

as 11, 10 are the only such strings

as 111, 110, 101 are the only such strings

as 1111, 1110, 1101, 1011, 1100, 1010, 1110 are the only such strings

This might be geometric again as the jump from is to large for a linear function

c) Number of lattice paths from (0,0) to (n,n) corresponds to choices at each step to move left/right/up/down

This number seems to be exponential in nature as we have several possibilities for each step (in terms of direction to take)

Hope this was helpful. Please do leave a positive rating if you liked this answer. Thanks and have a good day!