21.1.13. Injective Mapping Proof

So, our first claim is that in this bad sequence S the value at the position r is definitely –1. And this is because as per our assumption the partial sum namely the summation of the first r – 1 values is greater than equal to 0. So, that means that if a; so remember by the way that at rth position we can have either + 1 or –1. So, if s is greater than equal to 0 and if my rth value the rth position is + 1 then definitely s will also be positive. But that goes against the assumption that s namely the partial sum at rth position is negative.

This chunk introduces the key elements of the proof, which involves defining sets A and B. Set A represents all possible sequences of n 1s and n -1s without restrictions, while set B includes only those sequences that violate the condition that their partial sums must remain non-negative. The argument establishes the behavior of the partial sums, specifically that the first negative partial sum occurs at position r and hides the implied structure of valid sequences that we’re interested in. The next steps will hinge upon what happens at position r.

Imagine you are stacking blocks, where each block is either a 1 (a positive action) or a -1 (a negative action). You can only build your tower so high without it falling over (the partial sum must stay non-negative). Now, you notice that at a certain point, your tower threatens to collapse (you get a negative sum). The position where it first threatens to collapse is like our r—the moment that tells us we’re in trouble. This sets the stage for identifying which blocks are responsible.

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. ... So, our goal will be to show the existence of a bad sequence which has equal number of 1s and –1s and which has at least one negative partial sum.

Here, we further clarify what a bad sequence is: one that has an equal number of 1s and -1s but has at least one point where the sum dips below zero. This further segments our analysis and allows us to target sequences that aren't valid. The idea of 'reflection' begins to take shape, as indicated by the need to create images (or counterparts) of these bad sequences to visually or mathematically represent their properties.

Think of this as following a budget while planning a party. Each time you spend (a -1), you need to keep your expenses within your budget (the sum). If you overspend (the first negative partial sum), it indicates the party planning is going in the wrong direction. Capture this idea of 'bad planning'—you still want to work with equal means (1s and -1s), but you've made decisions that led to budget issues (negative sums).

So, now what we will show is that the cardinality of the set B is C(2n, n + 1) and if we subtract the cardinality of B from the cardinality of A then we will get our required answer.

The reflection method is introduced as a technique for predicting the number of bad sequences. In essence, for every bad sequence marked by a first negative partial sum, we can construct a corresponding valid sequence that shows how close we are to violating our summation rule. When we calculate these sequences as C(2n, n+1), and subtract them from the unrestricted set A, we can derive the count of valid sequences, which matches Catalan numbers.

Imagine you're at a racetrack. C(2n, n) represents all potential race scenarios while B (the bad ones) marks the races that end with a crash (negative sums). The reflection method shows us how many of those crashes could have been avoided by adjusting the race strategy. By analyzing what happens to the crashes, we find strategies that help us run a safe race, thus aligning with the positive outcomes expressed in Catalan sequences.

--