How to show that ∑ m = 1 n / 4 ( n m ) 2 − n ≤ exp ⁡ ( − n / 8 )

Question

How to show that       ∑          m      =      1              n              /            4                                    (                            n        m                              )                          2          −      n        ≤  exp  ⁡  (  −  n      /    8  )

Ordettyreomqu · Accepted Answer

For convenience, lets replace   n  →  4  n, so that it is equivalent to show             ∑              m        =        1            n                                (                                      4          n                m                              )                      ⩽          2              4        n                    e              −        n                  /                2            . We need a good bound for the partial sum in LHS, so consider                              (for                       m            &amp;lt;            n                    )                                                                (                                                          4              n                                      m              −              1                                                          )                                      =                              (            4            n            )            !                                m            !            (            4            n            −            m            )            !                          ⋅                  m                      4            n            −            m            +            1                          &amp;lt;                                            (                                                          4              n                        m                                              )                                      ⋅                  1          3                    As   1  +      1    3    +      1          3      2        +  ⋯  =      3    2  , we get the bound             ∑              m        =        1            n                                (                                      4          n                m                              )                      &amp;lt;          3      2                                (                                      4          n                n                              )                     for the partial sum. Now, using an easily found and rather well known upper bound for binomial coefficients, viz.                     (                    n      k                      )              &amp;lt;            n      k              k      !      , it is enough to show      3    2              (      4      n              )        n                    n      !        &amp;lt;      2          4      n        ⋅      e          −      n              /            2      which is straightforward by induction.

How to show that <munderover> <mo movablelimits="false">∑ <mrow class="M

Answered question

Answer & Explanation

New Questions in Calculus 1