Prove that $ \text{Inc}(n,m) = \text{Inc}(m-1, m) \circ \text{Inc}(n, m-1)$ Let $n, m \in \mathbb N$ and also let $n \leq m$, we define the set: $$\text{Inc}(n,m): = \{f: \{1,...,n\} \to \{1,...,m\} \mid f \text{ strictly increasing}\}.$$
I am trying to prove (for $n<m$ I think) that such increasing functions on a subset of the integers satisfy the following property:

$$ \text{Inc}(n,m) =  \text{Inc}(m-1, m) \circ \text{Inc}(n, m-1)$$
  Where the circle denotes composition of maps.

One direction was of course easy, namely composition of two increasing functions is again increasing. If  $fg \in \text{Inc}(m-1, m) \circ \text{Inc}(n, m-1)$, for $f \in \text{Inc}(m-1, m)$ and $g \in \text{Inc}(n, m-1)$. First $g$ maps the set $\{1, \dots, n\}$ to the set $\{1, \dots, m-1\}$, for $n<m$. Then $f$ maps from the set  $\{1, \dots, m-1\}$ to the  set  $\{1, \dots, m\}$. We see that the domain and range are as desired.  We also see both functions are increasing therefore their composition is as well. We then have that $fg \in  \text{Inc}(n,m) $.
I was having trouble breaking an increasing function up into two maps, the other way around. So given  $h \in \text{Inc}(n,m) $, find some decomposition $h= s \circ t$ such that each map lies in the respective set. 
 $$t: \{1, \dots, n\} \to \{ 1, \dots , m-1\}.$$
$$s: \{ 1, \dots , m-1\} \to\{ 1, \dots , m\}.$$
I was think about letting the first one just be $h$ piecewise until a certain point and then let the second one be linear up to where that one stops, something like:
$$t(i):= \begin{cases} 
      h(i) &  \text{ if } i \leq n-1 \\
      \dots & \text{ if } i=n
   \end{cases}. $$
$$s(i):= \begin{cases} 
      i &  \text{ if } i < t(n) \\
      h(i) & \text{ if } i \geq t(n)
   \end{cases}.$$ 
This does not quite work out as $h(i)$ might not be defined for some values and I cannot find a good spot to connect the two, any suggestions?
 A: Let $j\in \{1, \dots, n \}$ such that $h(j) >j$. If such a $j$ does not exist, we know that $h$ must be the natural embedding and this means that $\forall i \in \{ 1, \dots, n\}$ we have  $h(i)=i$. In this case we may decompose $h=s\circ t$ where: 
$$t(i)=i \quad \forall i \in \{ 1, \dots, n\}$$
$$s(i)=i,  \quad \forall i \in \{ 1, \dots, m-1\}.$$ 
Clearly these functions are increasing and their composition gives $h$ hence $h \in  \text{Inc}(m-1, m) \circ \text{Inc}(n, m-1)$.
Suppose now such a smallest $j$ exists such that $h(j)>j$. Since this is the smallest $j$ we also know that before this index occurs we must have $h(i)=i$, as $h$ is an increasing function. We define $t: \{1, \dots, n\} \to \{ 1, \dots , m-1\}$ as follows:
$$t(i):= \begin{cases} 
      h(i) &  \text{ if } i <j \\
      h(i)-1 & \text{ if } i \geq j
   \end{cases} .$$ 
Next we define  $s: \{1, \dots, m-1\} \to \{ 1, \dots , m\}$
$$s(i):= \begin{cases} 
      i &  \text{ if } i < k(n) \\
      i+1 & \text{ if } i \geq k(n)
   \end{cases} .$$
Again we claim that $h= s\circ t$. Observe  if $i < j$ we have : $s(t(i)) = s(i) = i = h(i)$
if $i \geq j: s(t(i)) = s(t(i)) = s(h(i)-1) = h(i) - 1 + 1=h(i)$ since $h(i)-1 \geq h(j)-1.$
One can now argue that $s$ and $t$ are both increasing functions.
