16.6.1. Recurrence Condition

Let $a_n$ denote my function which is the number of valid sequences ending with $n$. A trivial recurrence condition for $a_n$ is $a_n = a_{n-1} + a_{n-2} + ... + a_1$. This is because the second last value in the sequence, namely $k$, can be $1$. If that is the case, then I am saying find out all possible sequences starting and ending with $1$ and append it with the value $n$. That gives one category of valid sequences starting with $1$ and ending with $n$.

In this section, we introduce the concept of valid sequences that adhere to certain rules. We denote the number of valid sequences that end with a specific number $n$ as $a_n$. The recurrence condition states that the number of valid sequences ending with $n$ can be derived by looking at all sequences that end with the previous possible values (from 1 to $n-1$). The idea is to build up sequences by appending the number $n$ to sequences that can end with numbers less than it, hence forming the expression $a_n = a_{n-1} + a_{n-2} + ... + a_1$. This can be thought of as a way to count how many sequences exist with specific end values.

Imagine you are building a staircase. Each step on the staircase represents a number in the sequence. Starting from the ground (step 0), you can reach the first step (1) from the ground itself (1 way). To reach the second step (2), you can either step from the first step (1) or from the ground (0). The same applies to further steps; you can step on the current step from any of the previous steps, illustrating how one can determine valid paths to reach the top of the staircase.

How many such sequences can you have? You can have $a_n$ such sequences. Or $k$ can be $2$. In that case, find out all valid sequences starting with 1, ending with 2, and which is a strictly increasing sequence and in each such sequence you put an $n$ at the end... And all these categories of sequences that we have discussed, they are disjoint.

When considering the number of valid sequences that can end with a specific number, we categorize them based on their starting and ending points. For example, if the last number in a valid sequence is 2, we can generate sequences that begin with 1 and extend them by appending 2. Each such category of sequences is considered individually, hence they are disjoint from one another, meaning there is no overlap between the categories. This organization helps in simplifying the counting process.

Think of organizing books on a shelf. You have different categories for fiction, non-fiction, and science fiction books. No book belongs to more than one category (these are your disjoint sets). Now, if you want to understand how many arrangements you can have, you would look at each category separately, just like counting the sequences allows you to see each potential sequence composed of valid numbers.

We want a more compact recurrence condition. Compact in the sense, the degree of this equation that we had just formulated is $n-1$. We want a more compact recurrence condition. So let us derive that alternate recurrence equation.

The goal is to simplify the recurrence condition by deriving a more compact relation that relies on fewer previous terms. The original recurrence condition depended on multiple terms (specifically, all terms from 1 to $n-1$). In contrast, a more compact relation would ideally depend only on the immediately preceding term, thus reducing complexity in both calculation and understanding.

Consider a recipe that requires multiple steps to complete a dish. If you can create a simpler version of the dish that only requires fewer steps without losing the essence of the dish, you've essentially created a more compact recipe. Similarly, in mathematics, we aim to reduce our dependencies to simplify calculations while preserving the accuracy of outcomes.

So our alternate recurrence equation will be $a_n = 2 * a_{n-1}$. Now this is an equation of degree 1 because now the dependency of the n-th term is only on the previous term.

After simplifying, we arrive at a more manageable recurrence relation, which states that the number of valid sequences ending with $n$ is twice the number of sequences that end with $n-1$. This compact form significantly eases the computation since now we only need values from one previous term instead of many, making it easier to observe patterns or calculate values as needed.

Imagine a factory producing products. Instead of needing separate resources for every step (like materials for each previous model), you find that each new model only needs double the resources of the last one, simplifying your supply chain management significantly.

It turns out that even though this equation is of degree 1, we need 2 initial conditions. $a_1 = 1$ because if $n = 1$ there is only 1 sequence which is strictly increasing starting with 1 and ending with 1.

Initial conditions in recurrence relations are crucial as they provide a starting point for the calculations. Here, we see that even a simplified equation needs a specific context for its calculations to hold true. Our equations rely on knowing the values for the simplest forms of our sequences—this establishes a foundation upon which all subsequent values can be built.

Think of teaching a child to count. You start with 1. Without understanding that base (1 in this case), it’s difficult to explain how to count further. Teachers build on initial knowledge to expand understanding, much like we build on initial conditions to expand our sequence calculations.

--