Let $a_{i} \in\mathbb{R}$ ($i=1,2,\dots,n$), and $f(x)=\sum_{i=0}^{n}a_{i}x^i$ such that if $|x|\leqslant 1$, then $|f(x)|\leqslant 1$. Prove that:

Let $a_{i} \in\mathbb{R}$ ($i=1,2,\dots,n$), and $f(x)=\sum_{i=0}^{n}a_{i}x^i$ such that if $|x|\leqslant 1$, then $|f(x)|\leqslant 1$. Prove that:

1. $|a_{n}|+|a_{n-1} | \leqslant 2^{n-1}$.
2. $|a_{n}|+|a_{n-1}|+\cdots+|a_{1}|+|a_{0}|\leqslant\dfrac{(1+\sqrt{2})^n+(1-\sqrt{2})^n}{2}$.

Solution 1:

Part (b) As user644 guessed in his comment, the key argument is a Chebyshev interpolation, and we do not need $|P(x)| \leq 1$ for every $x\in [-1,1]$, we only need $|P(x)| \leq 1$ when $x$ is an extremal Chebyshev point.

For an arbitrary polynomial $P=\sum_{k=0}^n a_kx^k$, let us put $$ M(P)=\sum_{k=0}^n |a_k| \tag{1} $$

Let $T_n$ be the $n$-th Chebyshev polynomial, the unique polynomial satisfying $\cos(n\theta)=T_n(\cos(\theta))$. From the formula $\cos((n+1)\theta)+\cos((n-1)\theta)=2\cos(\theta)\cos(n\theta)$ one deduces the recurrence relation

$$ T_{n+1}(x)=2xT_n(x)-T_{n-1}(x) \tag{2} $$

It follows then that for any $q$, there are positive coefficients $u_{q,0},u_{q,1}, \ldots, u_{q,q}, v_{q,0},\ldots, v_{q,q}$ such that

$$ T_{2q}(x)=\sum_{k=0}^{q}(-1)^{q-k}u_{q,k}x^{2k},\ \ T_{2q+1}(x)=\sum_{k=0}^{q}(-1)^{q-k}v_{q,k}x^{2k+1} \tag{3} $$

Indeed, if (3) is true for some $q$ then on the next level we will have

$$ \begin{array}{lcl} T_{2q+2}(x)&=&(-1)^{q+1}u_{q,0}+\bigg(\sum_{k=1}^{q}(-1)^{q+1-k} (u_{q,k}+2v_{q,k-1})x^{2k}\bigg)+2v_{q,q}x^{2q+2}, \\ T_{2q+3}(x)&=&(-1)^{q+1}v_{q,0}x+\bigg(\sum_{k=1}^{q}(-1)^{q+1-k} (v_{q,k}+2u_{q,k}+4v_{q,k-1})x^{2k}\bigg)+4v_{q,q}x^{2q+3} \end{array} \tag{3'} $$

so that (3) follows from an inductive argument, and the base cases $T_0=1,T_1=x$ (yielding $u_{0,0}=v_{0,0}=1$). We deduce from (3) that

$$ M(T_{2q})=\sum_{k=0}^{q} u_{q,k}, \ \ M(T_{2q+1})=\sum_{k=0}^{q} v_{q,k}, \tag{4} $$

and combining this with the recurrence relations in (3'), we have

$$ M(T_{2q+2})=M(T_{2q})+2M(T_{2q+1}), \ M(T_{2q+3})=2M(T_{2q})+5M(T_{2q+1}) \tag{5} $$

which is equivalent to the simpler, classic recurrence relation

$$ M(T_{n+1})=M(T_n)+2M(T_{n-1}) \tag{5'} $$

Arguing by induction on $n$ from (5') (and the base cases $T_0=1,T_1=x$), we see that

$$ M(T_n)=\frac{(1+\sqrt{2})^n+(1-\sqrt{2})^n}{2} \tag{6} $$

Now let $P=\sum_{k=0}^n a_kx^k$ be a polynomial such that $|P(x)| \leq 1$ whenever $x$ is a Chebyshev extremal point of degree $n$. Consider the polynomials

$$ B(t)=\sum_{k=0}^{\llcorner \frac{n}{2} \lrcorner} a_{2k} t^k, \ C(t)= \sum_{k=0}^{\llcorner \frac{n-1}{2} \lrcorner} a_{2k+1} t^k \tag{7} $$

They are linked to $P$ by

$$ P(x)=B(x^2)+xC(x^2), B(x^2)=\frac{P(x)+P(-x)}{2}, C(x^2)=\frac{P(x)-P(-x)}{2x} \tag{8} $$

Suppose that $n$ is odd, $n=2m+1$. Then the set of Chebyshev extremal points is $\lbrace \pm x_j\rbrace_{0\leq j\leq m}$ where $x_j=\cos(\frac{(m-j)\pi}{n})$. Let us put $y_j=P(x_j)$ and $z_{j}=P(-x_j)$.

Then $B$ and $C$ have degree at most $m$, and those polynomials satisfy the interpolation conditions

$$ B(x_j^2)=\frac{y_j+z_j}{2},\ C(x_j^2)=\frac{y_j-z_j}{2x_j} \ (0\leq j \leq m) \tag{9} $$

So by Lagrange interpolation, one can write

$$ \begin{array}{lcl} B(t) &=& \sum_{j=0}^m \frac{(y_j+z_j)}{2} \bigg(\prod_{l\neq j} \frac{t-x_l^2}{x_j^2-x_l^2}\bigg) , \\ C(t) &=& \sum_{j=0}^m \frac{y_j-z_j}{2x_j} \bigg(\prod_{l\neq j} \frac{t-x_l^2}{x_j^2-x_l^2}\bigg) \end{array} \tag{10} $$

Let us denote by $s_{d,j}$ the $d$-th elementary symmetric polynomial in the $m$ variables $(x_i^2)_{i\neq j}$, and by $w_j$ the absolute value of the product $\prod_{l\neq j}(x_j^2-x_l^2)$.

We can then expand (10) as

$$ B(t)=\sum_{k=0}^{m} \bigg(\sum_{j=0}^m \frac{y_j+z_j}{2} \frac{(-1)^{k-j}s_{m-k,j}}{w_j} \bigg) t^k, \ \ C(t)=\sum_{k=0}^{m} \bigg(\sum_{j=0}^m \frac{y_j-z_j}{2x_j} \frac{(-1)^{k-j}s_{m-k,j}}{w_j} \bigg) t^k \tag{11} $$

So

$$ a_{2k}=\sum_{j=0}^m \frac{y_j+z_j}{2} \frac{(-1)^{k-j}s_{m-k,j}}{w_j} , \ \ a_{2k+1}=\sum_{j=0}^m \frac{y_j-z_j}{2x_j} \frac{(-1)^{k-j}s_{m-k,j}}{w_j} \tag{12} $$

Let $\varepsilon$ and $\eta$ be two signs in $\lbrace \pm 1\rbrace$. We have

$$ \begin{array}{lcl} \varepsilon a_{2k}+\eta a_{2k+1} &=& \sum_{j=0}^m \frac{(\varepsilon x_j+\eta)y_j+(\varepsilon x_j-\eta)z_j}{2x_j} \frac{(-1)^{k-j}s_{m-k,j}}{w_j} \\ & \leq & \sum_{j=0}^m \frac{|\varepsilon x_j+\eta|+|\varepsilon x_j-\eta|}{2x_j} \frac{s_{m-k,j}}{w_j} \\ &=&\sum_{j=0}^m \frac{|x_j+\varepsilon\eta|+|x_j-\varepsilon\eta|}{2x_j} \frac{s_{m-k,j}}{w_j} \\ &=& \sum_{j=0}^m \frac{s_{m-k,j}}{w_jx_j} \end{array} \tag{13} $$

Since (13) above holds for any two signs $\varepsilon$ and $\eta$, we see that

$$ |a_{2k}|+|a_{2k+1}| \leq \sum_{j=0}^m \frac{s_{m-k,j}}{w_jx_j} \tag{14} $$

Also, if we take our original $P$ to be $T_n$, then $y_j=(-1)^{m-j}, z_j=-y_j$ so by (12) we have $a_{2k}=0,a_{2k+1}=\sum_{j=0}^m \frac{s_{m-k,j}}{2x_jw_j}$ and so (14) becomes an equality.

Summing up all those inequalities (14) for $k$ between $0$ and $m$ (and remembering they all become equalities when $P=T_n$), we see that $M(P) \leq M(T_n)=\frac{(1+\sqrt{2})^n+(1-\sqrt{2})^n}{2}$ by (6), as wished.

Suppose now that $n$ is even, $n=2m$. Then the set of Chebyshev extremal points is $\lbrace 0 ; \pm x_j\rbrace_{1\leq j\leq m}$ where $x_j=\cos(\frac{(m-j)\pi}{n})$. Let us put $b=P(0)$, $y_j=P(x_j)$ and $z_{j}=P(-x_j)$.

Then $B$ has degree at most $m$, $C$ has degree at most $m-1$ and those polynomials satisfy the interpolation conditions

$$ B(0)=b,\ B(x_j^2)=\frac{y_j+z_j}{2},\ C(x_j^2)=\frac{y_j-z_j}{2x_j} \ (0\leq j \leq m) \tag{9'} $$

So by Lagrange interpolation, one can write

$$ \begin{array}{lcl} B(t) &=& b(-1)^m\bigg(\prod_{l}\frac{t-x_l^2}{x_l^2}\bigg)+\sum_{j=1}^m \frac{(y_j+z_j)t}{2x_j^2} \bigg(\prod_{l\neq j} \frac{t-x_l^2}{x_j^2-x_l^2}\bigg) , \\ C(t) &=& \sum_{j=1}^m \frac{y_j-z_j}{2x_j} \bigg(\prod_{l\neq j} \frac{t-x_l^2}{x_j^2-x_l^2}\bigg) \end{array} \tag{10'} $$

Let us denote by $s_{d,j}$ the $d$-th elementary symmetric polynomial in the $m-1$ variables $(x_i^2)_{i\neq j}$, by $S_{d}$ the $d$-th elementary symmetric polynomial of all the $m$ variables $(x_i^2)_{1\leq i \leq m}$ by $w$ the product $\prod_{j=1}^m x_j^2$ and by $w_j$ the absolute value of the product $\prod_{l\neq j}(x_j^2-x_l^2)$.

We can then expand (10') as

$$ \begin{array}{lcl} B(t)&=&b+\sum_{k=0}^{m-1} \bigg( \frac{(-1)^{k+1} b S_{m-k-1}}{w}+\sum_{j=0}^m \frac{y_j+z_j}{2x_j^2} \frac{(-1)^{k-j}s_{m-k,j}}{w_j} \bigg) t^{k+1}, \\ C(t)&=&\sum_{k=0}^{m-1} \bigg(\sum_{j=0}^m \frac{y_j-z_j}{2x_j} \frac{(-1)^{k-j}s_{m-k,j}}{w_j} \bigg) t^k \tag{11'} \end{array} $$

So

$$ \begin{array}{lcl} a_{2k+2} &=&\frac{(-1)^{k+1} b S_{m-k-1}}{w}+\sum_{j=0}^m \frac{y_j+z_j}{2x_j^2} \frac{(-1)^{k-j}s_{m-k,j}}{w_j} , \\ a_{2k+1} &=&\sum_{j=0}^m \frac{y_j-z_j}{2x_j} \frac{(-1)^{k-j}s_{m-k,j}}{w_j} \\ \end{array} \tag{12'} $$

Arguing as in the proof of (14), we see that

$$ |a_{2k+1}|+|a_{2k+2}| \leq \frac{S_{m-k-1}}{w}+\sum_{j=1}^m\frac{s_{m-k,j}}{w_jx_j^2} (14') $$

and that (14') becomes an equality when $P=T_n$. Then, again, we may add all those inequalities of the form (14') for $0\leq k \leq m-1$ (and add also $|a_0|=|b|$), which finishes the problem.

Solution 2:

Part (a)

By replacing $f(x)$ with $\pm f(\pm x)$ if necessary, we may assume that $a_n, a_{n-1}$ are both non-negative. Let $T_n(x)$ be the Chebyshev polynomial of the first kind, of degree $n$, i.e. it satisfies $$T_n(\cos \theta) = \cos (n\theta)$$ Notice that $T_n(x)$ is a polynomial of degree $n$ with leading coefficient $2^{n-1}$, and that $T_n(x) = \pm 1$ for $x = \cos \frac{0\pi}{n}, \cos \frac{\pi}{n}, \cdots, \cos \frac{n\pi}{n}$.

We first show that $a_n \leq 2^{n-1}$. Suppose the contrary, i.e. $a_n > 2^{n-1}$. Then consider $$g(x) = \frac{a_n}{2^{n-1}}T_n(x) - f(x)$$ would be positive at $\cos \frac{0\pi}{n}$, negative at $\cos\frac{\pi}{n}$, positive at $\cos\frac{2\pi}{n}$ and so forth. (Here we used $|f(x)| \leq 1$ whenever $|x| \leq 1$) Intermediate value theorem says that $g(x)$ would have at least $n$ distinct roots, but $g(x)$ has degree less than $n$. Thus $g(x) \equiv 0$, i.e. $f(x) = \frac{a_n}{2^{n-1}}T_n(x)$. But then $$f(1) = \frac{a_n}{2^{n-1}} T_n(\cos 0) = \frac{a_n}{2^{n-1}} > 1$$ Contradicting the assumption of $f$.

We then show that $a_n + a_{n-1} \leq 2^{n-1}$. Suppose the contrary, i.e. $$a_{n-1} > 2^{n-1} - a_n \hspace{5mm} (*)$$ Consider $$g(x) = (1+\epsilon) T_n(x) - f(x)$$ where $\epsilon > 0$ is sufficiently small and will be picked later.

The leading terms of $g(x)$ are $$g(x) = ((1+\epsilon)2^{n-1} - a_n)x^n - a_{n-1} x^{n-1} + \cdots$$ This implies that the sum of roots of $g(x)$ are $\frac{a_{n-1}}{(1+\epsilon)2^{n-1} - a_n}$. By picking a small enough $\epsilon$ and (*), the sum of roots of $g(x)$ is at least 1.

The condition on $f(x)$ (i.e. $|f(x)| \leq 1$ whenever $|x| \leq 1$) would again imply that $g(x)$ is positive at $\cos \frac{0\pi}{n}$, negative at $\cos\frac{\pi}{n}$, positive at $\cos\frac{2\pi}{n}$ and so forth. Intermediate value theorem says that $g(x)$ would have at least $n$ roots, one lying between $\cos \frac{k\pi}{n}$ and $\cos \frac{(k-1)\pi}{n}$ for $k = 1, \cdots, n$. But $g(x)$ has degree $n$, so these are exactly the roots of $g(x)$. But then the sum of roots is strictly smaller than

$$\cos \frac{0 \pi}{n} + \cos \frac{\pi}{n} \cdots + \cos \frac{(n-1) \pi}{n} = 1$$

Contradiction. This shows part (a).