# Prove inequality involving two vectors

Let $u_1,u_2 \in \mathbb R^n$ be two vectors in an Euclidean space. Suppose that for every integer $k \in \mathbb Z$ we have $|u_1| \le |u_2+ku_1|$. I need to show that for every $k_1, k_2 \in \mathbb Z$, (not both $0$) we have: $|u_1| \le |k_1u_1+k_2u_2|$.

I used the triangle inequality, inserted the $k_2$ in the equation but couldn't get back from a sum of norms to a norm of a sum as asked, because the triangle inequality goes one way if you know what I mean :) Also, the Cauchy-Schwarz inequality is not useful (I believe) here since we have to do with the vectors themselves and not the coordinates (but I may be worng).

If this needs a trick to be solved, can anyone provide a hint?

Let $\pi$ be the orthogonal projection along $u_1$. Then there is a $k \in \mathbb{Z}$ such that $\lVert (1-\pi)(u_2+ k u_1) \rVert = \lVert (1-\pi) u_2 + k u_1 \rVert \leq \tfrac12 \lVert u_1 \rVert$. For this $k$ we have $$\begin{eqnarray}\lVert u_1 \rVert^2 &\leq & \lVert u_2+ k u_1 \rVert^2 \\ &= & \lVert (1-\pi)(u_2+k u_1)\rVert^2 + \lVert \pi(u_2 + k u_1)\rVert^2 \\ &\leq & \tfrac14 \lVert u_1 \rVert^2 + \lVert \pi u_2 \rVert^2 \end{eqnarray}$$ and so $\lVert \pi u_2 \rVert > \tfrac12 \lVert u_1 \rVert$. Then for $k_1, k_2 \in \mathbb{Z}$ and $\lvert k_2 \rvert \geq 2$ $$\lVert k_2 u_2 + k_1 u_1\rVert \geq \lVert \pi(k_2 u_2 + k_1 u_1) \rVert \geq 2 \lVert \pi u_2 \rVert > \lVert u_1 \rVert.$$ The cases with $\lvert k_2 \rvert <2$ are easy to check.
• Some questions: 1) Why $\pi ku_1=0$? I thought that $\pi u_1=u_1$. 2) First inequality: where that $1/2$ came from! 3) Second equality: An equality?! I understand that you add and subtrack $\pi(u_1+ku_1)$ in that case but how come splitting the norm while "on powers of two"? 4) Last line, first inequality: this is from Cauchy–Schwarz inequality, correct? – John Feb 19 '17 at 19:14
• 1) $\pi$ projects in the direction of $u_1$ (not onto its span) so $\pi u_1=0$. 2) If you take steps of length $d$ along the span of $u_1$ then no matter where you start you can always reach a point closer than $d/2$ to the origin (make a picture). 3) That is Pythagoras. 4) An orthogonal projection cannot increase the norm of a vector. This is Pythagoras again: $\lVert v\rVert^2=\lVert \pi v\rVert^2 + \lVert (1-\pi)v\rVert^2$. – WimC Feb 19 '17 at 20:39
• Can you provide an analog of $\pi$ in the 2-dimension space or a link that shows what's $\pi$ and $1-\pi$ and why they make a right triangle? From what you said I understood that $u_1 \bot \pi$. The span of the vector here isn't like moving on it, like in its direction? I understood what you said about reaching closer than $d/2$, but you have an $(1-\pi)u_2$ over there! Where did that go? – John Feb 19 '17 at 21:02
• It would be very nice to really understand what $\pi$ and $1-\pi$ are. Other than that, the proof is impeccable. – John Feb 22 '17 at 16:28
• $$\pi(v)=v-\frac{\langle v, u_1\rangle}{\lVert u_1\rVert^2} u_1$$ – WimC Feb 22 '17 at 16:39