Prove: $d(x_1,x_n)\leq d(x_1,x_2)+...+d(x_{n-1},x_n)$

Question

Prove: $d(x_1,x_n)\leq d(x_1,x_2)+...+d(x_{n-1},x_n)$, where $d(x_i,x_j)$ is a metric

My question is regarding to the process of proving by induction, what I have done is the following:

for $n=3:$

$$d(x_1,x_3)\leq d(x_1,x_2)+d(x_2,x_3)$$ by definition of the metric.

Assume it is correct for $n=k:$ $$d(x_1,x_k)\leq d(x_1,x_2)+...+d(x_{k-1},x_k)$$

Now we have to prove for $n=k+1$

Can we look again at $$d(x_1,x_k)\leq d(x_1,x_2)+...+d(x_{k-1},x_k)$$ And say, this is by assumption is correct, lets add $d(x_k,x_{k+1})$ to both sides then:

$$d(x_1,x_{k+1})\leq d(x_1,x_k)+d(x_k,x_{k+1})\leq d(x_1,x_2)+...+d(x_{k-1},x_k)+d(x_k,x_{k+1})$$

Where $d(x_1,x_{k+1})\leq d(x_1,x_k)+d(x_k,x_{k+1})$ is by the first induction step

Is it valid proof by induction?

Answer 1

Yes, what you have done is correct, but I like to think a little different. The usual idea of induction is to reduce to the previous case. So, instead of "adding up" to both sides, we start with the expression $d(x_1, x_{k+1})$, separate $$ d(x_1, x_{k+1}) \leq d(x_1, x_k) + d(x_k, x_{k+1}) $$ and now we proceed by induction, from where conclude $$ d(x_1, x_{k+1}) \leq d(x_1, x_2) + \dotsb + d(x_{k-1}, x_k) + d(x_k, x_{k+1}), $$ as we desired to prove.