Cualquier prueba válida que pueda expresarse como "haz algo, luego repítelo hasta que termines" puede formalizarse como una prueba por inducción.
¿Por qué? Bueno, para convertir una prueba mediante "repite hasta que acabes" en una prueba válida, tienes que demostrar que no tendrás que repetir eternamente: al final acabarás. Es decir, deberías ser capaz de asignar alguna medida de complejidad a todas las situaciones que podrían surgir mientras repites tu(s) paso(s) de la prueba y demostrar que 1. cada vez que completas un paso, pasas a una situación estrictamente más simple, 2. si alguna vez llegas a una situación en la que no puedes completar más pasos de la prueba, has terminado, y 3. la situación no puede volverse estrictamente más simple infinitas veces seguidas.
La condición 3 dice que se quiere la relación "situación $x$ es más simple que la situación $y$ " para ser fundado es decir, algo que se puede inducir.
La condición 2 dice que se pueden manejar los casos base (la proposición $P$ que intentas demostrar es cierto allí).
La condición 1 dice que se puede reducir la verdad de $P$ en una situación $x$ a la verdad de $P$ en alguna situación estrictamente más simple $y$ (aplicando un paso de prueba). Dando la vuelta a esto, tenemos la condición inductiva: si $P$ es cierto en todas las situaciones $y$ que son estrictamente más simples que la situación $x$ entonces $P$ es cierto en $x$ .
Si la medida de la complejidad es sólo un número natural, y una situación de complejidad $n$ es más simple que una situación de complejidad $m$ justo cuando $n<m$ entonces tienes una inducción matemática normal (o tal vez inducción completa [o fuerte] ). Si la relación "más simple que" es un orden lineal, pero con un tipo de orden diferente al orden en $\mathbb{N}$ entonces tienes inducción transfinita . Y si la relación es algo más extraña, entonces tienes (generalmente) una inducción bien fundamentada.
Pero la mayoría de los casos que surgen en la práctica, como el ejemplo de la desigualdad del triángulo que das, son simplemente una simple inducción sobre los números naturales reformulada. Estás demostrando por inducción sobre $n\geq 3$ que $$d(x_1,x_n) \leq \sum_{i = 1}^{n-1} d(x_i,x_{i+1}).$$ La medida de la complejidad es el número de términos de la secuencia $x_1,\dots,x_n$ .
El caso base $n = 3$ es la desigualdad del triángulo. El paso inductivo sigue exactamente el argumento que has dado: aplicar la desigualdad del triángulo como $d(x_{n-2},x_n)\leq d(x_{n-2},x_{n-1}) + d(x_{n-1},x_n)$ obtenemos $$d(x_1,x_2) + \dots + d(x_{n-2},x_n) \leq \sum_{i = 1}^{n-1}d(x_i,x_{i+1}).$$
Y en lugar de decir "repetir", podemos concluir por inducción, ya que hemos simplificado el problema. Ahora hay $n-1$ elementos de la secuencia $x_1,\dots,x_{n-2},x_n$ Así que $$d(x_1,x_n) \leq d(x_1,x_2) + \dots + d(x_{n-2},x_n)\leq \sum_{i = 1}^{n-1}d(x_i,x_{i+1}).$$
