$\sum\limits_{k=0}^{19} \sqrt{1+u_k^2} \rightarrow \min$

Question

Solve $\sum\limits_{k=0}^{19} \sqrt{1+u_k^2} \rightarrow \min$, such that $x_0 = 0, x_{20} = 5$ and $x_{k+1} - x_k = u_k$.

---

I think I know how to solve problems like these recursively, but I don't know how I should attack this specific problem as it involves $20$ different $u_k$'s that need to be calculated (I think there must be a way to solve for general $u_k$ instead of recursively calculating each $u_k$). Could anyone please help?

Answer 1

Hint: This problem is equivalent to minimization of the distance between points $(0,0)$ and $(5,20)$ with the restriction that the path must go through $21$ point whose ordinates are $0,1,\ldots,20$. Clearly the optimal path is a straight line.

Answer 2

Here is another way to solve this problem.

First, we make the observation that $$\frac{d^2}{dx^2} \sqrt{1+x^2} = \frac{1}{\sqrt{1+x^2}^3} > 0$$ This implies the function $\sqrt{1+x^2}$ is a strictly convex function for $x$ over $\mathbb{R}$. Second, we have $$\sum_{k=0}^{19} u_k = \sum_{k=0}^{19}(x_{k+1} - x_{k}) = x_{20} - x_0 = 5$$

Using Jensen's inequality, we obtain:

$$\sum_{k=0}^{19}\sqrt{1+u_k^2} \ge 20 \sqrt{1+\left(\frac{1}{20}\sum_{k=0}^{19}u_k\right)^2} = 20 \sqrt{1 + \frac{1}{4^2}} = 5\sqrt{17} $$ It is clear above equality can be achieved when all $u_k$ is the same, i.e. equal to $\frac{5}{20} = \frac14$. This means the desired minimum is $5\sqrt{17}$.