這是我預備的 Presentation soft copy (Click)
TA 說：「又屈條 inequality 出黎....」= =。
今天有人再一次問我，甘仔 (定金?) 先前提出的問題的解法，已知 $g$ 是 differentiable (其餘 condition 略)
他問：「為甚麼一定存在 $c$ 令到 $ g'(c) = 0$？」
(這個問題沒甚麼，我再一次解釋一番)
我道：「因為由 slope 看到 local extrema 必定在那開區間裏發生」
(再明確一點 $ g'(a) < 0\implies$ $ g(a)$ 不是 minima，$ g'(b)>0\implies$ $ g(b)$ 也不是 minima，又由於一個 continuous function 必定在閉區間裏達到最大最小值，因此最小值必定在開區間 $ (a,b)$ 裏發生。)
他又問道：「那 $g$ 起角怎麼辦？」
我：「……」
事後又給我撞正他說我甚麼解釋得不清楚，諸如此類的，我快心臟病發。有時腦內補完也是蠻重要的吧?
Saturday, February 27, 2010
Thursday, February 25, 2010
MATH190 presentation next week
I am here to post my answer (numerical and method only) for my teammate, you can use it to check. If our answers are different, please discuss with me.
Problem (1990 Austrian-Polish Math Competition)
Let $ n>1$ be an integer and let $ f_1,f_2,\dots, f_{n!}$ be the $ n!$ permutations of $ 1,2,\dots,n$ (each $ f_i$ is a bijective function from $ \{1,2,\dots,n\}$ to itself). For each permutation $ f_i$, let us define $ \displaystyle S(f_i)=\sum_{k=1}^n|f_i(k)-k|$. Find $ \displaystyle \frac{1}{n!}\sum_{i=1}^{n!}S(f_i)$.
My numerical answer. $ \displaystyle \frac{n^2-1}{3}$.
Next question I just use Jensen's inequality once.
Problem (1990 Austrian-Polish Math Competition)
Let $ n>1$ be an integer and let $ f_1,f_2,\dots, f_{n!}$ be the $ n!$ permutations of $ 1,2,\dots,n$ (each $ f_i$ is a bijective function from $ \{1,2,\dots,n\}$ to itself). For each permutation $ f_i$, let us define $ \displaystyle S(f_i)=\sum_{k=1}^n|f_i(k)-k|$. Find $ \displaystyle \frac{1}{n!}\sum_{i=1}^{n!}S(f_i)$.
My numerical answer. $ \displaystyle \frac{n^2-1}{3}$.
Next question I just use Jensen's inequality once.
Wednesday, February 24, 2010
惡補 linear algebra
.... bilinear ... multilinear .... 甚麼鬼東西...。
最近上 MATH204 愈來愈一頭霧水。
Lift 3 Room 5003
Problem (1990 IMO Shortlisted Problem).
For any $ x,y,z >0$, $ xyz=1$, prove that \[ \frac{x^3}{(1+y)(1+z)}+\frac{y^3}{(1+z)(1+x)}+\frac{z^3}{(1+x)(1+y)} \ge \frac{3}{4}.\]
我第一次看這條題目時它給的 condition 是 $ x+y+z\ge 3$，代替了 $ xyz=1$，不知道其用意。重提這問題的原因是那時因年少無知，提出了這樣的答法 (按我)。這很明顯是錯的，我們從來沒有學過考慮三組數字的排序不等式。所以以前看過我這做法的人，對不起，我錯了。
首次看到它的原因是在瀏灠 Mathdb 時看到這頁(按我)，看到「頗有難度的不等式題目」的 pdf，正巧那時我正研究着不等式，便嘗試着解決裏面的問題。
李教授提出這個例子的目的是要表現出 Muirhead 有多暴力。有學過 H$ \ddot{\text{o}}$lder's 不等式的話，我們能給出一個較``雅"的做法。證法是很明顯的，在這裏不花口水了。
最近上 MATH204 愈來愈一頭霧水。
Lift 3 Room 5003
Problem (1990 IMO Shortlisted Problem).
For any $ x,y,z >0$, $ xyz=1$, prove that \[ \frac{x^3}{(1+y)(1+z)}+\frac{y^3}{(1+z)(1+x)}+\frac{z^3}{(1+x)(1+y)} \ge \frac{3}{4}.\]
我第一次看這條題目時它給的 condition 是 $ x+y+z\ge 3$，代替了 $ xyz=1$，不知道其用意。重提這問題的原因是那時因年少無知，提出了這樣的答法 (按我)。這很明顯是錯的，我們從來沒有學過考慮三組數字的排序不等式。所以以前看過我這做法的人，對不起，我錯了。
首次看到它的原因是在瀏灠 Mathdb 時看到這頁(按我)，看到「頗有難度的不等式題目」的 pdf，正巧那時我正研究着不等式，便嘗試着解決裏面的問題。
李教授提出這個例子的目的是要表現出 Muirhead 有多暴力。有學過 H$ \ddot{\text{o}}$lder's 不等式的話，我們能給出一個較``雅"的做法。證法是很明顯的，在這裏不花口水了。
Tuesday, February 23, 2010
內地的高考
不等式是內地高考一個重要的課題。懷着好奇的心去做做看，不懂的還蠻多的...。以下都是些解了的題目，在此不提供解答了。
Problem 1. Prove that for any $ a,b,c\in\mathbb{R}$, $ \displaystyle \sqrt{a^2+(1-b)^2}+\sqrt{b^2+(1-c)^2}+\sqrt{c^2+(1-a)^2}\ge \frac{3\sqrt{2}}{2}.$
Problem 2 (Mircea Lascu). Let $ a,b,c$ be positive real numbers such that $ abc=1$. Prove that $ \displaystyle \frac{b+c}{\sqrt{a}}+\frac{c+a}{\sqrt{b}}+\frac{a+b}{\sqrt{2}}\ge \sqrt{a}+\sqrt{b}+\sqrt{c}+3.$
Problem 3. Let $ a,b,c,x,y,z$ be positive real numbers such that $ x+y+z=1$. Prove that $ \displaystyle ax+by+cz+2\sqrt{(xy+yz+zx)(ab+bc+ca)}\leq a+b+c.$
Problem 1. Prove that for any $ a,b,c\in\mathbb{R}$, $ \displaystyle \sqrt{a^2+(1-b)^2}+\sqrt{b^2+(1-c)^2}+\sqrt{c^2+(1-a)^2}\ge \frac{3\sqrt{2}}{2}.$
Problem 2 (Mircea Lascu). Let $ a,b,c$ be positive real numbers such that $ abc=1$. Prove that $ \displaystyle \frac{b+c}{\sqrt{a}}+\frac{c+a}{\sqrt{b}}+\frac{a+b}{\sqrt{2}}\ge \sqrt{a}+\sqrt{b}+\sqrt{c}+3.$
Problem 3. Let $ a,b,c,x,y,z$ be positive real numbers such that $ x+y+z=1$. Prove that $ \displaystyle ax+by+cz+2\sqrt{(xy+yz+zx)(ab+bc+ca)}\leq a+b+c.$
Monday, February 22, 2010
An integral that even wolfram integrator cannot find
Here is the ``discussion" from uwants (click me)
Another discussion from mathlinks (click me)
But I find it in a way totally different from them, that's a challenge to find the formula.
Problem. Find the explicit formula of the integral $ \displaystyle \int \frac{x^2-1}{(x^2+1)\sqrt{1+x^4}}\,dx$.
My way is as follows
Another discussion from mathlinks (click me)
But I find it in a way totally different from them, that's a challenge to find the formula.
Problem. Find the explicit formula of the integral $ \displaystyle \int \frac{x^2-1}{(x^2+1)\sqrt{1+x^4}}\,dx$.
My way is as follows
Sunday, February 21, 2010
局部調整法
Kin Li 教授 d material 真係教左種好方便的 skill，由其是個 Local Refinement Method 感覺由複雜變簡單。同學學左個技巧就可以解決到呢題。
Problem (IMO-1984-1). Let $ x,y,z$ be non-negative integers satisfying $ x+y+z=1$, prove that \[xy+yz+zx -2xyz\leq \frac{7}{27}.\]
一開始 fix 數切忌不要 fix 得太多。Smoothing method 到而家都仲未領會到。
soarer TA 已經發放了下星期 4 將會用的 tutorial notes...，然後我突然看到這一題。
Problem (USA-1997). Let $ a, b, c > 0$. Prove that $\displaystyle \frac{1}{a^3+b^3+abc}+\frac{1}{b^3+c^3+abc}+\frac{1}{c^3+a^3+abc}\leq \frac{1}{abc}$.
只是借題發揮一下，這是一條需要很少不等式知識的題目。觀察到 $ (a^2-b^2)(a-b)\ge 0 \iff a^3+b^3\ge ab(a+b)$，我們便完成了這條問題。
My way.
$ \displaystyle\sum_{cyc} \frac{1}{a^3+b^3+abc}\leq\sum_{cyc}\frac{1}{ab(a+b) + ab(c)}=\sum_{cyc}\frac{c}{abc (a+b+c)}=\frac{1}{abc}$.
Muirhead 確實是很黃很暴力的不等式，它能夠令我們不加思索也能夠解決一條不等式的問題。在我的問庫中 (點我)，第 41 條正正是好例子。利用電腦運算它等同於要證明 \[ \displaystyle\sum_{sym}a^{12}b^3c^3 + \sum_{sym} a^9b^3c^3+\sum_{sym}a^6b^3c^3\leq \sum_{sym}a^{14}b^2c^2+\sum_{sym}a^{13}bc+\sum_{sym}a^{12}.\] 成立。比較相同次方的和，問題得證。有時不一定要齊次的時候才成功，用電腦爆它一爆可能別有洞天。
MATH190 可以開着 notebook 考試嗎?
An exercise in MATH204 assignment that suits MATH102
Problem. Find the range of $ p$ at which $ \displaystyle \lim_{{\normalsize (x,y)\to \vec{0},y^2>x>0}} \frac{x^py}{x^2+y^2}$ converges.
Problem (IMO-1984-1). Let $ x,y,z$ be non-negative integers satisfying $ x+y+z=1$, prove that \[xy+yz+zx -2xyz\leq \frac{7}{27}.\]
一開始 fix 數切忌不要 fix 得太多。Smoothing method 到而家都仲未領會到。
soarer TA 已經發放了下星期 4 將會用的 tutorial notes...，然後我突然看到這一題。
Problem (USA-1997). Let $ a, b, c > 0$. Prove that $\displaystyle \frac{1}{a^3+b^3+abc}+\frac{1}{b^3+c^3+abc}+\frac{1}{c^3+a^3+abc}\leq \frac{1}{abc}$.
只是借題發揮一下，這是一條需要很少不等式知識的題目。觀察到 $ (a^2-b^2)(a-b)\ge 0 \iff a^3+b^3\ge ab(a+b)$，我們便完成了這條問題。
My way.
$ \displaystyle\sum_{cyc} \frac{1}{a^3+b^3+abc}\leq\sum_{cyc}\frac{1}{ab(a+b) + ab(c)}=\sum_{cyc}\frac{c}{abc (a+b+c)}=\frac{1}{abc}$.
Muirhead 確實是很黃很暴力的不等式，它能夠令我們不加思索也能夠解決一條不等式的問題。在我的問庫中 (點我)，第 41 條正正是好例子。利用電腦運算它等同於要證明 \[ \displaystyle\sum_{sym}a^{12}b^3c^3 + \sum_{sym} a^9b^3c^3+\sum_{sym}a^6b^3c^3\leq \sum_{sym}a^{14}b^2c^2+\sum_{sym}a^{13}bc+\sum_{sym}a^{12}.\] 成立。比較相同次方的和，問題得證。有時不一定要齊次的時候才成功，用電腦爆它一爆可能別有洞天。
MATH190 可以開着 notebook 考試嗎?
An exercise in MATH204 assignment that suits MATH102
Problem. Find the range of $ p$ at which $ \displaystyle \lim_{{\normalsize (x,y)\to \vec{0},y^2>x>0}} \frac{x^py}{x^2+y^2}$ converges.
Saturday, February 20, 2010
Problem of today's MATH202 tutorial lesson
Too many hints are present in this note.
In example 4 we have come across a boring question. Here is a much interesting one.
$latex \boxed{\text{\textbf{Problem}}}$
Suppose $latex f''(0)$ exists and $latex f''(0)\neq 0$. Prove that in the mean value theorem $latex f(x)-f(0)=xf'(\theta x)$, we have $latex \displaystyle \lim_{x\to 0}\theta =\frac{1}{2}$.
This is a problem of my past assignment in MATH203, and the example 4 is exactly one of them.
In example 4 we have come across a boring question. Here is a much interesting one.
$latex \boxed{\text{\textbf{Problem}}}$
Suppose $latex f''(0)$ exists and $latex f''(0)\neq 0$. Prove that in the mean value theorem $latex f(x)-f(0)=xf'(\theta x)$, we have $latex \displaystyle \lim_{x\to 0}\theta =\frac{1}{2}$.
This is a problem of my past assignment in MATH203, and the example 4 is exactly one of them.
Friday, February 19, 2010
Problem of today's MATH190 tutorial lesson
Problems typed below can also be found in this tutorial note, http://ihome.ust.hk/~masoarer/math190/week3.pdf. For fear that the web host will be out of service due to any reason, I have typed everything below. This text is prepared for future use, for example, my ``collection of problems".
Exercise 1. Let $ a,b,c>0$, show that $ (a^3+1)(b^3+1)(c^3+1)\ge (a^2b+1)(b^2c+1)(c^2a+1)$.
My way.
Note that $ (a^3+1)(a^3+1)(b^3+1)\ge (a^2b+1)^3$, we are done (you can see what happens when $ (a,b)=(b,c)$ and $ (a,b)=(c,a)$.).
Exercise 2. If $ a,b,c>0$, prove that $ \displaystyle \frac{a+\sqrt{ab}+\sqrt[3]{abc}}{3}\leq \sqrt[3]{a\cdot \frac{a+b}{2}\cdot \frac{a+b+c}{3}}$.
My way.
We see that \begin{align*}
a\cdot \frac{a+b}{2}\cdot \frac{a+b+c}{3}&=\left(\frac{a}{3}+\frac{a}{3}+\frac{a}{3}\right)\left(\frac{a}{3}+\frac{a+b}{6}+\frac{b}{3}\right)\left(\frac{a}{3}+\frac{b}{3}+\frac{c}{3}\right)\\
&\ge \left(\frac{a}{3}+\sqrt[3]{\frac{ab(a+b)}{2\cdot 3^3}}+\frac{\sqrt[3]{abc}}{3}\right)^3.
\end{align*} Finally, $ \displaystyle\frac{a+b}{2}\ge\sqrt{ab}$ does solve the problem.
Exercise 5. Let $ a,b,c>0$, prove that $ \displaystyle \frac{a^6}{b^2+c^2}+\frac{b^6}{c^2+a^2}+\frac{c^6}{a^2+b^2}\ge \frac{abc(a+b+c)}{2}$.
My way.
Use exercise 4 once, we have a new lower bound $ \displaystyle \frac{a^6}{b^2+c^2}+\frac{b^6}{c^2+a^2}+\frac{c^6}{a^2+b^2}\ge \frac{1}{6}(a^2+b^2+c^2)^2$, since \[(a^2+b^2+c^2)^2 \ge (ab+bc+ca)^2\ge 3(abbc + bcca + caab)=3abc(a+b+c),
\] we are done.
Exercise 6. Let $ f$ be convex on $ [a,b]$. If $ c,d\in[a,b]$ with $ c-a>b-d$, prove that $ \displaystyle 2f\left(\frac{c+d}{2}\right) \leq f(c)+f(d)\leq f(c+d-b)+f(b)$.
My way.
The left inequality is obviously true. To go through right inequality, we first determine the position of $ a,b,c,d$ and $ c+d-b$. Observe that the inequality will change nothing if we interchange $ c$ and $ d$, so without loss of generality, we assume that $ c\leq d$, finally $ c+d-b\leq c \iff d\leq b$ we have known that $ a\leq c+d-b\leq c\leq d\leq b$.
Since $ \displaystyle f(c)+f(d)\leq f(c+d-b)+f(b)\iff \frac{f(b)-f(c)}{b-c}\ge \frac{f(d)-f(c+d-b)}{d-(c+d-b)}$, the equivalent inequality is obvious by convexity.
Exercise 9. Let $ A,B,C$ be angles of a triangle. Prove that $ \displaystyle \frac{\sin A}{A}+\frac{\sin B}{B}+\frac{\sin C}{C}\leq \frac{9\sqrt{3}}{2\pi}$.
My way.
We observe the ineqality $ \displaystyle \frac{\sin x}{x}\leq \left(\frac{\frac{\pi}{3}\cdot \frac{1}{2}-\frac{\sqrt{3}}{2}}{\left(\frac{\pi}{3}\right)^2}\right)\left(x-\frac{\pi}{3}\right)+\frac{3\sqrt{3}}{2\pi}$. I haven't rigorously checked its validity by calculus, at least it is true for $ x\in (0,\pi)$ with the aid of graph ploting, hence replacing $ x$ by respectively $ a,b,c$ and adding them up, we get desired result.
Exercise 10. Let $ f$ be a convex function on $ [a,b]$ and $ x,y,z\in [a,b]$. Prove by majorization inequality that $ \displaystyle f(x)+f(y)+f(z)+3f\left(\frac{x+y+z}{3}\right)\ge 2 \left(f\left(\frac{x+y}{2}\right)+f\left(\frac{y+z}{2}\right)+f\left(\frac{z+x}{2}\right)\right)$.
My way.
Correcting.
Exercise 3, 4, 7, 8 are skipped (I would not include these problems in my pdf), I am trying exercise 10.
Exercise 1. Let $ a,b,c>0$, show that $ (a^3+1)(b^3+1)(c^3+1)\ge (a^2b+1)(b^2c+1)(c^2a+1)$.
My way.
Note that $ (a^3+1)(a^3+1)(b^3+1)\ge (a^2b+1)^3$, we are done (you can see what happens when $ (a,b)=(b,c)$ and $ (a,b)=(c,a)$.).
Exercise 2. If $ a,b,c>0$, prove that $ \displaystyle \frac{a+\sqrt{ab}+\sqrt[3]{abc}}{3}\leq \sqrt[3]{a\cdot \frac{a+b}{2}\cdot \frac{a+b+c}{3}}$.
My way.
We see that \begin{align*}
a\cdot \frac{a+b}{2}\cdot \frac{a+b+c}{3}&=\left(\frac{a}{3}+\frac{a}{3}+\frac{a}{3}\right)\left(\frac{a}{3}+\frac{a+b}{6}+\frac{b}{3}\right)\left(\frac{a}{3}+\frac{b}{3}+\frac{c}{3}\right)\\
&\ge \left(\frac{a}{3}+\sqrt[3]{\frac{ab(a+b)}{2\cdot 3^3}}+\frac{\sqrt[3]{abc}}{3}\right)^3.
\end{align*} Finally, $ \displaystyle\frac{a+b}{2}\ge\sqrt{ab}$ does solve the problem.
Exercise 5. Let $ a,b,c>0$, prove that $ \displaystyle \frac{a^6}{b^2+c^2}+\frac{b^6}{c^2+a^2}+\frac{c^6}{a^2+b^2}\ge \frac{abc(a+b+c)}{2}$.
My way.
Use exercise 4 once, we have a new lower bound $ \displaystyle \frac{a^6}{b^2+c^2}+\frac{b^6}{c^2+a^2}+\frac{c^6}{a^2+b^2}\ge \frac{1}{6}(a^2+b^2+c^2)^2$, since \[(a^2+b^2+c^2)^2 \ge (ab+bc+ca)^2\ge 3(abbc + bcca + caab)=3abc(a+b+c),
\] we are done.
Exercise 6. Let $ f$ be convex on $ [a,b]$. If $ c,d\in[a,b]$ with $ c-a>b-d$, prove that $ \displaystyle 2f\left(\frac{c+d}{2}\right) \leq f(c)+f(d)\leq f(c+d-b)+f(b)$.
My way.
The left inequality is obviously true. To go through right inequality, we first determine the position of $ a,b,c,d$ and $ c+d-b$. Observe that the inequality will change nothing if we interchange $ c$ and $ d$, so without loss of generality, we assume that $ c\leq d$, finally $ c+d-b\leq c \iff d\leq b$ we have known that $ a\leq c+d-b\leq c\leq d\leq b$.
Since $ \displaystyle f(c)+f(d)\leq f(c+d-b)+f(b)\iff \frac{f(b)-f(c)}{b-c}\ge \frac{f(d)-f(c+d-b)}{d-(c+d-b)}$, the equivalent inequality is obvious by convexity.
Exercise 9. Let $ A,B,C$ be angles of a triangle. Prove that $ \displaystyle \frac{\sin A}{A}+\frac{\sin B}{B}+\frac{\sin C}{C}\leq \frac{9\sqrt{3}}{2\pi}$.
My way.
We observe the ineqality $ \displaystyle \frac{\sin x}{x}\leq \left(\frac{\frac{\pi}{3}\cdot \frac{1}{2}-\frac{\sqrt{3}}{2}}{\left(\frac{\pi}{3}\right)^2}\right)\left(x-\frac{\pi}{3}\right)+\frac{3\sqrt{3}}{2\pi}$. I haven't rigorously checked its validity by calculus, at least it is true for $ x\in (0,\pi)$ with the aid of graph ploting, hence replacing $ x$ by respectively $ a,b,c$ and adding them up, we get desired result.
Exercise 10. Let $ f$ be a convex function on $ [a,b]$ and $ x,y,z\in [a,b]$. Prove by majorization inequality that $ \displaystyle f(x)+f(y)+f(z)+3f\left(\frac{x+y+z}{3}\right)\ge 2 \left(f\left(\frac{x+y}{2}\right)+f\left(\frac{y+z}{2}\right)+f\left(\frac{z+x}{2}\right)\right)$.
My way.
Correcting.
Exercise 3, 4, 7, 8 are skipped (I would not include these problems in my pdf), I am trying exercise 10.
Wednesday, February 17, 2010
Interesting identity, deduced from a Probability problem of Ming (CU,CSC)
I can do all except (b) orz.
Well this is a good example that why combinatorics and probability can generate interesting identity. (discussion from part (e) on) It can be easily deduced that $ \displaystyle P(B_i)=\frac{1}{2^{n-1}(2^n-1)}$. Now we turn our objective to finding the probability that $ A$ and $ B$ will meet at the $ r$-th round. Having known what $ P(B_i)$ is, our desired probability is obviously
$ p = \displaystyle 2^{n-r}\cdot P(B_i) = \frac{2^{n-r}}{2^{n-1}(2^n-1)}$.
We take a step further, the same probability can be duduced if $ A$ and $ B$ cannot meet and they win at the first $ r-1$-th rounds and occasionally meet at the $ r$-th round, this is the same as \[
p = \underbrace{\prod_{k=1}^{r-1}\left\{\frac{\displaystyle \binom{2^{n-k}}{2}\cdot 2^3}{2^{n-k+1}(2^{n-k+1}-1)}\cdot \left(\frac{1}{2}\right)^2\right\}}_{\text{don't meet and win at the first r - 1 rounds}}\cdot \overbrace{\left(\frac{2}{2^{n-r+1}}\cdot \frac{1}{2^{n-r+1}-1}\cdot 2^{n-r}\right)}^{\text{meet at the last round}}.
\] We now equate two $ p$'s, having \[
\prod_{k=1}^{r-1}\left(1-\frac{1}{2^{n-k+1}-1}\right)=\frac{2^n-2^{r-1}}{2^n-1},
\] by simple algebra we get a more convenient form \[\boxed{\dis \prod_{k=j}^n\left(1-\frac{1}{2^k-1}\right)=1-\frac{2^{n-j+1}-1}{2^n-1}.}
\] If this is an unprecedented identity, then I would call it CC's identity (政昌恆等式).
Motivated by this problem, if we don't know the above formula, can we show that \[ \sum\limits_{k=2}^\infty\displaystyle\ln\left(1-\frac{1}{2^k-1}\right)
\] converges? The answer is yes! Take a suitable $N$ such that when $ k >N$, we always have $ \displaystyle \frac{1}{2^k - 1}<1$, consider the taylor expansion $ \displaystyle \ln (1+x)=x-\frac{1}{(1+c)^2}x^2$, for some $ c$ in between $ 0$ and $ x$, now consider $ |x|<1$ such that $ |c|<\delta <1$, then we get by putting $ x=x_k$, $ |x_k|<1$, \[
\frac{x_k^2}{(1+\delta)^2}<x_k-\ln(1+x_k)<\frac{x_k^2}{(1-\delta)^2},
\] actually $ x>\ln (1+x),\forall x>-1$ simply because $ e^x\ge 1+x$. Now let $ \displaystyle x_k=-\frac{1}{2^k-1}$, our required $ N$ is simply 1, so we know that $ \sum_{k=2}^\infty x_k^2$ converges, thus by above inequality, $ \sum_{k=2}^\infty (x_k-\ln(1+x_k))$ also converges by comparison test, since $ \sum_{k=2}^\infty x_k$ converges, $ \sum_{k=2}^\infty \ln(1+x_k)$ also converges, we are done. Moreover, $ \sum\limits_{k=2}^\infty\displaystyle\ln\left(1-\frac{1}{2^k-1}\right)=-\ln 2$.
Well this is a good example that why combinatorics and probability can generate interesting identity. (discussion from part (e) on) It can be easily deduced that $ \displaystyle P(B_i)=\frac{1}{2^{n-1}(2^n-1)}$. Now we turn our objective to finding the probability that $ A$ and $ B$ will meet at the $ r$-th round. Having known what $ P(B_i)$ is, our desired probability is obviously
$ p = \displaystyle 2^{n-r}\cdot P(B_i) = \frac{2^{n-r}}{2^{n-1}(2^n-1)}$.
We take a step further, the same probability can be duduced if $ A$ and $ B$ cannot meet and they win at the first $ r-1$-th rounds and occasionally meet at the $ r$-th round, this is the same as \[
p = \underbrace{\prod_{k=1}^{r-1}\left\{\frac{\displaystyle \binom{2^{n-k}}{2}\cdot 2^3}{2^{n-k+1}(2^{n-k+1}-1)}\cdot \left(\frac{1}{2}\right)^2\right\}}_{\text{don't meet and win at the first r - 1 rounds}}\cdot \overbrace{\left(\frac{2}{2^{n-r+1}}\cdot \frac{1}{2^{n-r+1}-1}\cdot 2^{n-r}\right)}^{\text{meet at the last round}}.
\] We now equate two $ p$'s, having \[
\prod_{k=1}^{r-1}\left(1-\frac{1}{2^{n-k+1}-1}\right)=\frac{2^n-2^{r-1}}{2^n-1},
\] by simple algebra we get a more convenient form \[\boxed{\dis \prod_{k=j}^n\left(1-\frac{1}{2^k-1}\right)=1-\frac{2^{n-j+1}-1}{2^n-1}.}
\] If this is an unprecedented identity, then I would call it CC's identity (政昌恆等式).
Motivated by this problem, if we don't know the above formula, can we show that \[ \sum\limits_{k=2}^\infty\displaystyle\ln\left(1-\frac{1}{2^k-1}\right)
\] converges? The answer is yes! Take a suitable $N$ such that when $ k >N$, we always have $ \displaystyle \frac{1}{2^k - 1}<1$, consider the taylor expansion $ \displaystyle \ln (1+x)=x-\frac{1}{(1+c)^2}x^2$, for some $ c$ in between $ 0$ and $ x$, now consider $ |x|<1$ such that $ |c|<\delta <1$, then we get by putting $ x=x_k$, $ |x_k|<1$, \[
\frac{x_k^2}{(1+\delta)^2}<x_k-\ln(1+x_k)<\frac{x_k^2}{(1-\delta)^2},
\] actually $ x>\ln (1+x),\forall x>-1$ simply because $ e^x\ge 1+x$. Now let $ \displaystyle x_k=-\frac{1}{2^k-1}$, our required $ N$ is simply 1, so we know that $ \sum_{k=2}^\infty x_k^2$ converges, thus by above inequality, $ \sum_{k=2}^\infty (x_k-\ln(1+x_k))$ also converges by comparison test, since $ \sum_{k=2}^\infty x_k$ converges, $ \sum_{k=2}^\infty \ln(1+x_k)$ also converges, we are done. Moreover, $ \sum\limits_{k=2}^\infty\displaystyle\ln\left(1-\frac{1}{2^k-1}\right)=-\ln 2$.
Tuesday, February 16, 2010
歌…
最近迷上左遠藤正明同古泉一樹 d 高音 ... sosad。
From Yan Min:
MATH204 (Analysis II) 及 MATH323 (Topology) 的同學仔都會去，不是這兩個 course 的同學也歡迎參加！
From Yan Min:
(12/2/2010) I will organize a hiking on Saturday, Feb 20. We will meet at noon at the university bus station. You and your friends are welcome. The hiking in Hong Kong is generally not strenuous. However, I am not reponsible for your safety.
MATH204 (Analysis II) 及 MATH323 (Topology) 的同學仔都會去，不是這兩個 course 的同學也歡迎參加！
Saturday, February 13, 2010
人情朱古力
收到 d 咁 ge 野，唔知點算好 = =。
今日陪屋企人睇錦衣衛。呢套片由頭到尾都係打打打，我覺得非常適合以下呢幾類人去睇
唔係以上呢幾類買飛前三思 (極度主觀 mode)。順帶一提，套野我睇到半路就走左，我都唔知結局係點，等到屋企人出黎就冇再提過套野。
今日陪屋企人睇錦衣衛。呢套片由頭到尾都係打打打，我覺得非常適合以下呢幾類人去睇
- 對甄子丹情有獨鍾
- 鍾意睇型仔 (冇靚女)
- 鍾意睇打鬥鏡頭
- 饑不擇食
唔係以上呢幾類買飛前三思 (極度主觀 mode)。順帶一提，套野我睇到半路就走左，我都唔知結局係點，等到屋企人出黎就冇再提過套野。
Problems of today's MATH202 tutorial notes #15
Problem 3. Let $ \{a_n\}$ and $ \{b_n\}$ be two sequences such that $ \lim_{n\to\infty}a_n=\lim_{n\to\infty}b_n=c$, suppose $ f'(c)$ exists. Show that $ \displaystyle \lim_{n\to\infty}\frac{f(b_n)-f(a_n)}{b_n-a_n}=f'(c)$.
My way.
I have to put some restictions to ensure my deduction is correct. If $ f'(x)$ is continuous near $ c$, then we are done with the Mean Value Theorem. But it, first and foremost, requires $ f(x)$ to be differentiable.
To avoid continuity of derivative, we inevitably set Mean Value Theorem aside, then differentiability of $ f(x)$ other than $ c$ doesn't carry weight any more. But I have to suppose we always have $ \boxed{a_n<c<b_n}$ or $ \boxed{b_n<c<a_n}$ for sufficiently large $ n$, this assumption will be used later on. By the fact that the existence of first order derivative implies the existance of linear approximation near $ c$, we have for any $ x$ near $ c$, \[f(x)=f'(c)(x-c)+f(c)+o(x-c),
\] Here for any $ \epsilon >0$, there exists a $ \delta > 0$ such that $ \displaystyle 0<|x-c|<\delta \implies \left|\frac{o(x-c)}{x-c}\right|<\frac{\epsilon}{2}$.
While for any $\delta_0 >0$, there exists an $ N$ such that $ n>N\implies |b_n-c|, |a_n-c|<\delta_0$, we take $ \delta_0<\delta$, now for $ n>N$,\begin{align*}
&{\color{white}=}\left|\frac{f(b_n)-f(a_n)}{b_n-a_n}-f'(c)\right|\\
&=\left|\frac{f'(c)(b_n-c-(a_n-c))+o(b_n-c)+o(a_n-c)}{b_n-a_n}-f'(c)\right|\\
&=\left|\frac{o(b_n-c)+o(a_n-c)}{b_n-a_n}\right| \\
&\leq \left|\frac{o(b_n-c)}{b_n-c}\right|\left|\frac{b_n-c}{b_n-a_n}\right|+\left|\frac{o(a_n-c)}{a_n-c}\right|\left|\frac{a_n-c}{b_n-a_n}\right| \\
&<\left|\frac{o(b_n-c)}{b_n-c}\right|+\left|\frac{o(a_n-c)}{a_n-c}\right|\text{(by the assumption)}\\
&<\epsilon.
\end{align*}
Redo example 10. Show that $ \displaystyle 2<65^{1/6}<2+\frac{1}{192}$.
My way.
The left hand side is obvious. For the right hand side, observe that \[
65=2\left(1+\frac{1}{2^6}\right)^{\frac{1}{6}}<2\left(1+\frac{1}{6\cdot 2^6}\right)=2+\frac{1}{192}.
\] We have used $ (1+x)^\alpha \leq 1+\alpha x,\forall x\ge 0,\forall \alpha \in[0,1]$.
Problem 6. Let $ f:[0,\infty)\to\mathbb{R}$ be continuous and $ f(0)=0$. If $ |f'(x)|<|f(x)|$ for very $ x>0$, show that $ f(x)=0$, for every $ x\in[0,\infty)$.
My way.
Instead of considering $ [0,\frac{1}{2}]$, we can consider any interval $ [0,p]$, $ p<1$ first. It can be shown that by mean value theorem,\begin{align*}
|f(x)-f(0)|&<|f(y_n)||x|\\
&=|f(y_n)-f(0)||x|\\
&<|f(y_{n-1})||x||y_n|\\
&<\cdots \\
&<|x||y_n|\cdots |y_2||f(y_1)|\\
&<p^n|f(y_1)|,\forall x\in [0,p].
\end{align*} Letting $ n\to\infty$, we get $ f(x)=\inf\{p^n|f(y_1)|:n\in\mathbb{N}\}=0$. We can show by induction that $ f(x)=0$, for all $ x\in [(n-1)p,np],n\in\mathbb{N}$ in the same manner.
Problem 9. Give an example of a function that is differentiable on $ (0,1)$ and $ f(0)=f(1)$ but does not satisfy the Rolle's Theorem.
My way.
Define $ f(x)=\sqrt{x},\forall x\in[0,1)$ and $ f(1) = 0$.
Additional problem. Let $ f(x)$ be a differentiable on $ [a,b]$, $ f'(a)<f'(b),$ for any $ y_0\in (f'(a),f'(b))$, prove that there exists $ c\in(a,b)$ such that $ f'(c)=y_0$.
My way.
Since that $ f$ is differentiable cannot imply the continuity of $ f'$. Intermediate value theorem fails to work here. We on the contrary define a new continuous function, $ g(x) = f(x)-y_0 x$. It can be easily varified that $ g'(a)=f'(a)-y_0<0$ and $ g'(b)=f'(b)-y_0>0$, then extreme value cannot be attained at the end point, the minima must lie somewhere else in the interval $ (a,b)$, hence there exists $ c\in(a,b)$ such that $ g'(c)=0\implies f'(c)=y_0$.
My way.
I have to put some restictions to ensure my deduction is correct. If $ f'(x)$ is continuous near $ c$, then we are done with the Mean Value Theorem. But it, first and foremost, requires $ f(x)$ to be differentiable.
To avoid continuity of derivative, we inevitably set Mean Value Theorem aside, then differentiability of $ f(x)$ other than $ c$ doesn't carry weight any more. But I have to suppose we always have $ \boxed{a_n<c<b_n}$ or $ \boxed{b_n<c<a_n}$ for sufficiently large $ n$, this assumption will be used later on. By the fact that the existence of first order derivative implies the existance of linear approximation near $ c$, we have for any $ x$ near $ c$, \[f(x)=f'(c)(x-c)+f(c)+o(x-c),
\] Here for any $ \epsilon >0$, there exists a $ \delta > 0$ such that $ \displaystyle 0<|x-c|<\delta \implies \left|\frac{o(x-c)}{x-c}\right|<\frac{\epsilon}{2}$.
While for any $\delta_0 >0$, there exists an $ N$ such that $ n>N\implies |b_n-c|, |a_n-c|<\delta_0$, we take $ \delta_0<\delta$, now for $ n>N$,\begin{align*}
&{\color{white}=}\left|\frac{f(b_n)-f(a_n)}{b_n-a_n}-f'(c)\right|\\
&=\left|\frac{f'(c)(b_n-c-(a_n-c))+o(b_n-c)+o(a_n-c)}{b_n-a_n}-f'(c)\right|\\
&=\left|\frac{o(b_n-c)+o(a_n-c)}{b_n-a_n}\right| \\
&\leq \left|\frac{o(b_n-c)}{b_n-c}\right|\left|\frac{b_n-c}{b_n-a_n}\right|+\left|\frac{o(a_n-c)}{a_n-c}\right|\left|\frac{a_n-c}{b_n-a_n}\right| \\
&<\left|\frac{o(b_n-c)}{b_n-c}\right|+\left|\frac{o(a_n-c)}{a_n-c}\right|\text{(by the assumption)}\\
&<\epsilon.
\end{align*}
Redo example 10. Show that $ \displaystyle 2<65^{1/6}<2+\frac{1}{192}$.
My way.
The left hand side is obvious. For the right hand side, observe that \[
65=2\left(1+\frac{1}{2^6}\right)^{\frac{1}{6}}<2\left(1+\frac{1}{6\cdot 2^6}\right)=2+\frac{1}{192}.
\] We have used $ (1+x)^\alpha \leq 1+\alpha x,\forall x\ge 0,\forall \alpha \in[0,1]$.
Problem 6. Let $ f:[0,\infty)\to\mathbb{R}$ be continuous and $ f(0)=0$. If $ |f'(x)|<|f(x)|$ for very $ x>0$, show that $ f(x)=0$, for every $ x\in[0,\infty)$.
My way.
Instead of considering $ [0,\frac{1}{2}]$, we can consider any interval $ [0,p]$, $ p<1$ first. It can be shown that by mean value theorem,\begin{align*}
|f(x)-f(0)|&<|f(y_n)||x|\\
&=|f(y_n)-f(0)||x|\\
&<|f(y_{n-1})||x||y_n|\\
&<\cdots \\
&<|x||y_n|\cdots |y_2||f(y_1)|\\
&<p^n|f(y_1)|,\forall x\in [0,p].
\end{align*} Letting $ n\to\infty$, we get $ f(x)=\inf\{p^n|f(y_1)|:n\in\mathbb{N}\}=0$. We can show by induction that $ f(x)=0$, for all $ x\in [(n-1)p,np],n\in\mathbb{N}$ in the same manner.
Problem 9. Give an example of a function that is differentiable on $ (0,1)$ and $ f(0)=f(1)$ but does not satisfy the Rolle's Theorem.
My way.
Define $ f(x)=\sqrt{x},\forall x\in[0,1)$ and $ f(1) = 0$.
Additional problem. Let $ f(x)$ be a differentiable on $ [a,b]$, $ f'(a)<f'(b),$ for any $ y_0\in (f'(a),f'(b))$, prove that there exists $ c\in(a,b)$ such that $ f'(c)=y_0$.
My way.
Since that $ f$ is differentiable cannot imply the continuity of $ f'$. Intermediate value theorem fails to work here. We on the contrary define a new continuous function, $ g(x) = f(x)-y_0 x$. It can be easily varified that $ g'(a)=f'(a)-y_0<0$ and $ g'(b)=f'(b)-y_0>0$, then extreme value cannot be attained at the end point, the minima must lie somewhere else in the interval $ (a,b)$, hence there exists $ c\in(a,b)$ such that $ g'(c)=0\implies f'(c)=y_0$.
Friday, February 12, 2010
Today's MATH190 problems in tutorial notes (the remaining is basic)
Problem 5. Let $ a,b,c>0$ be the sidelengths of a triangle. Prove that \[
a^2b(a-b)+b^2c(b-c)+c^2a(c-a)\ge 0.
\] My way.
We use the usual substitution, $(a,b,c)=(x+y,x+z,y+z)$, $ x,y,z>0$, then the original inequality is equivalent to \[
x^3y+y^3z+z^3x\ge xyz(x+y+z).
\] Finally, the last inequality is easy enough to see by noting that \[
x^3y+y^3z+z^3x = xyz\left(\frac{x^2}{z}+\frac{y^2}{x}+\frac{z^2}{y}\right),
\] we are done.
We are learning how to solve ODE. Now for those who has learnt ODE in secondary school (took AL applied maths paper II), you must be able to do the following.
a^2b(a-b)+b^2c(b-c)+c^2a(c-a)\ge 0.
\] My way.
We use the usual substitution, $(a,b,c)=(x+y,x+z,y+z)$, $ x,y,z>0$, then the original inequality is equivalent to \[
x^3y+y^3z+z^3x\ge xyz(x+y+z).
\] Finally, the last inequality is easy enough to see by noting that \[
x^3y+y^3z+z^3x = xyz\left(\frac{x^2}{z}+\frac{y^2}{x}+\frac{z^2}{y}\right),
\] we are done.
We are learning how to solve ODE. Now for those who has learnt ODE in secondary school (took AL applied maths paper II), you must be able to do the following.
- Evaluate $\displaystyle u(x)=1+\frac{x^3}{3!}+\frac{x^6}{6!}+\frac{x^9}{9!}+\cdots$, how do you link it with solving ODE? Of couse the substitution of cube root of unity will do in this question.
- Let $ f (x)$ be a differentiable function on $ [0, 1], f (0) = 0 $ and $f (1) = 1$, prove that $\displaystyle \int_0^1|f(x)-f'(x)|\,dx\ge \frac{1}{e}$. Once again, technique involved in solving ODE is needed. Can you recall it?
Tuesday, February 9, 2010
開始忙了
今日好充實，朝早上 (訓) 完 MATH151 再去再聽 eating style (HL001)，然後食午餐再備課備到點半上 MATH204。嚴民 d 堂講得好快，又易明，可惜一個星期得兩堂，如果一星期有四堂我都會肯去。落左堂之後同 204 同學做功課同備課去到 5:45，六點去 MATH204 tutorial lesson。
但奇怪嚴民教授明明 o係 course webpage 寫住
好在當時 save 左 ust 搵房網址入電腦 (出發時先醒起 3215 房間)，點我，慳左好多功夫，但原來 3215 係一個錯 ge 地址 (3215 係 TA 房)，有 4 至 5 個都走錯左地方。搵房果陣有個同班的人搵我講野...，o係果時先知道原來成日同班內地生傾計果個人都識講廣東話... (堔圳學生)，俾佢呃左好耐 = =，搞到我一直都唔敢搵佢講野。最後大家都要返返去 3584 上堂。
今次 tutorial 堂好奇怪 (奇怪在變返正常)，真係有個 PG 黎做 tutor...，平時都係教授一手包辦埋 tutorial 堂。老實，有少少失望。
I have come arcoss a question in uwants, prove that $ \tan 1^{\circ}$ is irrational, and here is the discussion.
I suppose that $ \tan 1^{\circ}$ is rational, then by the identity
$ \displaystyle \tan (30 \theta)=\frac{\sum_{k=1}^{15}(-1)^{k+1}\binom{30}{2k-1}\tan^{2k-1}\theta}{\sum_{k=0}^{15}(-1)^k\binom{30}{2k}\tan^{2k}\theta}$
We have by putting $ \theta = 1^{\circ}$, $ \displaystyle \frac{1}{\sqrt{3}} =\tan (30^{\circ})=\frac{\sum_{k=1}^{15}(-1)^{k+1}\binom{30}{2k-1}\tan^{2k-1}1^{\circ}}{\sum_{k=0}^{15}(-1)^k\binom{30}{2k}\tan^{2k}1^{\circ}}$, this shows that $ \displaystyle\frac{1}{\sqrt{3}}$ is rational, a contradiction. I hope this is one of the way that apook (koopa) thinks of.
但奇怪嚴民教授明明 o係 course webpage 寫住
(5/2/2010) Tutorial times set at Tuesday, 18:00 - 18:50, in room 3215.
好在當時 save 左 ust 搵房網址入電腦 (出發時先醒起 3215 房間)，點我，慳左好多功夫，但原來 3215 係一個錯 ge 地址 (3215 係 TA 房)，有 4 至 5 個都走錯左地方。搵房果陣有個同班的人搵我講野...，o係果時先知道原來成日同班內地生傾計果個人都識講廣東話... (堔圳學生)，俾佢呃左好耐 = =，搞到我一直都唔敢搵佢講野。最後大家都要返返去 3584 上堂。
今次 tutorial 堂好奇怪 (奇怪在變返正常)，真係有個 PG 黎做 tutor...，平時都係教授一手包辦埋 tutorial 堂。老實，有少少失望。
I have come arcoss a question in uwants, prove that $ \tan 1^{\circ}$ is irrational, and here is the discussion.
I suppose that $ \tan 1^{\circ}$ is rational, then by the identity
$ \displaystyle \tan (30 \theta)=\frac{\sum_{k=1}^{15}(-1)^{k+1}\binom{30}{2k-1}\tan^{2k-1}\theta}{\sum_{k=0}^{15}(-1)^k\binom{30}{2k}\tan^{2k}\theta}$
We have by putting $ \theta = 1^{\circ}$, $ \displaystyle \frac{1}{\sqrt{3}} =\tan (30^{\circ})=\frac{\sum_{k=1}^{15}(-1)^{k+1}\binom{30}{2k-1}\tan^{2k-1}1^{\circ}}{\sum_{k=0}^{15}(-1)^k\binom{30}{2k}\tan^{2k}1^{\circ}}$, this shows that $ \displaystyle\frac{1}{\sqrt{3}}$ is rational, a contradiction. I hope this is one of the way that apook (koopa) thinks of.
Monday, February 8, 2010
余振強紀念中學校友會成立十週年既會暨老師榮休宴
日期: 二零一零年三月二十日
時間: 下午四時正 (參觀校舍)
晚上七時正 (晚宴)
地點: 學校禮堂
內容: 週年會員大會及祝賀趙錦輝老師於09年榮休，亦邀請嘉賓老師(現任及退休老師)出席，設置自助晚宴及神秘節目，歡迎攜眷出席。
入場票價: 每位參加者$100，每席10位
付款方式: 透過銀行入數到校友會的銀行戶口
(恆生銀行戶口: 024-242-4-039747)，
入數紙需連同入數人姓名、參加者人數、日期和聯絡電話一併 fax(2760 1488) 或郵寄到學校。
截止日期: 二零一零年二月二十八日
聯絡方法: 陳學明 9031 0921
蔡文遜 9251 4420
勞國樑老師 9273 8036
Email: yckmcaa@gmail.com
Problem. Show that for any $ a,b,c>0$ (not necessarily integer), $ \displaystyle a^ab^bc^c\ge (abc)^{(a+b+c)/3}$.
這是一條例題，李教授以此來 dem 一 dem Chebyshev 不等式的用法，其後便給我們一個練習：
重證這一條不等式，但你只能使用 AM-GM inequality。
這是不難的，中七的學生可當練習。
時間: 下午四時正 (參觀校舍)
晚上七時正 (晚宴)
地點: 學校禮堂
內容: 週年會員大會及祝賀趙錦輝老師於09年榮休，亦邀請嘉賓老師(現任及退休老師)出席，設置自助晚宴及神秘節目，歡迎攜眷出席。
入場票價: 每位參加者$100，每席10位
付款方式: 透過銀行入數到校友會的銀行戶口
(恆生銀行戶口: 024-242-4-039747)，
入數紙需連同入數人姓名、參加者人數、日期和聯絡電話一併 fax(2760 1488) 或郵寄到學校。
截止日期: 二零一零年二月二十八日
聯絡方法: 陳學明 9031 0921
蔡文遜 9251 4420
勞國樑老師 9273 8036
Email: yckmcaa@gmail.com
Problem. Show that for any $ a,b,c>0$ (not necessarily integer), $ \displaystyle a^ab^bc^c\ge (abc)^{(a+b+c)/3}$.
這是一條例題，李教授以此來 dem 一 dem Chebyshev 不等式的用法，其後便給我們一個練習：
重證這一條不等式，但你只能使用 AM-GM inequality。
這是不難的，中七的學生可當練習。
A PuiChing Question (to someone)
Problem. Denote $ [x]$ the greastest integer not exceeding $ x$, calculate $ \displaystyle\sum\limits_{k=1}^{100}[\sqrt{k(k+4)+20}]$.
Solution.
First note that $ \sqrt{k(k+4)+20}=(k+2)\sqrt{1+\big(4/(k+2)\big)^2}$, it conveys us some messages. As $ k$ increases, we have $ \sqrt{k(k+4)+20}= k+2 + f(k)$, where $ f(k)\to 0$ as $ k\to\infty$. But only the integral part deserves our concern, so if $ k+2 <\sqrt{k(k+4)+20}<k+3$, then everything goes smooth and we have $ [\sqrt{k(k+4)+20}]=k+2$. But when does this inequality hold? Just solve the inequality we have $ k>5.5$, so the inequality is true of $ k\ge 6$ and thus the value should be $ 5+5+6+7+8+8+9+10+\cdots +102 = 5256$. $ \blacksquare$
Solution.
First note that $ \sqrt{k(k+4)+20}=(k+2)\sqrt{1+\big(4/(k+2)\big)^2}$, it conveys us some messages. As $ k$ increases, we have $ \sqrt{k(k+4)+20}= k+2 + f(k)$, where $ f(k)\to 0$ as $ k\to\infty$. But only the integral part deserves our concern, so if $ k+2 <\sqrt{k(k+4)+20}<k+3$, then everything goes smooth and we have $ [\sqrt{k(k+4)+20}]=k+2$. But when does this inequality hold? Just solve the inequality we have $ k>5.5$, so the inequality is true of $ k\ge 6$ and thus the value should be $ 5+5+6+7+8+8+9+10+\cdots +102 = 5256$. $ \blacksquare$
Saturday, February 6, 2010
Last problem of MATH202 tutorial note #14
Problem. Consider a continuous function $ f$ on $ [a,b]$, suppose for any $ a\leq x\leq b$, there is $ a\leq y\leq b$, such that $ |f(y)|\leq \frac{1}{2}|f(x)|$. Prove that there is a $ c\in[a,b]$ such that $ f(c)=0$.
My way.
It is often easy to prove the converse to be impossible for this kind of problems. We on the contrary suppose that $ f(x)\neq 0,\forall x\in[a,b]$, then either $ f(x)>0$ or $ f(x)<0$ for all $ x\in[a,b]$.
We assume that $ f(x)>0$, due to continuity there exists $ x_0$ such that
$ (*):\qquad f(x)\ge f(x_0)>0, \forall x\in[a,b].$
However, we have the following observation.
$ \exists y_1\in [a,b], f(y_1)\leq \frac{1}{2}f(y_0)$;
$ \exists y_2\in [a,b], f(y_2)\leq \frac{1}{2}f(y_1)$;
$ \qquad \vdots$
$ \exists y_n\in [a,b], f(y_n)\leq \frac{1}{2}f(y_{n-1})$.
thus $ \displaystyle f(y_n)\leq \frac{1}{2}f(y_{n-1})\leq \left(\frac{1}{2}\right)^2f(y_{n-2})\leq \cdots \leq \left(\frac{1}{2}\right)^nf(y_0)$. Since right hand side tends to 0 as $ n\to\infty$, there exists an $ N$ such that $ n>N\implies f(y_n)<\epsilon < f(x_0)$, a contradiction with (*). The case that $ f(x)<0$ is essentially the same, hence there exists $ c\in[a,b]$ such that $ f(c)=0$.
Alternatively, if we know that any bounded sequence have a convergent subsequence, then this problem can be solved in a much neater way. As above we show that \[
|f(y_n)|\leq \frac{1}{2}|f(y_{n-1})|\leq \left(\frac{1}{2}\right)^2|f(y_{n-2})|\leq \cdots \leq \left(\frac{1}{2}\right)^n|f(y_0)|,\forall n \in \mathbb{N}\cup\{0\},
\] then since there exists a convergent subsequence $ \{y_{n_k}\}$ with $ \lim_{k\to\infty}y_{n_k}=c\in[a,b]$, thus taking limit on the proved inequality, we get \[
0\leq \lim_{k\to\infty}|f(y_{n_k})|=\left|f\left(\lim_{k\to\infty}y_{n_k}\right)\right| =|f(c)|\leq\lim_{k\to\infty}\left(\frac{1}{2}\right)^{n_k}|f(y_0)| = 0,
\] here we used the fact that a composite of continuous function is still continuous, we are done.
My way.
It is often easy to prove the converse to be impossible for this kind of problems. We on the contrary suppose that $ f(x)\neq 0,\forall x\in[a,b]$, then either $ f(x)>0$ or $ f(x)<0$ for all $ x\in[a,b]$.
We assume that $ f(x)>0$, due to continuity there exists $ x_0$ such that
$ (*):\qquad f(x)\ge f(x_0)>0, \forall x\in[a,b].$
However, we have the following observation.
$ \exists y_1\in [a,b], f(y_1)\leq \frac{1}{2}f(y_0)$;
$ \exists y_2\in [a,b], f(y_2)\leq \frac{1}{2}f(y_1)$;
$ \qquad \vdots$
$ \exists y_n\in [a,b], f(y_n)\leq \frac{1}{2}f(y_{n-1})$.
thus $ \displaystyle f(y_n)\leq \frac{1}{2}f(y_{n-1})\leq \left(\frac{1}{2}\right)^2f(y_{n-2})\leq \cdots \leq \left(\frac{1}{2}\right)^nf(y_0)$. Since right hand side tends to 0 as $ n\to\infty$, there exists an $ N$ such that $ n>N\implies f(y_n)<\epsilon < f(x_0)$, a contradiction with (*). The case that $ f(x)<0$ is essentially the same, hence there exists $ c\in[a,b]$ such that $ f(c)=0$.
Alternatively, if we know that any bounded sequence have a convergent subsequence, then this problem can be solved in a much neater way. As above we show that \[
|f(y_n)|\leq \frac{1}{2}|f(y_{n-1})|\leq \left(\frac{1}{2}\right)^2|f(y_{n-2})|\leq \cdots \leq \left(\frac{1}{2}\right)^n|f(y_0)|,\forall n \in \mathbb{N}\cup\{0\},
\] then since there exists a convergent subsequence $ \{y_{n_k}\}$ with $ \lim_{k\to\infty}y_{n_k}=c\in[a,b]$, thus taking limit on the proved inequality, we get \[
0\leq \lim_{k\to\infty}|f(y_{n_k})|=\left|f\left(\lim_{k\to\infty}y_{n_k}\right)\right| =|f(c)|\leq\lim_{k\to\infty}\left(\frac{1}{2}\right)^{n_k}|f(y_0)| = 0,
\] here we used the fact that a composite of continuous function is still continuous, we are done.
Left a name in Excalibur!
There is a fairly easy question in the problem corner of the latest mathematical excalibur:
Show that $ \displaystyle \sum_{k=0}^{n-1}(-1)^k\cos^n\left(\frac{k\pi}{n}\right)=\frac{n}{2^{n-1}}$, for any positive integer $ n$.
The term $ 2^{n-1}$ is reminiscent of something, isn't it? What is it? How it works?
But I guess there must be some combinatorics/probabilistic argument, especially the use of inclusion-exclusion principle.
I am glad that Kin Li adopted my solution of the strange inequality and quoted my name^^.
For details:
http://www.math.ust.hk/excalibur/v14_n3.pdf
(You can search LEE Ching Cheong to see where I am XD)
Show that $ \displaystyle \sum_{k=0}^{n-1}(-1)^k\cos^n\left(\frac{k\pi}{n}\right)=\frac{n}{2^{n-1}}$, for any positive integer $ n$.
The term $ 2^{n-1}$ is reminiscent of something, isn't it? What is it? How it works?
But I guess there must be some combinatorics/probabilistic argument, especially the use of inclusion-exclusion principle.
I am glad that Kin Li adopted my solution of the strange inequality and quoted my name^^.
For details:
http://www.math.ust.hk/excalibur/v14_n3.pdf
(You can search LEE Ching Cheong to see where I am XD)
Friday, February 5, 2010
Another basic counting in discusshk
Problem. There are 6 distinct presents. How many ways to distribute the presents to three people if everyone at least have one present?
In the past I have answered how to distribute 20 different presents to 6 people (of course different people!). Intrinsically two problems are the same. The complexity lies here is the way we draw presents, it is not of necessity to distribute all presents to them.
Ok, now back to this question, just applied the same trick that I have developed in the past, this is an easy problem if one can set up a reccurence relation like the following:
Define $s_n = \{\text{number of way of distribution if exactly \textit{n} people have present(s).}\}$, \[ s_n = ({n+1})^6-\sum_{i=0}^{n-1}\binom{n}{i}s_i,
\] setting $ i=1,2$ and defining $ s_0=1$, one can have that \[
\left\{\begin{array}{l}s_0=1\\s_1 = 2^6 - 1\\s_2 = 3^6 - 2\cdot 2^6 + 1\\s_3 = 4^6 - 3^7 + 3\cdot 2^6 - 1 = 2100\end{array}\right.\]
One may ask what happens when presents are identical, the solution is much trivial and I guess every statistic (especially MAEC ?) student in UST is able to count it.here is the PDF concerning 20 presents case
Click me
In the past I have answered how to distribute 20 different presents to 6 people (of course different people!). Intrinsically two problems are the same. The complexity lies here is the way we draw presents, it is not of necessity to distribute all presents to them.
Ok, now back to this question, just applied the same trick that I have developed in the past, this is an easy problem if one can set up a reccurence relation like the following:
Define $s_n = \{\text{number of way of distribution if exactly \textit{n} people have present(s).}\}$, \[ s_n = ({n+1})^6-\sum_{i=0}^{n-1}\binom{n}{i}s_i,
\] setting $ i=1,2$ and defining $ s_0=1$, one can have that \[
\left\{\begin{array}{l}s_0=1\\s_1 = 2^6 - 1\\s_2 = 3^6 - 2\cdot 2^6 + 1\\s_3 = 4^6 - 3^7 + 3\cdot 2^6 - 1 = 2100\end{array}\right.\]
One may ask what happens when presents are identical, the solution is much trivial and I guess every statistic (especially MAEC ?) student in UST is able to count it.here is the PDF concerning 20 presents case
Click me
Wednesday, February 3, 2010
Tuesday, February 2, 2010
An ugly limit
$\displaystyle \lim_{n\to\infty}\left\{\frac{1}{n^{4}}\left (\sum_{k=1}^{n}k^{2}\int_{k}^{k+1}x\ln\big( (x-k)(k+1-x)\big) \mathrm{d} x\right )\right\}$.
Subscribe to:
Posts (Atom)