\documentclass[a4paper]{scrartcl}%{{{1

\usepackage{array}
\usepackage{listings}
\usepackage{titlesec}
\usepackage{fancyhdr}
\usepackage{fancyref}
\usepackage{clrscode}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage[x11names]{xcolor}
\usepackage[unicode]{hyperref}
\usepackage{graphicx,tabularx}
\usepackage[shortlabels]{enumitem}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{mathtools}

\usepackage{setspace}
\usepackage{lastpage}
\usepackage{extramarks}
\usepackage{chngpage}
\usepackage{soul,color}

\usepackage[adobe-utopia]{mathdesign}
\usepackage{inconsolata}
\usepackage[T1]{fontenc}

\newcommand{\Class}{Mathematics for Computer Science}
\newcommand{\ClassInstructor}{Andrew C. Yao}

\newtheorem{definition}{Definition}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}

\DeclareMathOperator*{\Var}{Var}
\DeclareMathOperator*{\E}{E}
\providecommand{\abs}[1]{\left\lvert{#1}\right\rvert}
\providecommand{\norm}[1]{\left\lVert{#1}\right\rVert}
\providecommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\providecommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\providecommand{\pa}[1]{\left({#1}\right)}

% % In case you need to adjust margins:
% \topmargin=-0.45in%
% \evensidemargin=0in%
% \oddsidemargin=0in%
% \textwidth=6.5in%
% \textheight=9.0in%
% \headsep=0.25in%

\newcommand{\StudentName}{Yichao Zhou}
\newcommand{\StudentClass}{CST-10}
\newcommand{\StudentNumber}{2011011299}

% Setup the header and footer
\pagestyle{fancy}%
\lhead{\StudentName}%
\chead{\Title}%
\rhead{\firstxmark}%
\lfoot{\lastxmark}%
\cfoot{}%
\rfoot{Page\ \thepage\ of\ \protect\pageref{LastPage}}%
\renewcommand\headrulewidth{.5pt}%
\renewcommand\footrulewidth{.5pt}%

\newcommand{\enterProblemHeader}[1]{\nobreak\extramarks{#1}{#1 continued on next page\ldots}\nobreak%
\nobreak\extramarks{#1 (continued)}{#1 continued on next page\ldots}\nobreak}%
\newcommand{\exitProblemHeader}[1]{\nobreak\extramarks{#1 (continued)}{#1 continued on next page\ldots}\nobreak%
\nobreak\extramarks{#1}{}\nobreak}%

\newcommand{\homeworkProblemName}{}%
\newcounter{homeworkProblemCounter}%
\newenvironment{homeworkProblem}[1][Problem \arabic{homeworkProblemCounter}]%
{\stepcounter{homeworkProblemCounter}%
  \renewcommand{\homeworkProblemName}{#1}%
  \section*{\homeworkProblemName}%
\enterProblemHeader{\homeworkProblemName}}%
{\exitProblemHeader{\homeworkProblemName}}%

\newcommand{\homeworkSectionName}{}%
\newlength{\homeworkSectionLabelLength}{}%
\newenvironment{homeworkSection}[1]%
{% We put this space here to make sure we're not connected to the above.

  \renewcommand{\homeworkSectionName}{#1}%
  \settowidth{\homeworkSectionLabelLength}{\homeworkSectionName}%
  \addtolength{\homeworkSectionLabelLength}{0.25in}%
  \changetext{}{-\homeworkSectionLabelLength}{}{}{}%
  \subsection*{\homeworkSectionName}%
\enterProblemHeader{\homeworkProblemName\ [\homeworkSectionName]}}%
{\enterProblemHeader{\homeworkProblemName}%

% We put the blank space above in order to make sure this margin
% change doesn't happen too soon.
\changetext{}{+\homeworkSectionLabelLength}{}{}{}}%

\newcommand{\Answer}{\ \\{\bfseries \sffamily Answer: }}
\newcommand{\Remark}{\ \\{\bfseries \sffamily Remark: }}
\newcommand{\Acknowledgement}[1]{\ \\{\bfseries \sffamily Acknowledgement:} #1}

% Make title
\title{\textmd{\bf \Class: \Title}\\{\large Instructed by \textit{\ClassInstructor}}\\\normalsize\vspace{0.1in}\small{Due\ on\ \DueDate}}
\date{}
\author{\textbf{\StudentName}\ \ \StudentClass\ \ \StudentNumber}

% Homework Information {{{1
\newcommand{\Title}{Homework 3}
\newcommand{\DueDate}{Mar 13, 2011}

\begin{document} %{{{1
\begin{spacing}{1.1}
  \maketitle \thispagestyle{empty}

  \begin{homeworkProblem}[Problem 5.4.5 on Page 85] %{{{2
    We flip a coin $n$ times $(n \ge 1)$. For which values of $n$ are the
    following pairs of events independent?

    \begin{enumerate}[(a)]
      \item The first coin flip was head, the number of all heads was even.
      \item The first coin flip was head, the number of all heads was more than
        the number of tails.
      \item The number of heads was even, the number of heads was more than the
        number of tails.
    \end{enumerate}
    
    \Answer

    We define the sample space $S$ as all the result we flip a coin $n$ times.
    \begin{enumerate}[(a)]
        %{{{ (a)
      \item Let $E_u$ be the event that first coin flip was heads.\par
        Let $E_v$ be the event that all heads was even.

        \begin{equation}
          \begin{aligned}
            \Pr(E_u) &= \frac{\abs{E_u}}{\abs{S}} \\
                 &= \frac{2^{n-1}}{2^n} \\
                 &= \frac{1}{2}
          \end{aligned}
          \label{eq:p1_1}
        \end{equation}

        For $E_v$, we know that for every scheme that there are even heads, we
        can flip the first coin.  Then there will be odd heads.  The reverse
        operation holds too.  So we can conclude that $\Pr(E_v)$ =
        $\Pr(\overline{E_v})$.
        \begin{equation}
          \begin{aligned}
            \Pr(E_v) &= \frac{\abs{E_v}}{\abs{S}} \\
                   &= \frac{1}{2}
          \end{aligned}
          \label{eq:p1_2}
        \end{equation}

        For $\Pr(E_v \cup E_u)$, let us consider about the second coin.  Just
        as the preceding method, when we can flip both the first and second
        coin we do not change the parity of the heads but the first coin is no
        longer head.  Also we can do the reverse option.  So this is a
        bijection. We can get $\Pr(E_v \cup E_u) = \Pr(E_v - E_v \cup E_u)$

        \begin{equation}
          \begin{aligned}
            \Pr(E_v \cup E_u) &= \frac{\abs{E_v \cup \E_u}}{\abs{S}} \\
                              &= \frac{\abs{E_v}}{2 \times \abs{S}} \\
                              &= \frac{1}{4}
          \end{aligned}
          \label{eq:p1_3}
        \end{equation}

        So we have
        \begin{equation}
          \Pr(E_v)\Pr(E_u) = \Pr(E_v \cap E_v)
          \label{eq:p1_1f}
        \end{equation}

        Thus they are independent events.

        %}}}
        %%{{{ (b)
      \item The probability of first coin being head is as same as that in (a).
        So $E_u=\frac{1}{2}$.  Then we need to discuss in case.
        \begin{enumerate}[i)]
          \item Suppose $N$ is even.  The probability that the number of all
            heads was more than the number of tails is
            \begin{equation}
              \begin{aligned}
                \Pr(E_v)
                &= \frac{\abs{E_v}}{\abs{S}} \\
                &= \frac{\sum_{i=\frac{n}{2}+1}^{n} \binom{n}{i}}{2^n} \\
                &= \frac{\left(2^n-\binom{n}{n/2}\right)/2}{2^n} \\
                &= \frac{1}{2} - \frac{\binom{n}{n/2}}{2^{n+1}}
              \end{aligned}
            \end{equation}

            As for $E_u \cap E_v$, the first coin is determinate.  We only need
            to consider the left $n-1$ coins.  So we have
            \begin{equation}
              \begin{aligned}
                \Pr(E_u \cap E_v)
                &= \frac{\abs{E_u \cap E_v}}{\abs{S}} \\
                &= \frac{\sum_{i=\frac{n}{2}}^{n} \binom{n-1}{i}}{2^n} \\
                &= \frac{\left(2^{n-1}\right)/2}{2^n} \\
                &= \frac{1}{4}
              \end{aligned}
            \end{equation}

            Obviously, this does not match $\Pr(E_u)\Pr(E_v) = \Pr(E_u \cap
            E_v)$.  So they are not independent when $N$ is even.
          \item Suppose $N$ is odd.  The probability that the number of all
            heads was more than the number of tails is almost the same as when
            $N$ is even.
            \begin{equation}
              \begin{aligned}
                \Pr(E_v)
                &= \frac{\abs{E_v}}{\abs{S}} \\
                &= \frac{\sum_{i=\frac{n+1}{2}}^{n} \binom{n}{i}}{2^n} \\
                &= \frac{2^n/2}{2^n} \\
                &= \frac{1}{2}
              \end{aligned}
            \end{equation}

            As for $E_u \cap E_v$, the first coin is determinate.  We only need
            to consider the left $n-1$ coins.  So we have
            \begin{equation}
              \begin{aligned}
                \Pr(E_u \cap E_v)
                &= \frac{\abs{E_u \cap E_v}}{\abs{S}} \\
                &= \frac{\sum_{i=\frac{n-1}{2}}^{n} \binom{n-1}{i}}{2^n} \\
                &= \frac{\left(2^{n-1}+\binom{n-1}{(n-1)/2}\right)/2}{2^n} \\
                &= \frac{1}{4} + \frac{\binom{n-1}{(n-1)/2}}{2^{n+1}}
              \end{aligned}
            \end{equation}

            Obviously, this does not match $\Pr(E_u)\Pr(E_v) = \Pr(E_u \cap
            E_v)$.  So they are not independent when $N$ is even.
        \end{enumerate}
        %}}}
        %{{{ (c)
      \item Let $E_u$ be the event that the number of heads was even. \par
        Let $E_v$ be the event that the number of heads was more than the number
        of tails.

        As (a) shows, $\Pr(E_u)=\frac{1}{2}$.  And as (b) shows,
        \begin{equation}
          \Pr(E_v)=
          \begin{dcases}
            \frac{1}{2}-\frac{\binom{n}{n/2}}{2^{n-1}} & n = 2k \\
            \frac{1}{2} & n = 2k+1
          \end{dcases}
        \end{equation}
        For all $k \in \mathbb{N}$.

        Also we can use the similar ways to get that
        \begin{equation}
          \Pr(E_u \cap E_v)=
          \begin{dcases}
            \frac{1}{4} - \frac{\binom{n-1}{n/2}}{2^{n}} & n=4k \\
            \frac{1}{4} - \frac{\binom{n-1}{(n-1)/2}}{2^{n+1}} & n=4k+1 \\
            \frac{1}{4} & n=4k+2 \\
            \frac{1}{4} + \frac{\binom{n-1}{(n-1)/2}}{2^{n+1}} & n=4k+3 \\
          \end{dcases}
        \end{equation}

        So they are not independent event.
        %}}}
    \end{enumerate}
  \end{homeworkProblem}

  \begin{homeworkProblem}[Problem 6.10.6 on Page 122] %{{{2
    Let $a > 1$, and $k, n > 0$. Prove that $a^k - 1 \mid a^n - 1$ if and only
    if $k \mid n$.

    \Answer
    \begin{description}
      \item[Necessity]
        \begin{proof}
          We need to proof that $a^k - 1 \mid a^n - 1$ if $k \mid n$.  
          We know that $x^p-1 = (x-1)(x^{p-1} + \dots + x + 1)$.
          Let $p = a^k$ and plug $p$ into the preceding equation.  We get
          $a^k - 1 \mid a^n - 1$.
        \end{proof}

      \item[Sufficiency]
        \begin{proof}
          Let $P(a) = a^k -1$.  Let $Q(a) = a^n - 1$.
          \begin{align}
            P(a) &= (a^{k-1} + a^{k-2} + \dots + a + 1) \\
            Q(a) &= (a^{n-1} + a^{n-2} + \dots + a + 1)
          \end{align}
          Because $a^k - 1 \mid a^n - 1$, so $P(x) \mid Q(x)$.  Suppose
          $Q(x)=P(x)R(x)$.  Let $R(x) = a_{n-k}x^{n-k} + a_{n-k-1}x^{n-k-1} +
          \dots1+ a_1x + a_0$.  $a_{n-k}$ must be $1$.  $Q(x)-P(x) \cdot
          x^{n-k} = x_{n-k-1} + \dots + x + 1$.  So $a_{n-k-1} \dots a_{n-2k}$
          must be $0$ and $a_{n-2k-1}$ must be $1$.  And keep on doing this
          \ldots Finally we will get $n-lk=0$.  And thus we proof that $k \mid
          n$.
        \end{proof}
    \end{description}

  \end{homeworkProblem}

  \begin{homeworkProblem}[Probblem 6.10.16 on Page 123] %{{{2
    Prove that for every positive integer $m$ there is a Fibonacci number
    divisible by $m$ (well, of course, $F_0 = 0$ is divisible by any $m$; we
    mean a larger one).

    \Answer Let $f_i=F_i \bmod m$ and define $f_0 = 0$.  Thus $f_i \in \{0 \dots
    m-1\}$.  We know that if two successive numbers occurs before them, then
    there will be a circle in the sequence.  Because $f_i \in \{0 \dots m-1 \}$
    the ways of two successive number is at most $(m-1)^2$.  So there must be a
    circle in this sequence.

    Suppose $f_{p}=f_{q} \text{and} f_{p+1} = f_{q+1}$ which $p<q$.  Because
    $f_i = F_i \bmod m$ and $F_i = F_{i-1} + F{i-2}$.  We will get
    $f_{p-1}=f_{q-1} \pmod{m}$.  Keep doing this operation, we will finally get
    $f_0 \equiv f_k \pmod{m}$.  And thus $f_k = 0$, which means $F_k \equiv 0
    \pmod{m}$.  So $m \mid F_k$.
  \end{homeworkProblem}

  \begin{homeworkProblem}[10.6.18] %{{{2
    Find integers $x$ and $y$ such that
    \begin{align}
      2x + y  & \equiv 4 \pmod{17} \label{eq:p4_1}\\
      5x - 5y & \equiv 9 \pmod{17} \label{eq:p4_2}
    \end{align}

    \Answer $\eqref{eq:p4_1} \times 5 + \eqref{eq:p4_2}$, we will get:
    \begin{equation}
      15x \equiv 12 \pmod{17}
    \end{equation}

    And we can get $x \equiv 11 \pmod{17}$.  Plug it into \fref{eq:p4_1} and we will get
    $y \equiv 16 \pmod{17}$.

    In conclusion,
    \begin{equation}
      \begin{aligned}
        x &= 11 +17k \\
        y &= 16 +17k
      \end{aligned}
    \end{equation}
    for all $k \in \mathbb{Z}$.
  \end{homeworkProblem}

  \begin{homeworkProblem}[Special Problem 1] %{{{2
    Consider a \textit{random walk} on a circle with nodes $v_0, v_1, \cdots
    ,v_{n-1}$, and an edge between $v_i$ and $v_{(i+1) \bmod n}$ for each of $i
    = 0, 1, 2, \cdots ,n-1$. Starting initially at $v_0$, in each step we move
    from the current node $v_i$ randomly to either $v_{(i-1) \bmod n}$ or
    $v_{(i+1) \bmod n}$ with equal probability. After $N$ steps, let $p_N$ be
    the probability that all $n$ nodes have been visited. Prove that $p_N \ge 1
    - \frac{cn}{\sqrt{N}}$ for some positive constant $c$.

    \Remark This implies that $p_N \to 1$ as $N \to 1$. Thus, an
    infinite random walk on such a circle will eventually visit all the nodes.

    \Answer 
    \begin{proof}
      Let $q_N$ be the probability that one person never walks across the
      origin through $N$ times \textit{random walk}.
      
      \begin{equation}
        \begin{aligned}
                     & \quad p_N \ge 1 - \frac{cn}{\sqrt{N}} \\
          \Leftarrow & \quad 1-p_N \le   \frac{cn}{\sqrt{N}} \\
          \Leftarrow & \quad q_N   \le   \frac{cn}{\sqrt{N}} 
        \end{aligned}
      \end{equation}

      So we only need to proof $q_N \le \frac{cn}{\sqrt{N}}$.  $q_N$ can be
      easily calculated:

      \begin{equation}
        \begin{aligned}
          q_N &= \sum_{i=\ceil{N/2-n/2}}^{\floor{N/2+n/2}} \binom{N}{N/2-n/2} \\
              &\le n \times \binom{N}{N/2} \\
              &\le n \times \frac{N!}{\pa{N/2}^2} \\
              &\le n \times \frac{e\sqrt{N}\pa{\frac{N}{e}}^N}{
                2\pi\frac{N}{2}\pa{\frac{N}{e}}^N
              } \\
              &= \frac{cn}{\sqrt{N}}
        \end{aligned}
      \end{equation}

      In this equation, we used the Stirling's bound for $n!$.
      \begin{equation}
        \sqrt{2\pi}n^{n+1/2}e^{-n} \le n! \le en^{n+1/2}e^{-n}
      \end{equation}
    \end{proof}
  \end{homeworkProblem}

  \begin{homeworkProblem}[Special Problem 2] %{{{2
    The probability space concept $\omega= (U, p)$ can be generalized to the
    case when $U$ is an infinite set $\{u_1,u_2,u_3,\cdots,u_n,\cdots\}$. As
    before, an \textit{event} $T$ is a subset of $U$, and $\Pr(T) = \sum_{u \in
    T}^{} p(u)$. Consider a random walk on an $n$-node circle (as in the
    previous problem) such that it halts as soon as all the nodes have been
    visited. We are interested in the probability $q_{n,i}$ for the random walk
    to halt at node $v_i$ (i.e. $v_i$ is the very last node that the random
    walk visits).  Clearly, for $n = 3$, we have $q_{3,1} = q_{3,2} =
    \frac{1}{2}$.

    \begin{enumerate}[(a)]
      \item Specify a probability space $\omega = (U, p)$ for this random walk.
        You may use an infinite $U$. Show that, according to your
        specification, $\sum_{u \in U}^{} p(u) = 1$.
      \item Derive the values of $q_{4,i}$ for $i = 1, 2, 3$.
      \item Determine $q_{n,i}$ for $1 \le i \le n-1$.
    \end{enumerate}

    \Answer
  \end{homeworkProblem}

  \begin{homeworkProblem}[Special Problem 3] %{{{2
    Let $P_{2n}$ be the set of all $(2n)!$ permutations of
    $\{1,2,3,\cdots,2n\}$. For any $\omega=(a_1,a_2,\cdots,a_{2n}) \in P_{2n}$,
    a pair of positions $(i, j)$ (where $i < j$) is called an inversion in
    $\omega$ if $ai > aj$.  For example, in the permutation $(a_1,a_2,a_3,a_4)
    = (2,4,1,3)$, $(2, 4)$ is an inversion as $a2 = 4 > a4 = 3$; in fact, in
    this case there are exactly $3$ inversions $(1, 3), (2, 3), (2, 4)$.

    For any $\omega = (a_1, a_2, \cdots, a_{2n}) \in P_{2n}$, let $f(\omega)$
    be the permutation obtained from $\omega$ by sorting the sublist of odd
    positions. That is, $f(\omega) = (b_1, b_2, \cdots, b_{2n}) \in P_{2n}$,
    where $b_k = a_k$ for $k = 2, 4, 6, \cdots, 2n$ and $b_1 < b_3 < b_5 <
    \cdots < b_{2n-1}$ is the sorted list of $a_1, a_3, \cdots, a_{2n-1}$. For
    example, for $\omega = (3, 8, 2, 5, 6, 7, 1, 4)$, $f(\omega) = (1, 8, 2, 5,
    3, 7, 6, 4)$. For a random $\omega$ uniformly chosen from $P_{2n}$, let
    $I_n$ be the random variable corresponding to the number of inversions in
    the permutation $f(\omega)$. Do the following problems:

    \begin{enumerate}[(a)]
      \item Determine $\E(I_n)$.
      \item Determine $\Var(I_n)$.
    \end{enumerate}

    \Remark For Question (a) above, let $h_n = E(I_n)$ be the answer, then $h_1
    = 1/2$, $h_2 = 13/6, h_3 = 5$. Your formula should be consistent with that.
    As explained in class, a \textit{closed-form formula} is a mathematical
    expression involving only a constant number of familiar function. For
    example, $\binom{n^2}{5n}+\frac{3n^4\log n}{1+2n}$ a closed-form formula,
    but $5 + \sum_{1 \le k \le n} k^3$ is not a closed-form formula.

    \Answer
    \begin{enumerate}[(a)]
      \item Let $X_n$ be the random variable representing the number of
        inversions in even positions.

        Let $Y_n$ be the random variable representing the number of inversions
        which one of numbers is in the even position and another is in the odd
        position.

        Since the odd positions are sorted, there will be no inversions in
        them.  Thus we know that $\E(I_n) = \E(X_n) + \E(Y_n)$.

        Finding $X_n$ is a classical problem.  Let's consider every number pair
        $\pa{i,\,j}$.  They have $\frac{1}{2}$ probability to be an inversion.
        So $X_n$ = $\binom{n}{2}/2 = n(n-1)/4$.

        For $Y_n$, consider each number in even position $2i$.  Then we
        enumerate its rank in odd position and suppose it is $j$.  Then we will
        have this equation:
        \begin{equation}
          \begin{aligned}
            \E(Y_N) &= \sum_{i=1}^{n}\frac{\sum_{j=0}^{n} \abs{i-j}}{n+1} \\
                    &= \frac{1}{n+1}\sum_{i=1}^{n} i(i+1) - \frac{i(i+1)}{2} + \frac{(i+1+n)(n-i)}{2} - i(n-i) \\
                    &= \frac{1}{n+1}\sum{i=1}^{n} i^2 - ni + \frac{n(n+1)}{2} \\
                    &= \frac{1}{n+1}\pa{\frac{n(n+1)(2n+1)}{6}} - \frac{n^2(n+1)}{2} + \frac{n^2(n+1)}{2} \\
                    &= \frac{n(2n+1)}{6}
          \end{aligned}
        \end{equation}

        Thus we have 
        \begin{equation}
          \begin{aligned}
            I_n &= X_n + Y_n \\
                &= \frac{7n-1}{12}
          \end{aligned}
        \end{equation}
    \end{enumerate}
  \end{homeworkProblem}

  \begin{homeworkProblem}[Special Problem 4] %{{{2
    Use the above Chernoff Bounds to prove the following inequalities: For all
    $0 < \delta \le 1$

    \begin{enumerate}[(a)]
      \item $\Pr\{X \ge (1 + \delta) \mu\} \le e^{-\mu\delta^2/3}$
      \item $\Pr\{X \ge (1 - \delta) \mu\} \le e^{-\mu\delta^2/2}$
    \end{enumerate}

    \Remark Note that it follows from (a) and (b) that $\Pr\{\lvert X-\E(X)
    \rvert > a\} \le 2e^{a^2/3\E(x)}$ for all $0 < a \le \E(X)$.
    
    \Answer
    We need the Chernoff Bounds.
    \begin{align}
      \Pr\{X \ge (1+\delta)\mu\} \le &
      \pa{\frac{e^\delta}{(1+\delta)^{1+\delta}} }^\mu \label{eq:sp4_1} \\
      \Pr\{X \ge (1-\delta)\mu\} \le &
      \pa{\frac{e^\delta}{(1-\delta)^{1-\delta}} }^\mu \label{eq:sp4_2}
    \end{align}

    \begin{enumerate}[(a)]
        % {{{ (a)
      \item
        \begin{proof}
          From \fref{eq:sp4_1}, we need to proof:
          \begin{equation}
            \begin{aligned}
              &\quad \pa{\frac{e^\delta}{(1+\delta)^{1+\delta}} }^\mu
              - \mu e^{-\mu\delta^2/3} \le 0 \nonumber \\
              \Rightarrow & \quad \ln \frac{e^\delta}{(1+\delta)^{1+\delta}} -
              \frac{\delta^2}{3} \le 0
            \end{aligned}
          \end{equation}

          For $\delta=0$, the left side is equal to zero.  Thus we need to proof
          the derivative of the left size is always less than zero.

          Simplify the derivative of left size, thus we need to proof:
          \begin{equation}
            \log(\delta+1) \ge \frac{2\delta}{3}
            \label{eq:sp4_a1}
          \end{equation}

          And we know that $\log(x+1)$ is a concave function. So we have
          \begin{equation}
            \begin{aligned}
              \log(x+1) &\ge (1-x)\ln1 + x\ln2 \\
                        &=  x(\ln2 - \ln1) \\
                        &\ge  0.69x \\
                        &\ge \frac{2x}{3}
            \end{aligned}
          \end{equation}

          Thus we proof the \fref{eq:sp4_a1}.
        \end{proof}
        % }}}
        % {{{ (b)
      \item 
        \begin{proof}
          From \fref{eq:sp4_2}, we need to proof:
          \begin{equation}
            \begin{aligned}
              & \quad \pa{\frac{e^\delta}{(1+\delta)^{1+\delta}} }^\mu
              - \mu e^{-\mu\delta^2/3} \le 0 \nonumber \\
              \Rightarrow & \quad \ln \frac{e^\delta}{(1+\delta)^{1+\delta}} -
              \frac{\delta^2}{3} \le 0 \label{eq:sp4_b1}
            \end{aligned}
          \end{equation}

          For $\delta=0$, the left side is equal to $0$.  Thus we need to proof
          the derivative of the left size is always less than zero.

          Simplify the derivative of left side of \fref{eq:sp4_b1}, thus we
          need to proof:
          \begin{equation}
            \delta + \ln(1-\delta) \le 0
          \end{equation}
          which is a very famous inquality if we define $x=-\delta$.
        \end{proof}
        %}}}
    \end{enumerate}

  \end{homeworkProblem}
  % }}}2

  \Acknowledgement{
    Thank Pufan He 2011011377 and Qiwei Feng 2011011250 for the discussion.
  }

\end{spacing}
\end{document}
