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

ScommaMaruj

ScommaMaruj

Answered question

2022-07-01

Proving that the sum of fractions has an odd numerator and even denominator.
I'm struggling to show that, for all n > 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 n
Base 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."

Answer & Explanation

jugf5

jugf5

Beginner2022-07-02Added 18 answers

We actually need to prove by strong induction.
Suppose the result holds for all 2 , 3 , 4 , . . . , n 1. Now let's look at the case of n
We 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 n
First 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 > 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'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

Bruno Pittman

Beginner2022-07-03Added 4 answers

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

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?