From "An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof" by Peter B. Andrews:
1101 Rule of Substitution (Sub). If $\mathcal{H} \vdash A$, and if $p_{1}, \ldots, p_{n}$ are distinct variables which do not occur in any wff in $\mathcal{H}$, then $\mathcal{H} \vdash S_{B_{1} \ldots B_{n}}^{p_{1} \ldots p_{n}} A$.
Proof: Let $\theta$ be the substitution $S_{B_{1} \ldots B_{n}}^{p_{1} \ldots p_{n}}$. It is easy to see that if $C_{1}, \ldots, C_{m}$ is a proof of $A$ from $\mathcal{H}$, then $\theta C_{1}, \ldots, \theta C_{m}$ is a proof of $\theta A$ from $\mathcal{H}$. Note how the condition on the variables comes into play when $C_{i}$ is a member of $\mathcal{H}$.
Of course, the sentence above is really a rather brief sketch of a proof of this metatheorem. For a more complete proof, show by complete induction on $i$ that $\mathcal{H} \vdash \theta C_{i}$ for each $i$ with $1 \leq i \leq m$. Break the proof into cases according to how $C_{i}$ was justfied in the original proof.
I am confused as to why induction is necessary for this proof. It seems that since we have shown the case for an arbitrary natural number $m$, that it holds for all natural numbers $m$. If I expand the given proof:
Proof: Let $m$ be any natural number. Suppose that $C_{1}, \ldots, C_{m}$ is a proof from $\mathcal{H}$. We will show that $\theta C_{1}, \ldots, \theta C_{m}$ is a proof from $\mathcal{H}$. Let $j$ be any natural number such that $1 \leq j \leq m$. Then either (1) $C_{j}$ is an axiom, (2) $C_{j}$ is a member of $\mathcal{H}$, or (3) there exist $i < j$ and $k < j$ such that $C_{k}$ is $[C_{i} \to C_{j}]$. Suppose $C_{j}$ is an axiom. Then $\theta C_{j}$ is an axiom. Suppose $C_{j}$ is a member of $\mathcal{H}$. Then $\theta C_{j} = C_{j}$ and hence $\theta C_{j}$ is a member of $\mathcal{H}$. Suppose there exist $i < j$ and $k < j$ such that $C_{k}$ is $[C_{i} \to C_{j}]$. Then $\theta C_{k} = \theta [C_{i} \to C_{j}] = [\theta C_{i} \to \theta C_{j}]$. Hence there exist $i < j$ and $k < j$ such that $\theta C_{k}$ is $[\theta C_{i} \to \theta C_{j}]$. Hence $\theta C_{1}, \ldots, \theta C_{m}$ is a proof from $\mathcal{H}$.
Then suppose $\mathcal{H} \vdash A$. Then for some natural number $m$ there is a proof $C_{1}, \ldots, C_{m}$ of $A$ from $\mathcal{H}$. Then $\theta C_{1}, \ldots, \theta C_{m}$ is a proof of $\theta A$ from $\mathcal{H}$. Hence $\mathcal{H} \vdash \theta A$.
EDIT:
The text also states: A proof of a wff $B$ from the set $\mathcal{H}$ of hypotheses is a finite sequence $B_{1}, \ldots, B_{m}$ of wffs such that $B_{m}$ is $B$ and for each $j$ $(1 \leq j \leq m)$ at least one of the following conditions is satisfied: (1) $B_{j}$ is an axiom. (2) $B_{j}$ is a member of $\mathcal{H}$. (3) $B_{j}$ is inferred by Modus Ponens from wffs $B_{i}$ and $B_{k}$, where $i < j$ and $k < j$. An alternative way of expressing condition (3) is to say that there exist $i < j$ and $k < j$ such that $B_{k}$ is $[B_{i} \to B_{j}]$.
In (3) you are forgetting an important thing: the formula $C_i$ must either be an axiom, an hypothesis in $\mathcal H$ or an already proven proposition, that is that $C_1,\dots,C_i$ is a valid proof.
Hence in order to prove that the sequence $\theta C_1,\dots, \theta C_n$ is the valid proof you have to prove inductively that for all those $C_i$'s that are neither axioms or hypotheses the sequence $\theta C_1,\dots,\theta C_i$ is a valid proof.
Edit: I have noticed that the OP has added the definition of proof. According to this definition the argument without induction seems correct. Do not be that surprise by that, it may happen that sometimes authors suggested proofs may be moe complex than they actually need to be, after all we are all humans.
Hope this helps.