Recurrence relation for a strictly increasing sequence

Question

Find a recurrence relation for the number of strictly increasing sequences of positive integers such that the first term is 1 and last term is $n$, where $n$ is a positive integer. The sequence is: $a_1$, $a_2$, $a_3$, ... , $a_k$ and $a_1=1$, $a_k=n$ and $a_{j-1}$ < $a_j$ where $j=1,2,3, ... , k-1$.

Here $a_{j-1}$ means the $(j-1)th$ term of the sequence. The solution considers two cases when $a_{k-1} = n-1$ and when $a_{k-1} < n-1$.

I don't understand why two cases are considered.

Answer 1

Let $f_n(m)$ be the number of $m$-length sequences with first term $1$, last term $n$.

A sequence of length $m$ which ends at $n$ is precisely one of the following two disjoint possibilities:

• A sequence of length $m-1$ which ends at $n-1$, with $n$ appended
• A sequence of length $m-1$ which ends at something less than $n-1$, with $n$ appended

The first case: there are $f_{n-1}(m-1)$ options for this.

The second case: there is one option for each of the $n-1$ ending points. Therefore, there are $f_1(m-1) + f_2(m-1) + \dots + f_{n-2}(m-1)$ options.

That is, $f_n(m) = \sum_{i=1}^{n-1} f_i(m-1)$.

The initial conditions are that $f_n(n) = 1$, $f_n(m) = 0$ if $m > n$, and $f_n(1) = 0$.

To be honest, I'm not really sure why they've asked you to split it into those two cases. It's a very artificial distinction.

Answer 2

Denote the number of $k$ sequences in $[1, n]$ by $s_{n, k}$. Then we have two cases:

• $n - 1$ is part of the sequence: There are $s_{n - 1, k - 1}$ sequences of those, just chop off $n$
• $n - 1$ is not part of the sequence: There are $s_{n - 1, k}$ such ones, you can just shift the end one down.

In all:

$$s_{n, k} = s_{n - 1, k} + s_{n - 1, k - 1}$$

As boundary conditions you have that $s_{n, 2} = 1$ for all $n \ge 2$, and that $s_{n, n} = 1$ for all $n \ge 2$.

It is easy to see that:

$$s_{n, k} = \binom{n - 2}{k - 2}$$

Answer 3

Let $H_n$ be the number of these sequences.

Each sequence ending in $n$ either has $n − 1$ in it or it doesn’t. By removing the last term from a sequence that has $n−1$ in it, you’re left with an increasing sequence starting at $1$ and ending at $n−1$, of which there are $H_{n−1}$. If the sequence doesn’t have an $n − 1$ in it, then replacing $n$ with $n − 1$ leaves an increasing sequence starting at $1$ and ending at $n − 1$, of which there are $H_{n−1}$. So $H_n = 2H_{n−1}$.

There is one sequence starting at $1$ and ending at $2$, so $H_2 = 1$ (it doesn’t make sense to start with $H_2$).