ScommaMaruj

Answered

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+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}=\frac{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+\frac{1}{2}=\frac{3}{2}$

Assume the theorem is true for $n$ and consider $n+1$

$1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}+\frac{1}{n+1}$

We know by the induction hypothesis that the first $n$ terms take the form $\frac{k}{m}$, where $k$ is odd and $m$ is even.

$\frac{k}{m}+\frac{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."

I'm struggling to show that, for all $n>1$

$1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}=\frac{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+\frac{1}{2}=\frac{3}{2}$

Assume the theorem is true for $n$ and consider $n+1$

$1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}+\frac{1}{n+1}$

We know by the induction hypothesis that the first $n$ terms take the form $\frac{k}{m}$, where $k$ is odd and $m$ is even.

$\frac{k}{m}+\frac{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

Expert

2022-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:

$\frac{a}{c}=1+\frac{1}{3}+...+\frac{1}{p}$ where $p$ is the largest odd number not exceeding $n$.

$\frac{b}{d}=\frac{1}{2}+...+\frac{1}{q}$ where $q$ is the largest even number not exceeding $n$

First we can conclude $b$ is odd and $d$ is even as

$\frac{b}{d}=\frac{1}{2}+...+\frac{1}{q}=\frac{1}{2}(1+\frac{1}{2}+\frac{1}{3}...+\frac{1}{(\frac{q}{2})})$

By induction hypothesis we know for $q>2$, $(1+\frac{1}{2}+\frac{1}{3}...+\frac{1}{(\frac{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+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}=\frac{a}{c}+\frac{b}{d}=\frac{ad+bc}{cd}$. The numerator is odd and the denominator is even and we are good.

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:

$\frac{a}{c}=1+\frac{1}{3}+...+\frac{1}{p}$ where $p$ is the largest odd number not exceeding $n$.

$\frac{b}{d}=\frac{1}{2}+...+\frac{1}{q}$ where $q$ is the largest even number not exceeding $n$

First we can conclude $b$ is odd and $d$ is even as

$\frac{b}{d}=\frac{1}{2}+...+\frac{1}{q}=\frac{1}{2}(1+\frac{1}{2}+\frac{1}{3}...+\frac{1}{(\frac{q}{2})})$

By induction hypothesis we know for $q>2$, $(1+\frac{1}{2}+\frac{1}{3}...+\frac{1}{(\frac{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+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}=\frac{a}{c}+\frac{b}{d}=\frac{ad+bc}{cd}$. The numerator is odd and the denominator is even and we are good.

Bruno Pittman

Expert

2022-07-03Added 4 answers

To complete your proof, first observe that

$\frac{k}{m}+\frac{1}{n+1}=\frac{k(n+1)+m}{m(n+1)}$

now $m$ is even so let $m={2}^{\alpha}a$,where $\alpha $ 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}^{\beta}b$, where $\beta $ is the biggest power of 2 in $n+1$, so b is odd. so $\frac{k(n+1)+m}{m(n+1)}=\frac{k({2}^{\beta}b)+{2}^{\alpha}a}{({2}^{\beta}b)({2}^{\alpha}a)}=\frac{k({2}^{\beta}b)+{2}^{\alpha}a}{{2}^{\alpha +\beta}ab}$

now look at whether $\alpha $ or $\beta $ is smaller. Say $\alpha $ is smaller, then

$\frac{k({2}^{\beta}b)+{2}^{\alpha}a}{{2}^{\alpha +\beta}ab}=\frac{k({2}^{\beta -\alpha}b)+a}{{2}^{\beta}ab}$

now we have an even denominator, and on the numerator $k({2}^{\beta -\alpha}b)$ is even and $a$ is odd, so the numerator is odd.

Now if $\beta $ is smaller, then

$\frac{k({2}^{\beta}b)+{2}^{\alpha}a}{{2}^{\alpha +\beta}ab}=\frac{kb+{2}^{\alpha -\beta}a}{{2}^{\alpha}ab}$

now $kb$ is odd so the numerator is odd, and our denominator is obviously even.

By induction, you have proved statement as required

$\frac{k}{m}+\frac{1}{n+1}=\frac{k(n+1)+m}{m(n+1)}$

now $m$ is even so let $m={2}^{\alpha}a$,where $\alpha $ 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}^{\beta}b$, where $\beta $ is the biggest power of 2 in $n+1$, so b is odd. so $\frac{k(n+1)+m}{m(n+1)}=\frac{k({2}^{\beta}b)+{2}^{\alpha}a}{({2}^{\beta}b)({2}^{\alpha}a)}=\frac{k({2}^{\beta}b)+{2}^{\alpha}a}{{2}^{\alpha +\beta}ab}$

now look at whether $\alpha $ or $\beta $ is smaller. Say $\alpha $ is smaller, then

$\frac{k({2}^{\beta}b)+{2}^{\alpha}a}{{2}^{\alpha +\beta}ab}=\frac{k({2}^{\beta -\alpha}b)+a}{{2}^{\beta}ab}$

now we have an even denominator, and on the numerator $k({2}^{\beta -\alpha}b)$ is even and $a$ is odd, so the numerator is odd.

Now if $\beta $ is smaller, then

$\frac{k({2}^{\beta}b)+{2}^{\alpha}a}{{2}^{\alpha +\beta}ab}=\frac{kb+{2}^{\alpha -\beta}a}{{2}^{\alpha}ab}$

now $kb$ is odd so the numerator is odd, and our denominator is obviously even.

By induction, you have proved statement as required

Most Popular Questions