Is there such thing as "bounded" Induction?

164 Views Asked by At

Consider, for example, a simple result in group theory. Let $\sigma=(a_1 \ a_2 \cdots a_k )$ be a cyclic permutation in $S_n$. I wish to show that $\sigma^{i}(a_1)=a_{i+1}$ for all $i\in\{0,1,\dots,k-1\}$. Knowing that $\sigma(a_i)=a_{i+1}$ for all such $i$ (*), it should be easy to prove the result by induction. However, the property I want to prove only holds (or rather, only makes sense) up to $i=k-1$, that is, the proof is for $i$ in a bounded subset of $\mathbb{N}$, rather than a set of the form $\{m,m+1,m+2,...\}$. However, it sounds reasonable to believe that induction can still prove something in this case.

The way I thought to deal with this is the following: define a property $P(i)$ of $i\in\mathbb{N}$ which translates to "$\sigma^{i}(a_1)=a_{i+1}$ if $i\in\{0,1,\dots,k-1\}$; $i=i$ , otherwise". Now, $P(i)$ can be proven by induction, applying (*) in the induction step whenever $i<k-1$ (if $i\geq k-1$, then $i+1\notin \{0,1,\dots,k-1\}$, and since $i+1=i+1$ always, $P(i+1)$ holds). Doing so proves, in particular, what we wanted initially.

Is my reasoning correct? Is there a common terminology for this technique? It would be nice to know a "shortcut-principle" so I don't need to state $P(i)$ explicitly every time...