Given a book with $100$ pages and a $100$ lemmas, prove that there is some lemma written on the same page as its index

A book consists of 100 pages and contains 100 lemmas and some images. Each lemma is at most one page long and can't be split into two pages (it has to fit in one page). The lemmas are numbered from 1 to 100 and are written in ascending order. Prove that there must be at least one lemma written on a page with the same number as the lemma's number.

If lemma no. $1$ is written on page $1$, then it is proved. Let's assume lemma no. $1$ is written on page $k, k>1$. Then on at least one page there must be $2$ lemmas. Let's assume that always on page $k+i$ we have lemma no. $i+1$ and so on. Then the last $100-k-i$ lemmas must fit on the last page, which means that there will be at least one lemma (number $100$) on page $100$.

But I don't know how to express it in a more mathematical way!

Any help?

We claim more generally that a book of $n$ pages and $n$ lemmas numbered $1$ through $n$ has at least one lemma on a page matching its number.

Proof by induction on $n$: The case $n=1$ is obvious. Now suppose the statement is true for some $n$, and suppose we have a book of $n+1$ lemmas and $n+1$ pages. If lemma $n+1$ is on a page numbered less than $n+1$, then lemmas $1$ through $n$ must be on pages $1$ through $n$, and there must be at least one lemma on a same-numbered page by the inductive hypothesis. If not, then lemma $n+1$ is on page $n+1$, and we're done.

For each page $i$ assign a number $p(i)$ that defines the highest number of lemma printed on all pages starting from page 1 up to page $i$ (inclusive). So if we have lemmas 3, 4 and 5 printed on page 12, with page 13 having images only: $p(12)=p(13)=5$.

We have the following sequence:

$$p(1), p(2), \dots, p(100)=100\tag{1}$$

If $p(1)\ge1$ it means that lemma 1 is printed on the first page and we are done.

Let us consider a case when $p(1)=0$ (which basically means that the first page is reserved for images only).

The sequence of page numbers $i$ is strictly increasing and the sequence of values $p(i)$ is non-decreasing. Both sequencies have the same number of items (100), with $p(1)<1$ and $p(100)=100$.

Because of that we must have a pair of consecutive pages $i,\space j=i+1$ such that:

$$p(i)<i$$

$$p(j)\ge j$$

This basically means that lemma $j$ is not printed on page $i$ or on any other page before it. It is actually printed on page $j$ and this completes the proof.

Slight rephrasing of Oldboy's argument:

Let $a_i = i - p_i$, where $p_i$ is the page number of lemma $i$.

Then $a_1 \leq 0$, $a_{100} \geq 0$, and $a_{i+1}-a_{i} \leq 1$. Thus $a_i$ must be $0$ for some $i$.

Here's a slightly amended proof by induction, which I hope will make the induction step more obvious.

Let $P_n$ be the proposition that for a book with $n$ sequentially numbered pages and $n$ or more sequentially numbered lemmas, at least one lemma is on a page with the same number as the lemma.

Suppose $P_n$ is true for some $n=k$, and consider the case of $k+1$ pages and $k+1$ lemmas. To avoid being on its own-numbered page, lemma $k+1$ has to be somewhere in the first $k$ pages, and to keep the lemmas in sequence, no other lemma can go on page $k+1$.

We therefore have to fit all $k+1$ lemmas onto the first $k$ pages. By $P_k$, this puts at least one of them on its own-numbered page.

So wherever lemma $k+1$ is, at least one lemma is on its own-numbered page.

Clearly this remains true if we add more lemmas without adding more pages. That is, with $k+1$ pages and $\ge k+1$ lemmas, at least one lemma is on its own-numbered page: ie $P_{k+1}$ holds. That is, if $P_n$ is true for $n=k$, it is also true for $n=k+1$.

Now consider the case of $1$ page and $\ge 1$ lemmas. Clearly lemma 1 is on page 1, so $P_1$ is true. Therefore, by induction, $P_n$ is true for all $n\ge 1$.

Finally, putting $n=100$ proves the case in the original question.