From ∑ ⌊ log ⁡ n ⌋ + 1 ∞ n / 2 r to ∑ r = 0 ∞ 1 / 2 r E [ h ] = E [ ∑ r = 1 ∞ I r ] = ∑ r = 1 ∞ E [ I r ] = ∑ r = 1 ⌊ log ⁡ n ⌋ E [ I r ] + ∑ ⌊ log ⁡ n ⌋ + 1 ∞ E [ I r ] ≤ ∑ r = 1 ⌊ log ⁡ n ⌋ 1 + ∑ ⌊ log ⁡ n ⌋ + 1 ∞ n / 2 r ≤ log ⁡ n + ∑ r = 0 ∞ 1 / 2 r = log ⁡ n + 2I'm trying to understand how you go from ∑ ⌊ log ⁡ n ⌋ + 1 ∞ n / 2 r to ∑ r = 0 ∞ 1 / 2 r

Question

From       ∑          ⌊      log      ⁡      n      ⌋      +      1        ∞    n      /              2      r       to       ∑          r      =      0        ∞    1      /        2    r    E  [  h  ]  =  E  [      ∑          r      =      1        ∞        I    r    ]  =      ∑          r      =      1        ∞    E  [      I    r    ]  =      ∑          r      =      1              ⌊      log      ⁡      n      ⌋        E  [      I    r    ]  +      ∑          ⌊      log      ⁡      n      ⌋      +      1        ∞    E  [      I    r    ]  ≤      ∑          r      =      1              ⌊      log      ⁡      n      ⌋        1  +      ∑          ⌊      log      ⁡      n      ⌋      +      1        ∞    n      /              2      r        ≤  log  ⁡  n  +      ∑          r      =      0        ∞    1      /        2    r    =  log  ⁡  n  +  2I&#039;m trying to understand how you go from       ∑          ⌊      log      ⁡      n      ⌋      +      1        ∞    n      /              2      r       to       ∑          r      =      0        ∞    1      /        2    r

alisonhleel3 · Accepted Answer

Assuming   log here means the base-   2 (since the inequality doesn&#039;t generally hold if the base is larger), we have  n  &amp;lt;      2          ⌊      log      ⁡      n      ⌋      +      1        ,and therefore      ∑          r      =      ⌊      log      ⁡      n      ⌋      +      1        ∞        n          2      r        &amp;lt;      ∑          r      =      ⌊      log      ⁡      n      ⌋      +      1        ∞              2              ⌊        log        ⁡        n        ⌋        +        1                    2      r        =      ∑          r      =      ⌊      log      ⁡      n      ⌋      +      1        ∞        1          2              r        −        (        ⌊        log        ⁡        n        ⌋        +        1        )              =      ∑          k      =      0        ∞        1          2      k        .

From <munderover> ∑ <mrow class="MJX-TeXAtom-ORD"> <mo fence="fals

Answered question

Answer & Explanation

New Questions in Algebra II