Note: This is a rework of an effort I made over a year ago. It wasn't my intention but I wound up developing the fundamental background to understanding finite cardinals.
I do not think this proof uses induction.
We use the notation $[n] = \{0,1,\ldots,n-1\}$
Recall the following fact:
Proposition 1: Let $f: A \to B$ be a function and $\beta: B \to B$ be a bijective transformation of the target. Then $f$ is $\text{1:1}$ if and only if $\beta \circ f$ is $\text{1:1}$.
Proposition 2: If $\tau: [j] \to [k]$ is an injection, then $j \le k$.
Proof
For any injection $\sigma: [j] \to [k]$ let $S(\sigma) = max(\{s \, | \, \sigma(t) = t \text{ for } t \le s\}$. For the injection $\tau$, let
$\tag 1 T = max(\{S(\beta \circ \tau \, | \, \beta \text{ is a bijective transformation of } [k]\}$
The integer $T$ must be equal to $j-1$. Assume to get a contradiction that $T \lt j-1$ and select a transformation so that $S(\beta \circ \tau) = T$. Let $\beta \circ \tau (T+1) = u$, so that $u \gt T$. Let $\rho$ be the transformation that interchanges $u$ with $T + 1$. Then $S(\rho \circ \beta \circ \tau) \ge T+1$, which is absurd.
We have shown the existence of an insertion $\iota: [j] \to [k]$, so $j \le k$. $\quad \blacksquare$
Proposition 3: If there is a bijective correspondence $f$ between $[n]$ and a set $B$, then there is no injective mapping $g$ from $[n+1]$ into $B$.
Proof
Assume $g$ is injective and consider the function $f^{-1} \circ g$. By proposition 2, $n+1\le n$, but that doesn't make sense. $\quad \blacksquare$
Using the above theory it is easy to show the following theorem:
Theorem 4: If a set $B$ is finite then there exists a $C \in \mathbb N$ such that for $m \lt C$ there exists proper injections from $[m]$ into $B$, for $m = C$ there exist a bijection between $[C]$ and $B$, and for $m \gt C$ there exists no injections from $[m]$ into $B$.
The following is now also easy to prove:
Proposition 5: If $B$ is not a finite set, then for every $m \ge 0$ the set $[m]$ can be non-surjectively injected into $B$.
Proposition 6: If $A$ is a finite set and $B$ is a subset, then $B$ is finite.
Proof
Assume, to get a contradiction, that $B$ in not finite. Let $f: A \to [n]$ be a bijective mapping. By proposition 5, there is an injection $g:[n+1]\to B$. Since we can naturally insert $B$ into $A$, we have an injection from $[n+1]$ to $[n]$. By proposition 2, this is impossible. $\quad \blacksquare$