Proving that the sum of fractions has an odd numerator and even denominator.I'm struggling to show that, for all n &gt; 1 1 + 1 2 + 1 3 + ⋯ + 1 n = k m where k is an odd number and m is an even number.Proof: The proof is by induction on nBase Case: 1 + 1 2 = 3 2 Assume the theorem is true for n and consider n + 1 1 + 1 2 + 1 3 + ⋯ + 1 n + 1 n + 1 We know by the induction hypothesis that the first n terms take the form k m , where k is odd and m is even. k m + 1 n + 1 To combine the terms, we find the least common multiple of m and n + 1. Since m is even, the least common multiple must be even.Now What? I'm not sure how to show that the numerator remains odd. I don't think there's enough information to do just a case analysis on whether n + 1 is odd or even.This question is from Manber's Introduction to Algorithms: A Creative Approach, which I'm using for personal development. He marked this question as "substantially more difficult."

Question

Proving that the sum of fractions has an odd numerator and even denominator.I&#039;m struggling to show that, for all   n  &amp;gt;  1  1  +      1    2    +      1    3    +  ⋯  +      1    n    =      k    m  where   k is an odd number and   m is an even number.Proof: The proof is by induction on   nBase Case:   1  +      1    2    =      3    2  Assume the theorem is true for   n and consider   n  +  1  1  +      1    2    +      1    3    +  ⋯  +      1    n    +      1          n      +      1      We know by the induction hypothesis that the first   n terms take the form       k    m  , where   k is odd and   m is even.      k    m    +      1          n      +      1      To combine the terms, we find the least common multiple of   m and   n  +  1. Since   m is even, the least common multiple must be even.Now What? I&#039;m not sure how to show that the numerator remains odd. I don&#039;t think there&#039;s enough information to do just a case analysis on whether   n  +  1 is odd or even.This question is from Manber&#039;s Introduction to Algorithms: A Creative Approach, which I&#039;m using for personal development. He marked this question as &quot;substantially more difficult.&quot;

jugf5 · Accepted Answer

We actually need to prove by strong induction.Suppose the result holds for all   2  ,  3  ,  4  ,  .  .  .  ,  n  −  1. Now let&#039;s look at the case of   nWe first look at the following sequences:            a      c        =  1  +            1      3        +  .  .  .  +            1      p       where   p is the largest odd number not exceeding   n.            b      d        =            1      2        +  .  .  .  +            1      q       where   q is the largest even number not exceeding   nFirst we can conclude   b is odd and   d is even as            b      d        =            1      2        +  .  .  .  +            1      q        =            1      2        (  1  +            1      2        +            1      3        .  .  .  +            1              (                              q            2                          )              )By induction hypothesis we know for   q  &amp;gt;  2,   (  1  +            1      2        +            1      3        .  .  .  +            1              (                              q            2                          )              ) has odd numerator and even denominator and hence   d is even and   b is odd.For the case where   q  =  2,   b  =  1 and   d  =  2 so still   d is even and   b is odd.Then let&#039;s look at   c, we know   c must be odd because   1  ,  3  ,  5  ,  .  .  .  ,  p are all odd.Now   1  +      1    2    +      1    3    +  ⋯  +      1    n    =            a      c        +            b      d        =                    a        d        +        b        c                    c        d            . The numerator is odd and the denominator is even and we are good.

Bruno Pittman · Accepted Answer

To complete your proof, first observe that      k    m    +      1          n      +      1        =            k      (      n      +      1      )      +      m              m      (      n      +      1      )      now   m is even so let   m  =      2    α    a,where   α is the biggest power of   2 in   m, so   a is odd.if   n  +  1 is odd obviously   k  (  n  +  1  )  +  m is odd and       m    (    n    +    1    )   is even, so we are done.So consider the case when   n  +  1 is even. Then   n  +  1  =      2    β    b, where   β is the biggest power of 2 in   n  +  1, so b is odd. so             k      (      n      +      1      )      +      m              m      (      n      +      1      )        =            k      (              2        β            b      )      +              2        α            a              (              2        β            b      )      (              2        α            a      )        =            k      (              2        β            b      )      +              2        α            a                      2                  α          +          β                    a      b      now look at whether   α or   β is smaller. Say   α is smaller, then            k      (              2        β            b      )      +              2        α            a                      2                  α          +          β                    a      b        =            k      (              2                  β          −          α                    b      )      +      a                      2                  β                    a      b      now we have an even denominator, and on the numerator   k  (      2          β      −      α        b  ) is even and   a is odd, so the numerator is odd.Now if   β is smaller, then            k      (              2        β            b      )      +              2        α            a                      2                  α          +          β                    a      b        =            k      b      +              2                  α          −          β                    a                      2                  α                    a      b      now   k  b is odd so the numerator is odd, and our denominator is obviously even.By induction, you have proved statement as required

Proving that the sum of fractions has an odd numerator and even denominator. I'm struggling to show

Answered question

Answer & Explanation

New Questions in Pre-Algebra