Let $n$ be a natural number greater than 1. Let $M$ be set of intervals $[a,b], a,b \in\mathbb{N}, 1 \leq a < b \leq n$ such that for $I,J \in M$ either $I$ and $J$ are disjoint either one is a subset of the other one. Prove by induction that $M$ can contain at most $n-1$ such interval.
It is easy for $n=2$.
Can anyone help with step in induction?
Thanks in advance.
Suppose it works for n. Let $M$ be the set of intervals contained in $[1,n+1]$. If all those intervals are of shape $[a,b]$, where $b<n+1$, then all of them are contained in $[1,n]$ and we can apply i.h. to get $|M|\leq n-1 < n$. If not, there is some interval $I=[k,n+1]$ in $M$. Now we count other elements of $M$.
They can be subsets of $[k,n+1]$, there are at most $n-k+1$ of those, by i.h. ; or they can be subsets of $[1,k-1]$ (not of [1,k] because of disjoint intersection condition) and there are at most $k-2$ of them. There is another kind of those subsets- subsets containing $[k,n+1]$, but there are in 1-1 correspondence with subsets of $[1,k-1]$ (we can't have $[1,k-2]$ and $[k-2,n+1]$ at the same time).
This means we have at most $(n-k+1)+(k-2)+1=n$ intervals.