# Prove that a strictly monontone increasing sequence in $\Bbb{N}$ is greater or equal than its index.

Prove that for a sequence $(n_k)_{k\in\mathbb{N}}$ in $\mathbb{N}$, with $(n_k)$ strictly monotone increasing, $n_k\geqslant k$, for all $k\in\mathbb{N}$.

I started with noticing that $n_0\geqslant 0$ and $n_1>n_0$, so $n_1\geqslant1$. So we see that $n_k\geqslant k$ for $k=1$ and $k=2$. Now, suppose that $n_j\geqslant j$ for $j=\{0,1,\dotsc,k\}$. We see that $n_{k+1}>n_k\geqslant k$.

But from here I'm stuck. Does anyone have something to keep me going?

• Go by induction. Let $n$ be the least index such that $a_n<n$. Derive a contradiction. – lulu Jun 14 '18 at 11:01
• Well, $n_{k+1}$ is a natural number strictly greater than $k$, and the smallest natural number (strictly) greater than $k$ is $k+1$, so $n_{k+1}$ is greater than or equal to $k+1$, and the conclusion follows. – SystematicDisintegration Jun 14 '18 at 11:06

Since $n_{k+1}>n_k$ and $n_k\ge k\implies n_{k+1}>k\implies n_{k+1}\ge k+1$
Note that $(n_k)$ is strictly increasing so $n_{k+1}> n_k$
And since $n_k\ge k$
So we must have $n_{k+1}>n_k\ge k$
Now since $n_k\in \Bbb N$ for each $n\in \Bbb N$ and $n_{k+1}>k$ we must have $n_{k+1}\ge k+1$