Canadian Mathematical Olympiad

Solution:
Let $Q(x) = x^{2} - k x - 1$ and let $P(x) = a_{0} + a_{1} x + \cdots + a_{n} x^{n}$. Note that the product of the two roots of $Q(x)$ is $-1$ and thus one of the two roots has magnitude at most $1$. Let $z$ be this root. Now note that since $a_{1} = a_{n-1} = 0$, we have that
$$\begin{aligned} 0 = Q(z) P(z) & = -a_{0} - k a_{0} z + \sum_{i=0}^{n-2} \left(a_{i} - k a_{i+1} - a_{i+2}\right) z^{i+2} - k a_{n} z^{n+1} + a_{n} z^{n+2} \\ & = a_{0}(-1 - k z) + \sum_{i=0}^{n-2} \left(a_{i} - k a_{i+1} - a_{i+2}\right) z^{i+2} + a_{n} z^{n} (z^{2} - k z) \\ & = -a_{0} z^{2} + \sum_{i=0}^{n-2} \left(a_{i} - k a_{i+1} - a_{i+2}\right) z^{i+2} + a_{n} z^{n} \end{aligned}$$
where the third equality follows since $z^{2} - k z - 1 = 0$. The triangle inequality now implies
$$\begin{aligned} \left|a_{0}\right| \cdot |z|^{2} & \leq \left|a_{n}\right| \cdot |z|^{n} + \sum_{i=0}^{n-2} \left|a_{i} - k a_{i+1} - a_{i+2}\right| \cdot |z|^{i+2} \\ & \leq \left|a_{n}\right| \cdot |z|^{2} + \sum_{i=0}^{n-2} \left|a_{i} - k a_{i+1} - a_{i+2}\right| \cdot |z|^{2} \end{aligned}$$
since $|z| \leq 1$ and $n \geq 2$. Since $z \neq 0$, the inequality is obtained on dividing by $|z|^{2}$.

Solution 2:
Let $k$ be a real number. Put
$$R = \begin{cases} \sqrt{k^{2} + 4} & \text{ if } k \geq 0 \\ -\sqrt{k^{2} + 4} & \text{ if } k < 0 \end{cases}$$
Define the polynomial
$$S(x) = x^{2} + R x + 1$$
The roots of $S$ are
$$b = \frac{-R - k}{2} \quad \text{ and } \quad c = \frac{-R + k}{2}$$
Then we have
$$b - c = -k, \quad b c = 1, \quad \text{ and } \quad |c| \leq 1$$
(the inequality follows from $b c = 1$ and $|c| \leq |b|$).
Put $d_{i} = a_{i} + b a_{i+1}$ for $i = 0, 1, \ldots, n-1$. Then, for $i = 0, 1, \ldots, n-2$, we have
$$\begin{aligned} d_{i} - c d_{i+1} & = a_{i} + (b - c) a_{i+1} - b c a_{i+2} \\ & = a_{i} - k a_{i+1} - a_{i+2} \end{aligned}$$
Therefore
$$\begin{aligned} \sum_{i=0}^{n-2} \left|a_{i} - k a_{i+1} - a_{i+2}\right| & = \sum_{i=0}^{n-2} \left|d_{i} - c d_{i+1}\right| \\ & \geq \sum_{i=0}^{n-2} \left( \left|d_{i}\right| - |c| \left|d_{i+1}\right| \right) \\ & = \left|d_{0}\right| + (1 - |c|) \sum_{i=1}^{n-2} \left|d_{i}\right| - |c| \left|d_{n-1}\right| \\ & \geq \left|d_{0}\right| - |c| \left|d_{n-1}\right| \\ & = \left|a_{0} + b a_{1}\right| - |c| \left|a_{n-1} + b a_{n}\right| \\ & = \left|a_{0}\right| - |b c| \left|a_{n}\right| \\ & = \left|a_{0}\right| - \left|a_{n}\right| \end{aligned}$$