Question

How many ±1-sequences of length n are there?For example, (1, −1, −1, 1) is not a happy sequence, because although 1 ≥ 0 and 1 − 1 ≥ 0,the sum 1−1−1 is negative, so the condition fails for k = 3.

Answer 1

First of all there are sequences with entries as each entry has 2 choices - +1 or -1.

Now we calculate the number of happy sequences of length n. Let the number of happy sequences of length n be

First case: n is even

Then, Consider. Since is odd, for all happy sequences of length , the sum of all entries is positive. So the last entry can be both +1 or -1. So, for this case for all n even.

Second Case : n is odd

Then n-1 is even. We now look at all the happy sequences of length n-1. :

Let The sum of all entries is zero. Then there are same number of +1 and -1. So then it is the number of Dyck Words of length n-1, which is given by . So the last entry has to be +1.

Sofor all n odd. Solving the two recursions we get the desired answer. Base case, .