Logarithmic approximation of ∑ 0 N − 1 1 2 i + 1 Can anyone confirm that it's possible to approximate the sum ∑ 0 N − 1 1 2 i + 1 with the log ⁡ N 2 ? And why?It's clearly visible that the sum has a logarithmic growth over i but it's unclear to me how to prove it.

Question

Logarithmic approximation of       ∑    0          N      −      1            1          2      i      +      1      Can anyone confirm that it&#039;s possible to approximate the sum       ∑    0          N      −      1            1          2      i      +      1       with the             log      ⁡              N              2  ? And why?It&#039;s clearly visible that the sum has a logarithmic growth over i  but it&#039;s unclear to me how to prove it.

kuncwadi17 · Accepted Answer

∑                      i            =            0                                N            −            1                                                1                          2              i              +              1                                                          =                              1            2                                    ∑                      i            =            0                                N            −            1                                                1                          i              +              1                              /                            2                                      =                              1            2                                    [          Ψ                      (                                          1                2                                      +            N            )                    −          Ψ                      (                                          1                2                                      )                    ]                =                              1            2                          Ψ                  (          N          +                                    1              2                                )                +                              1            2                                  γ        +        ln        ⁡                  (          2          )                    where   Ψ      (    z    )   is the       digamma function   and   γ  =  0.577215664901533  … is the       Euler-Mascheroni constant  .             Ψ              (                  1          2                )            =      −      γ      −      2      ln      ⁡              (        2        )            Also,             Ψ              (        z        )            ≈      ln      ⁡              (        z        )            −                        1                      2            z                                             when                           |                z                |            ≫      1                                    ∑                      i            =            0                                N            −            1                                                1                          2              i              +              1                                                          ≈                              1            2                                    [          ln          ⁡                      (            N            +                                          1                2                                      )                    −                                    1                              2                                  (                  N                  +                  1                                      /                                    2                  )                                                              ]                +                              1            2                                  γ        +        ln        ⁡                  (          2          )                        ,                N        ≫        1                                ∑                  i          =          0                          N          −          1                                      1                      2            i            +            1                              ≈                        1          2                    ln      ⁡              (        N        +                              1            2                          )            −                        1                      2                          (              2              N              +              1              )                                          +                        1          2                          γ      +      ln      ⁡              (        2        )                  ,            N      ≫      1

polivijuye · Accepted Answer

This is a Riemann sum for the integral from 0 to   N of   1      /    (  2  x  +  1  ), so it approximates   (  1      /    2  )  ln  ⁡  (  2  N  +  1  ), which is approximately   (  1      /    2  )  ln  ⁡  N