When performing induction on say a graph $G=(V,E)$, one has many choices for the induction parameter (e.g. $|V|, |E|$, or $|V|+|E|$). Often, it does not matter what choice one makes because the proof is basically the same. However, I just read the following ingenious proof of König's theorem due to Rizzi.

König's theorem. For every bipartite graph $G$, the size of a maximum matching $v(G)$ is equal to the size of a minimum vertex cover $\rho(G)$.

Proof. Induction on $|V|+|E|$. Base case is clear. Now if $G$ has maximum degree 2, then $v(G)=\rho(G)$, so we may assume that $G$ has a vertex $x$ of degree at least 3. Let $y$ be a neighbour of $x$ and let $Y$ be a minimum vertex cover of $G - y$. Evidently, $Y \cup y$ is a vertex cover of $G$. But, by induction $|Y|=v(G-y)$, so we are done unless $v(G)=v(G-y)$. Thus, $G$ has a maximum matching $M$ avoiding $y$. Let $e \in E - M$ be incident to $x$ but not to $y$. By induction,

$v(G)=|M|=v(G-e)=\rho(G-e)$.

Let $Z$ be a vertex cover of $G-e$ of size $|M|$. Note that $y \notin Z$, since $M$ does not cover $y$. This implies $x \in Z$, since $xy \in E$. But then $Z$ also covers $e$ and hence is a vertex cover of $G$.

Question. What are some other instances (not necessarily in graph theory), where simply changing the induction parameter results in a nice shorter proof?