Recurrence relation for a strictly increasing sequence 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.
 A: 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.
A: 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}$$
A: 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$).
