Quod Erat Demonstrandum

2008/12/03

證明不等式的基礎招式 (Part 2)

Filed under: Pure Mathematics,Teaching — johnmayhk @ 5:12 下午
Tags: , ,

招式七:算幾不等式 A.M. \ge G.M.

e.g. 11 For any positive integer n, show that (1 + \frac{1}{n + 1})^{n + 1} > (1 + \frac{1}{n})^n

考慮以下 n + 1 個正整數:

11n1 + \frac{1}{n}

應用 A.M. \ge G.M.,得

\frac{1 + n(1 + \frac{1}{n})}{n + 1} > \sqrt[n + 1]{1 \times (1 + \frac{1}{n})^n}
\Rightarrow \frac{1 + n + 1}{1 + n} > \sqrt[n + 1]{(1 + \frac{1}{n})^n}
\Rightarrow (1 + \frac{1}{n + 1})^{n + 1} > (1 + \frac{1}{n})^n

相信這是證明上述結果的最簡潔方法。

e.g. 12 For any positive integers m, n, p and non-negative numbers a, b, c, show that (\frac{ma + nb + pc}{m + n + p})^{m + n + p} \ge a^mb^nc^p.

類似 e.g. 11,應用 A.M. \ge G.M.manbpc 上,即可。

利用 A.M. \ge G.M.,再配合級數和(sum of series),我們可以產生一系列的不等式:

e.g. 13
(a) 1 + 2 + 3 + \dots + n = \frac{n(n + 1)}{2}

可產生 \frac{n + 1}{2} > \sqrt[n]{n!}

(b) 1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n + 1)(2n + 1)}{6}

可產生 \frac{(n + 1)(2n + 1)}{6} > \sqrt[n]{(n!)^2}

(c) 1^3 + 2^3 + 3^3 + \dots + n^3 = \frac{n^2(n + 1)^2}{4}

可產生 \frac{n(n + 1)^2}{4} > \sqrt[n]{(n!)^3}

(d) 1 + a + a^2 + \dots + a^{n - 1} = \frac{a^n - 1}{a - 1} (a \ne 1)
\Rightarrow \frac{a^n - 1}{n(a - 1)} > \sqrt[n]{a^{1 + 2 + 3 + \dots + (n - 1)}}

可產生 \frac{a^n - 1}{n(a - 1)} > a^{\frac{n - 1}{2}}

(e) 1 + 2a + 3a^2 + \dots + na^{n - 1} = \frac{1 - (n + 1)a^n + na^{n + 1}}{(1 - a)^2} (a \ne 1)

可產生 \frac{1 - (n + 1)a^n + na^{n + 1}}{n(1 - a)^2} > \sqrt[n]{n!}a^{\frac{n - 1}{2}}

(f) C_0^n + C_1^n + C_2^n + \dots + C_n^n = 2^n

可產生 \frac{2^n}{n} > \sqrt[n]{C_0^nC_1^nC_2^n \dots C_n^n}

課程中,我們把玩了不少涉及 binomial coefficients 的級數和,諸如

(C_1^n)^2 + 2(C_2^n)^2 + 3(C_3^n)^2 + \dots + n(C_n^n)^2 = \frac{(2n - 1)!}{[(n - 1)!]^2}

可想而知,我們可以製作很多這系列的不等式,只是結果不太漂亮而已。

(g) \frac{1}{1\times 2} + \frac{1}{2\times 3} + \dots + \frac{1}{n\times (n + 1)} = (1 - \frac{1}{2}) + (\frac{1}{2} - \frac{1}{3}) + \dots + (\frac{1}{n} - \frac{1}{n + 1}) = 1 - \frac{1}{n + 1}
\Rightarrow \frac{1}{n}(1 - \frac{1}{n + 1}) > \sqrt[n]{\frac{1}{1 \times 2}\frac{1}{2 \times 3}\dots\frac{1}{n(n + 1)}}
\Rightarrow \frac{1}{n + 1} > \sqrt[n]{\frac{1}{(n!)^2(n + 1)}}

可產生 (n!)^2 > (n + 1)^{n - 1}((n + 1)!)^2 > (n + 1)^{n + 1}

結果不錯吧?是節節相消和 A.M. \ge G.M. 合作的成果。

同學,老師要擬出形如上述層次較低的題目是不費吹灰之力,問題是當看到結果,要找到相應的級數,就要視乎大家對級數和式的熟悉程度。

招式八:柯西不等式 Cauchy-Schwarz inequality P.S. \ge S.P.

同學一定要懂得以「平方非負」作起手式推導柯西不等式:對任何實數 a_i, b_i

(a_1^2 + a_2^2 + \dots + a_n^2)(b_1^2 + b_2^2 + \dots + b_n^2) \ge (a_1b_1 + a_2b_2 + \dots + a_nb_n)^2

小技巧:n 即是 n 個 1 的總和。

e.g. 14 For non-negative numbers x_1, x_2, \dots ,x_n, show that n(x_1 + x_2 + \dots + x_n) \ge (\sqrt{x_1} + \sqrt{x_2} + \dots + \sqrt{x_n})^2

看到那個 n 嗎?把它寫成 n 個 1 總和,情況一目了然:

(1 + 1 + \dots + 1)(x_1 + x_2 + \dots + x_n)
=  (1^2 + 1^2 + \dots + 1^2)(\sqrt{x_1}^2 + \sqrt{x_2}^2 + \dots + \sqrt{x_n}^2)
\ge (1\times\sqrt{x_1} + 1\times\sqrt{x_2} + \dots + 1\times\sqrt{x_n})^2

result follows.

n 是平方數,比方設 n = 9,我們可進一步得到:\sqrt{x_1 + x_2 + \dots + x_9} \ge \frac{\sqrt{x_1} + \sqrt{x_2} + \dots + \sqrt{x_9}}{3}

e.g. 15 Show that r.m.s. \ge A.M., that is \sqrt{\frac{x_1^2 + x_2^2 + \dots + x_n^2}{n}} \ge \frac{x_1 + x_2 + \dots + x_n}{n}

把上式進行重組,即 n(x_1^2 + x_2^2 + \dots x_n^2) \ge (x_1 + x_2 + \dots + x_n)^2

看到那個 n 嗎?把它寫成 n 個 1 總和,情況一目了然:

(1^2 + 1^2 + \dots + 1^2)(x_1^2 + x_2^2 + \dots x_n^2) \ge (x_1 + x_2 + \dots + x_n)^2

連同其他級數求和的結果,也可產生一些(不太漂亮的)結果:

e.g. 16 Show that \sqrt{8^n - 4^n - 2^n + 1} \ge \sqrt{3}\sum_{k = 1}^n\sqrt{4^{n - k}C_k^n}

嗯,這是亂作題一道,思路如下:有 _nC_r,應該有 sum of binomial coefficients 的考慮,存在 2^n, 4^n, 8^n,相信是有關 sum of G.S. 的,把兩種材料混和,即:

_nC_1 + _nC_2 + \dots + _nC_n = 2^n - 1
1 + a^2 + a^4 + \dots + a^{2n - 2} = \frac{a^{2n} - 1}{a^2 - 1} (a \ne 1)

由柯西不等式,

(_nC_1 + _nC_2 + \dots + _nC_n)(1 + a^2 + a^4 + \dots + a^{2n - 2})
\ge (\sqrt{_nC_1} + a\sqrt{_nC_2} + a^2\sqrt{_nC_3} + \dots a^{n - 1}\sqrt{_nC_n})^2

\Rightarrow (2^n - 1)(\frac{a^{2n} - 1}{a^2 - 1}) \ge (\sqrt{_nC_1} + a\sqrt{_nC_2} + a^2\sqrt{_nC_3} + \dots a^{n - 1}\sqrt{_nC_n})^2

代入 a = 2,得

(2^n - 1)(\frac{4^n - 1}{3}) \ge (\sum_{k = 1}^n2^{k - 1}\sqrt{_nC_k})^2
\Rightarrow (2^n - 1)(4^n - 1) \ge 3(\sum_{k = 1}^n\sqrt{4^{k - 1}C_k^n})^2
\Rightarrow \sqrt{8^n - 4^n - 2^n + 1} \ge \sqrt{3}\sum_{k = 1}^n\sqrt{4^{k - 1}C_k^n}

對稱地,我們得

\Rightarrow \sqrt{8^n - 4^n - 2^n + 1} \ge \sqrt{3}\sum_{k = 1}^n\sqrt{4^{n - k}C_k^n}

類似地,拿別的材料混和,比如節節相消啦,甚至三角級數啦,老師又可以輕易泡製別的不等式來玩學生,唉。

招式九:代入法 method of substitution

此仍上乘武功,層次低一點的,有跡可尋;稍微層次提昇,變得毫無章法,難以擊破,小心小心!

基礎層:有跡可尋

e.g. 17 Given that \frac{a + b + c + d}{4} \ge \sqrt[4]{abcd} for any non-negative numbers a, b, c, d, show that \frac{a + b + c}{3} \ge \sqrt[3]{abc}.

要證明的結果內沒有 d,可代入適當的 d,從而得出結果。這裡代 d = \frac{a + b + c}{3},得

\frac{3d + d}{4} \ge \sqrt[4]{abcd}
\Rightarrow d^4 \ge abcd
\Rightarrow d^3 \ge abc
\Rightarrow d \ge \sqrt[3]{abc}
\Rightarrow \frac{a + b + c}{3} \ge \sqrt[3]{abc}

e.g. 18 Given that for any positive numbers a_1, a_2, \dots ,a_n such that \sum_{k = 1}^n a_k = 1, then \sum_{k = 1}^{n} a_k^p \le n\sum_{k = 1}^{n} a_k^{p + 1} for any non-negative integer p. Show that, for any positive numbers b_1, b_2, \dots ,b_n, (\sum_{k = 1}^n b_k)(\sum_{k = 1}^n b_k^p) \le n\sum_{k = 1}^n b_k^{p + 1} for any non-negative integer p.

要應用前題的結果,即 \sum_{k = 1}^{n} a_k^p \le n\sum_{k = 1}^{n} a_k^{p + 1},我們要確保有 \sum_{k = 1}^n a_k = 1 這個條件成立。

但現在的 b_1, b_2, \dots ,b_n,未必符合有 \sum_{k = 1}^n b_k = 1 這個條件。

\sum_{k = 1}^n b_k = B (say)

再變一變,即

\sum_{k = 1}^n \frac{b_k}{B} = 1

那麼 \frac{b_1}{B}, \frac{b_2}{B}, \dots ,\frac{b_n}{B} 就滿足條件 \sum_{k = 1}^n \frac{b_k}{B} = 1,於是可運用題目的結果,得

\sum_{k = 1}^{n} (\frac{b_k}{B})^p \le n\sum_{k = 1}^{n} (\frac{b_k}{B})^{p + 1}
\Rightarrow \frac{\sum_{k = 1}^{n} b_k^p}{B^p} \le n\frac{\sum_{k = 1}^{n} b_k{p + 1}}{B^{p + 1}}
\Rightarrow B\sum_{k = 1}^{n} b_k^p \le n\sum_{k = 1}^{n} b_k^{p + 1}
\Rightarrow (\sum_{k = 1}^n b_k)(\sum_{k = 1}^n b_k^p) \le n\sum_{k = 1}^n b_k^{p + 1} for any non-negative integer p

e.g. 19 Given that for any positive numbers a_1, a_2, \dots ,a_n such that a_1a_2 \dots a_n = 1, then a_1 + a_2 + \dots + a_n \ge n. Show that, for any positive numbers b_1, b_2, \dots ,b_n, we have \frac{b_1 + b_2 + \dots + b_n}{n} \ge \sqrt[n]{b_1b_2 \dots b_n}

要應用前題的結果,即 a_1 + a_2 + \dots + a_n \ge n,我們要確保有 a_1a_2 \dots a_n = 1 這個條件成立。

但現在的 b_1, b_2, \dots ,b_n,未必符合有 b_1b_2 \dots b_n = 1 這個條件。

b_1b_2 \dots b_n = B (say)

再變一變,即

\frac{b_1b_2 \dots b_n}{B} = 1
\frac{b_1}{\sqrt[n]{B}}\frac{b_2}{\sqrt[n]{B}}\dots\frac{b_n}{\sqrt[n]{B}} = 1 [即把 B 平均地分配給 b_1, b_2, \dots ,b_n]

那麼 \frac{b_1}{\sqrt[n]{B}}, \frac{b_2}{\sqrt[n]{B}}, \dots ,\frac{b_n}{\sqrt[n]{B}} 就滿足條件 \frac{b_1}{\sqrt[n]{B}}\frac{b_2}{\sqrt[n]{B}}\dots\frac{b_n}{\sqrt[n]{B}} = 1,於是可運用題目的結果,得

\frac{b_1}{\sqrt[n]{B}} + \frac{b_2}{\sqrt[n]{B}} + \dots + \frac{b_n}{\sqrt[n]{B}} = n
\Rightarrow \frac{b_1 + b_2 + \dots b_n}{n} \ge \sqrt[n]{B}
\Rightarrow \frac{b_1 + b_2 + \dots b_n}{n} \ge \sqrt[n]{b_1b_2 \dots b_n}

上述三例,不過是代入「平均數」,包括 A.M.G.M.。不同於剛才代入一個變量,下例稍微複雜,須要考慮兩個變量:

e.g. 20 Given that for any positive numbers a_1, a_2, \dots ,a_n and b_1, b_2, \dots ,b_n such that \sum_{k = 1}^n a_kb_k = \sum_{k = 1}^n b_k = 1, then \prod_{k = 1}^na_k^{b_k} \le 1.

Show that for any positive numbers c_k, d_k (k = 1, 2, \dots ,n),

(\prod_{k = 1}^nc_k^{d_k})^{\frac{1}{\sum_{k = 1}d_k}} \le \frac{\sum_{k = 1}^n c_kd_k}{\sum_{k = 1}^n d_k}.

嗯,未做過這題的同學可試試。

二話不說,

代入 b_k = \frac{d_k}{\sum_{k = 1}d_k},那麼便有 \sum_{k = 1}b_k = 1 之效。
代入 a_k = \frac{c_k\sum_{k = 1}^n d_k}{\sum_{k = 1}^n c_kd_k},那麼 a_kb_k = \frac{c_kd_k}{\sum_{k = 1}^n c_kd_k} \Rightarrow \sum_{k = 1}^na_kb_k = \sum_{k = 1}^n (\frac{c_kd_k}{\sum_{k = 1}^n c_kd_k})=  \frac{\sum_{k = 1}^nc_kd_k}{\sum_{k = 1}^n c_kd_k} = 1

這樣的 a_k, b_k 滿足題目條件,可安心應用題目結果,即

\prod [\frac{c_k\sum d_k}{\sum_{c_kd_k}}]^{\frac{d_k}{\sum d_k}} \le 1

(為簡化起見,我不寫上下標。)

\prod c_k^{\frac{d_k}{\sum d_k}} \times \prod [\frac{\sum d_k}{\sum c_kd_k}]^{\frac{d_k}{\sum d_k}} \le 1

(\prod c_k^{d_k})^{\frac{1}{\sum d_k}} \times [\frac{\sum d_k}{\sum c_kd_k}]^{\frac{\sum d_k}{\sum d_k}} \le 1

result follows.

非基礎層:太多變異,難以盡錄,有機再談。

1 則迴響 »

  1. Hi,

    It will be nice to have an English equivalent of your two articles to reach out to more people :)

    Thanks!

    Cheers,
    Wen Shih

    迴響 由 Wen Shih — 2008/12/08 @ 10:29 下午 | 回覆


RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在WordPress.com寫網誌.

%d 位部落客按了讚: