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?

  • $\begingroup$ Yes, looks fine to me. Still, you should comment on the cases $n=1$ and $n=2$ for the sake of completeness. $\endgroup$ – Mars Plastic Jul 18 at 14:26
  • 1
    $\begingroup$ Yes, of course! $\endgroup$ – Michael Rozenberg Jul 18 at 14:27
  • 1
    $\begingroup$ It is correct. Everything is right! $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.