How do you prove that proof by induction is a proof? Are proofs by induction limited to cases where there is an explicit dependance on a integer, like sums? I cannot grasp the idea of induction being a proof in less explicit cases. What if you have a function that suddenly changes behavior? If a function is positive up to some limit couldn't I prove by induction that it is always positive by starting my proof on the left of the limit?
I feel like I am not getting a grasp on something fundamental and I hope you can help me with this. Thank you.

Here is another example from graph theory.
Claim: There is a $4$-regular graph on $n$ vertices for all $n \geq 5$.
Base Case: The complete graph on $5$ vertices is four regular.
Inductive Step: Assume there is a $4$-regular graph $G$ on $k$ vertices. We want to show there is a $4$-regular graph on $k+1$ vertices. Remove any two disjoint edges $e$ and $f$ from $G$. The resulting graph is almost $4$-regular, except it has four vertices of degree $3$ (the vertices involved with the edges $e$ and $f$). Introduce a new vertex to $G - \{e,f\}$ (so now $G$ has $k+1$ vertices) and connect it to each of the aforementioned degree $3$ vertices. The result graph is now $4$-regular, as desired.

How does this proof work? We showed explicitly there is a $4$-regular graph on $5$ vertices. The inductive step tells us how to take this graph and turn it into a $4$-regular graph on $6$ vertices. Applying the inductive step again would take the $4$-regular graph on $6$ vertices and turn it into a $4$-regular graph on $7$ vertices, and so on for any number of vertices you like.
The reason this all works is because my induction step does not depend on any properties of particular values of $k$. It goes through no matter what integer I set to $k$. This assures me that there won't be a sudden change in behavior of the graphs.
