I'm just starting with the concept of proving mathematical statements with induction.
The complete exercise with solution can be found under:
http://www2.isye.gatech.edu/~hsharp/math2420/harmonic.pdf
I'm struggeling with the translation from step 4 to step 5.
According to the notes its because we have 2^k elements (I got that part) which are >=1/2^(k+1) since its the smalles number.
However the part I don't understand is why we are using 1/2^(k+1) and not 1/2^k+1. shouldn't we calculate with the bigger number since we want to prove that H2^(k+1) is bigger than that?
Our tutor explained, that you are allowed to do the following:
H2^k+2>= 1 + k/2 + 1/2^k+1+...+1/2^(k+1) >= 1+(k+1)/2 and because of that you have to use the smaller term. However that education is not prooven as far as I get the concept, or am I wrong?
Any help is much appriciated!
Well, I actually was confused on the same thing, but after a while, I was able to understand. The proof is saying that $$= H2n + \frac{1}{2^k+1} +... \frac{1}{2^{k+1}} \ge \frac{1+k}{2} + \frac{1}{2^k+1}+...\frac{1}{2^{k+1}}$$ So the reason we multiply the $2^{nd}$ part by $\frac{1}{2^{k+1}}$ is that we are 100% sure that the inequality will be true, as $\frac{1}{2^{k+1}}$ is the lowest value in the sequence.
If we multiply by $\frac{1}{2^k+1}$, then the inequality may not hold true. In other words, if the $2^{nd}$ part of the inequality is lower, we are not changing the first part. If the $2^{nd}$ part is higher, then the $1^{st}$ part has to be higher than the $2^{nd}$ part, leading to uncertainty.
Hope this helps!