1
$\begingroup$

Hi guys I just started metric spaces and was working on the following question. I need to prove by finite induction the following:-

Show that $x_1,\dots, x_n$ are n points in a metric space $(X,d)$ then

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

Now from based on the question by looking at a number of points for example 3 points

$$d(x_1,x_3) \leq d(x_1,x_2)+d(x_2,x_3)$$

therefore by adding a point we would then get the following

$$d(x_1,x_4) \leq d(x_1,x_2)+d(x_2,x_3)+d(x_3,x_4)$$

The following shows my induction proof but I am not familiar with proof by induction and was wondering if I have done it correctly if not can someone guide me:-

$$d(x_1,x_n) \leq d(x_1,x_n)$$ The above is my base case

Initial Hypothesis : Assume the following

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

Then the following holds:- $$d(x_1,x_{k+1}) \leq d(x_1,x_2)+\dots+d(x_k,x_{k+1})$$

$\endgroup$
2
  • 1
    $\begingroup$ Well, how does the last line follow? I can‘t see any justifications in your reasoning. (The inequality is just applying the triangle inequality multiple times which can be formalized via induction.) $\endgroup$
    – Qi Zhu
    Nov 14, 2019 at 4:04
  • $\begingroup$ thats what i am trying to do develop the proof via induction but i am not sure how to justify the reasoning and thats what i attempted thus far. $\endgroup$
    – John
    Nov 14, 2019 at 4:11

1 Answer 1

3
$\begingroup$

The base case is: $d(x_1,x_1)\leq d(x_1,x_1)$.

The inductive hypothesis is: Assume $d(x_1,x_k)\leq d(x_1,x_2)+\dots +d(x_{k-1},x_k)$ for some $k\geq 1$.

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)+\dots +d(x_{k-1},x_k)+d(x_k,x_{k+1})$$

by the triangle inequality and the inductive hypothesis.

$\endgroup$
1
  • $\begingroup$ thanks for the help @JDZ i appreciate it $\endgroup$
    – John
    Nov 14, 2019 at 4:33

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.