For example, let's prove that if $\{a_n\}_{n \in \mathbb{N}}$ is not bounded above, then there exists a subsequence $\{ a_{k_n} \}_{n \in \mathbb{N}}$ that diverges to $+\infty$.
Suppose $\{a_n\}$ is not bounded above. Set $k_0 \in \mathbb{N}$ such that $a_{k_0} > 0$. Among the terms $a_n$ for $n > k_0$, there must be some $a_q > 1$ for $q > k_0$ (else the sequence is bounded above by $\max \{1, \max \{a_n : n \leq k_0\}\}$). Set $k_1 = q > k_0$. Now assume for some $\beta \geq 1$ we have a subsequence $(a_{k_0}, a_{k_1}, \dots, a_{k_\beta})$ such that $a_{k_j} > j$ for each $j \in \{0, \dots, \beta\}$. Then there must be some $r > k_\beta$ such that $a_r > \beta + 1$, so setting $k_{\beta + 1} = r$ yields a subsequence $(a_{k_0}, a_{k_1}, \dots, a_{k_\beta}, a_{k_{\beta + 1}})$ such that $a_{k_j} > j$ for each $j \in \{0, \dots, \beta, \beta + 1\}$. Therefore, the proposition "we can construct a subsequence of $n \in \mathbb{N}$ terms such that blah" satisfies the inductive step and base, so by induction it is true for any finite $n \in \mathbb{N}$.
Apparently, this implies we can construct an infinitely long subsequence $\{a_{k_n}\}_{n \in \mathbb{N}}$ with the property we want? How can we make this conclusion? Perhaps some connection to thinking of a real-valued sequence as a function $f : S \to \mathbb{R}$ for $S \subseteq \mathbb{N}$?
EDIT: based on the comments, induction is indeed not a valid technique for proving the existence of a sequence. The appropriate technique is recursion? How would one reformulate this proof (particularly the ending) to justify the existence of a subsequence $\{a_{k_n}\}_{n \in \mathbb{N}}$ with the property that $a_{k_j} > j$ for all $j \in \mathbb{N}$?