Proving that the sum of fractions has an odd numerator and even denominator.I'm struggling to...
Proving that the sum of fractions has an odd numerator and even denominator.
I'm struggling to show that, for all
where is an odd number and is an even number.
Proof: The proof is by induction on
Assume the theorem is true for and consider
We know by the induction hypothesis that the first terms take the form , where is odd and is even.
To combine the terms, we find the least common multiple of and . Since 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 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
We actually need to prove by strong induction.
Suppose the result holds for all . Now let's look at the case of
We first look at the following sequences:
where is the largest odd number not exceeding .
where is the largest even number not exceeding
First we can conclude is odd and is even as
By induction hypothesis we know for , has odd numerator and even denominator and hence is even and is odd.
For the case where , and so still is even and is odd.
Then let's look at , we know must be odd because are all odd.
Now . The numerator is odd and the denominator is even and we are good.
To complete your proof, first observe that
now is even so let ,where is the biggest power of in , so is odd.
if is odd obviously is odd and is even, so we are done.
So consider the case when is even. Then , where is the biggest power of 2 in , so b is odd. so
now look at whether or is smaller. Say is smaller, then
now we have an even denominator, and on the numerator is even and is odd, so the numerator is odd.
Now if is smaller, then
now is odd so the numerator is odd, and our denominator is obviously even.
By induction, you have proved statement as required