21.1.4. Proof Strategy

The proof strategy will be the following. We will first find out the cardinality or the number of sequences consisting of n 1s and n -1s without any restriction. So, that means let A denote the set of sequences of n 1s and n -1s with no restriction. Then the set A has all the sequences where the partial sums are greater than equal to 0, as well as it has all the sequences where the partial sum at every k may not be greater than equal to 0.

In the first part of the strategy, we establish set A, which contains all possible sequences composed of n instances of 1 and n instances of -1, without any restrictions on their arrangement. Set A includes valid sequences (where the partial sums are non-negative at all positions) and invalid sequences (where there are positions with negative partial sums). We need to distinguish between these two kinds of sequences to find the valid ones later.

Imagine you have a basket with 10 apples (1s) and 10 oranges (-1s). The total number of ways you can arrange these fruits is like set A, which includes all possible combinations of apples and oranges regardless of whether there's a 'negative' moment (too many oranges at first).

And then we will find out the set B of all bad sequences and by bad sequences I mean the sequences consisting of n number of 1s and n number of -1s which violate the restrictions. And of course then it is easy to see that the required value or value of the required number of sequences of n 1s and n -1s where the partial sums are greater than equal to 0 will be the difference of the cardinality of the A set and the B set.

Next, we introduce set B, which contains bad sequences—sequences that have at least one point where the sum of numbers is negative (partial negative sums). To find the valid sequences (where the partial sums never drop below zero), we can simply subtract the count of invalid sequences (set B) from the total possible sequences (set A). This subtraction will highlight the sequences that remain valid.

Continuing with the basket analogy, suppose you identify which arrangements of apples and oranges create a situation where you pick an orange first (negative sum). Those arrangements are like the bad sequences we want to avoid. By counting all the arrangements and then only counting the arrangements that start with an apple, we can figure out the successful combinations.

So, it is easy to see that the cardinality of the A set is C(2n, n). This is because, what is the set A? It is the set of all sequences with n number of 1s and n number of -1s where we do not put any restriction whatsoever over the partial sums in the sequences.

We compute the size of set A, denoted as C(2n, n), which represents the total number of ways to choose n positions out of 2n for the 1s. The remaining positions will automatically be filled with -1s. This combinatorial function reflects the total combinations of arrangements of 1s and -1s without any restrictions.

Visualize it as choosing 5 positions out of 10 to place apples in a row of fruits (which also include oranges). The total number of ways you could arrange them, without any limitations on their order, is akin to counting all possible sequences in set A.

Now for the rest of our discussion our focus will be to find out the cardinality of the set of bad sequences and what is a bad sequence? A sequence is a bad sequence if it consists of n number of 1s, n number of -1s such that in such sequence there is at least one occurrence of a partial negative sum.

Here, we aim to determine the number of bad sequences that have at least one negative partial sum. We use a technique called the reflection method to identify these sequences effectively. The reflection method allows us to create a one-to-one correspondence between bad sequences and a different sequence type, which will help us count them more easily.

Think of it like a game where you are following a set of rules. If you break a rule (negative partial sum), you want to reflect on what caused the break (using the reflection method). By identifying those problematic moments in your journey (bad sequences), you can better understand how to avoid them in future games.

Now, let us count the number of 1s and -1s in the sequence S’ where the occurrence of partial negative sum is there namely if I focus on the portion of the sequence till the rth position, then I know that the number of -1s is more than the number of 1s by one position.

In this section, we establish that when we reflect a bad sequence, we create a reflective sequence that preserves the nature of bad sequences. An injective mapping means that each bad sequence corresponds uniquely to a new sequence, ensuring we do not double count any bad sequence nor miss any. The specifics of the relationship between the two sequences help us examine their properties.

Picture a mirror reflecting your image. Each unique posture or movement you make is precisely mirrored. If you take a position that would convey a negative message (a bad sequence), its reflection would be uniquely heightened, clearly indicating your exact stance. This unique connection reflects the injective nature of our sequence mapping.

Now what we will prove is that the above process of converting any bad sequence S to a corresponding sequence S’ is also a surjective mapping.

Here, we show that every possible sequence in set C corresponds back to at least one bad sequence in set B, signifying surjective mapping. This means that for any sequence formed with two extra 1s than -1s, we can trace back to a bad sequence indicating the existence of a negative partial sum.

Suppose you've set out to discover all types of scenic routes (set C). Each of these scenic routes must have originated from a specific starting point (set B). By ensuring that each scenic route can trace back to a starting point, you confirm that every journey has its roots in something, validating your exploration is complete and comprehensive.

--