Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$.
share|improve this question
    
by $n=3$ is IMO $1996 $shortlist. so I think General n have this . Do not know to have who has this information or Paper?artofproblemsolving.com/Forum/… –  math110 Jan 18 '13 at 10:44
    
Hint: take a a look at Chebysev polynomials. –  user64494 May 24 '13 at 19:46
add comment

2 Answers 2

up vote 16 down vote accepted
+400

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.

share|improve this answer
    
(+1) Nice answer! It seems that you only used the fact that $|P|\le 1$ at the extremal points of the Chebyshev polynomial, which is much weaker than $|P|\le 1$ on $[-1,1]$; maybe you could highlight it. By the way, there are some typos, such as the coefficient of Lagrange interpolation $B$ in $(10)$, and the missing summation in $(14')$. –  23rd Oct 19 '13 at 18:00
    
@Landscape thanks for all the corrections. –  Ewan Delanoy Oct 19 '13 at 19:33
    
You are welcome. I should thank you for solving this problem, because it puzzled me for a few days. By the way, are you interested in the question I asked in a comment to Sanchez's answer? –  23rd Oct 19 '13 at 19:48
    
@Landscape In my opinion you should ask it as a separate question here on MSE. Never thought much about it, until now. Maybe there’s a simple answer. –  Ewan Delanoy Oct 19 '13 at 19:59
    
Thank you. If I cannot figure it out in a couple of days, I will consider to post an question later. –  23rd Oct 19 '13 at 20:22
add comment

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).

share|improve this answer
    
Thank you ,@Sanchez, I,think part (b) is true, But I don't prove that –  math110 Jan 20 '13 at 11:15
    
Hi, Sanchez. Since the question is closely related to $T_n$ and since $T_n$ satisfies a recurrence relation $T_n(x)=2xT_{n-1}(x)-T_{n-2}(x)$, I wonder if you have considered the following statement. If $f$ is a polynomial with $\deg f=n\ge 2$, then there exist polynomials $g$ and $h$, such that $f(x)=2xg(x)-h(x)$, $\deg g\le n-1$, $\deg h\le n-2$ and $\|g\|,\|h\|\le \|f\|$. Here $\|f\|$ denotes the maximum modulus of $f$ on $[-1,1]$. I have no clue whether statement is true or not. Sorry for bothering. –  23rd Oct 17 '13 at 14:50
    
@Landscape, I haven't thought about this for quite a while, and will look into it later. Thanks for your suggestion! –  user27126 Oct 18 '13 at 0:11
    
@Sanchez: You are welcome and thank you for your help in advance! –  23rd Oct 18 '13 at 5:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.