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

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?

• Yes, looks fine to me. Still, you should comment on the cases $n=1$ and $n=2$ for the sake of completeness. – Mars Plastic Jul 18 at 14:26
• Yes, of course! – Michael Rozenberg Jul 18 at 14:27
• It is correct. Everything is right! – Azif00 Jul 18 at 14:27

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.