How to show the Jungle River Metric is Complete

Hints: First it probably helps to understand the metric in the following way: it is the length of the shortest path given that we can only travel vertically at any $x$ value, or horizontally along $y=0$ (I guess we are supposed to imagine a horizontal river along $y=0$ with many vertical tributaries).

Note that $d((x,y),(x',y'))\geq d_1((x,y),(x',y'))$ where $$ d_1((x,y),(x',y'))=|x-x'|+|y-y'| $$ is the metric induced by the norm $\|\cdot\|_1$. Assuming you already know $\mathbb R^2$ is complete wrt $d_1$, this means a sequence which is Cauchy wrt $d$ is also Cauchy wrt $d_1$, and therefore converges to some $(x,y)$ wrt $d_1$. If $y\neq0$, you should be able to show that $x_n=x$ for $n$ sufficiently large.

There are a few tricks we can employ to solve this problem. Firstly, since this metric seems to incorporate the standard Euclidean metric on $\mathbb{R}$ (that is, the distance between $a,b\in\mathbb{R}$ is $|a-b|$), we should use the fact that $\mathbb{R}$ is complete with respect to this metric. This is helpful because we can look at the sequences $(x_{n})_{n\in\mathbb{N}}$ and $(y_{n})_{n\in\mathbb{N}}$ in $\mathbb{R}$ and use their limits to find a limit for $\{(x_n,y_n)\}_{n \in \mathbb{N}}$ in $(\mathbb{R}^{2},d)$.

Another trick which is useful in general metric spaces is the fact that if a subsequence of a Cauchy sequence converges, then the whole Cauchy sequence converges (to the same limit as the subsequence). For a proof of this see here. This is useful for this metric $d$ since we can consider two cases which come from the two scenarios given in the definition of $d$. You don't have to use this trick, but it does make splitting the problem up into cases a bit easier.

Suppose $S=\{(x_n,y_n)\}_{n \in \mathbb{N}}$ is a Cauchy sequence in $\mathbb{R}^{2}$ with respect to $d$. We only have to show that a subsequence of $S$ converges.

Suppose first that we can find $x\in\mathbb{R}$ such that $x_{n}=x$ for infinitely many $n\in\mathbb{N}$. Then we can find a subsequence $S'=\{(x_{n_{k}},y_{n_{k}})\}_{k \in \mathbb{N}}$ of $S$ with $x_{n_{k}}=x$ for all $k$. As $S$ is Cauchy, so is $S'$. Thus, for each $\varepsilon>0$, we can find $N_{\varepsilon}\in\mathbb{N}$ such that $$d((x_{n_{k}},y_{n_{k}}),(x_{n_{k'}},y_{n_{k'}})) =|y_{n_{k}}-y_{n_{k'}}|<\varepsilon$$ holds for all $k,k'\geqslant N_{\varepsilon}$. This shows that the sequence $(y_{n_{k}})_{k\in\mathbb{N}}$ is a Cauchy sequence in $\mathbb{R}$ (with respect to the usual Euclidean metric). As $\mathbb{R}$ is complete, we can find $y\in\mathbb{R}$ such that $(y_{n_{k}})_{k\in\mathbb{N}}$ converges to $y$ in $\mathbb{R}$. It is now easy to show that $(x,y)$ is the limit in $(\mathbb{R}^{2},d)$ for $S'=\{(x_{n_{k}},y_{n_{k}})\}_{k \in \mathbb{N}}$.

Now let's look at the case where such a subsequence of $S$ doesn't exist. In other words, for each $x\in\mathbb{R}$, there are only finitely many $n\in\mathbb{N}$ such that $x_{n}=x$. By replacing $S$ with a subsequence, we can therefore assume without loss of generality that the $x_{n}$ are all distinct. As before, for each $\varepsilon>0$, we can find $N_{\varepsilon}\in\mathbb{N}$ such that $$d((x_{m},y_{m}),(x_{n},y_{n})) =|y_{m}|+|y_{n}|+|x_{m}-x_{n}|<\varepsilon$$ holds for all $m,n\geqslant N_{\varepsilon}$.

Observe from this inequality that $y_{n}\rightarrow0$ as $n\rightarrow\infty$. Also, this inequality shows that $(x_{n})_{n\in\mathbb{N}}$ is a Cauchy sequence in $\mathbb{R}$, and so converges to some limit $x\in\mathbb{R}$. It is then easy to show that $(x,0)$ is the limit in $(\mathbb{R}^{2},d)$ of $S$ (take care to check both cases in the definition of $d$).