I've been studying algorithm analysis and the book i'm reading, Introduction to Algorithms, has given me a problem that i can't seem to solve. the problem is stated as follows.
"Show that $\sum_{k = 1}^n \frac{1}{2k-1} = \ln({ \sqrt{ n }}) + O(1)$ by manipulating the harmonic series."
where O(1) is a constant number (the solution below seems to throw away constants, since asymptotic analysis only cares about the highest terms).
i have found the apparent solution here: https://atekihcan.github.io/CLRS/EA.01-02/
buti can't seem to figure out line 3 where: $$\sum_{k = 1}^n \frac{1}{2k-1} = \sum_{k=1}^{2n} (\frac{1}{k}) - \frac{1}{2}\sum_{k=1}^n (\frac{1}{k})$$
from what I understood of the authors explanation, he or she is adding, then subtracting $\frac{1}{2} \sum_{k=1}^n$ to get the solution, but when I try to replicate the step the closest i get is this: $$\sum_{k = 1}^n \frac{1}{2k-1}+\frac{1}{2} \sum_{k=1}^n-\frac{1}{2} \sum_{k=1}^n \implies \sum_{k=1}^n \frac{2k+(2k+1)}{2k(k+1)}-\frac{1}{2} \sum_{k=1}\frac{1}{k}$$ I'm wondering if anyone can help me see what i'm doing wrong, and if they know any resources to help me solving similar types of problems in the future (apparently i can't google hard enough). thanks.
We see that the first sum adds the multiplicative inverses of integers from $1$ to $2n$: $$\sum_{k=1}^{2n} \frac{1}{k}=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{2n}$$ and that the second sum adds the multiplicative inverses of integers from $1$ to $n$, and then multiplies them by $\frac{1}{2}$: $$\frac{1}{2}\sum_{k=1}^{n} \frac{1}{k}=\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+\ldots+\frac{1}{2n}$$ Note that these sums are different.
After substracting the first from the second, only the fractions with odd denominators survive: $$\sum_{k=1}^{2n} \frac{1}{k}-\frac{1}{2}\sum_{k=1}^{n} \frac{1}{k}=\frac{1}{1}+\frac{1}{3}+\frac{1}{5}+\ldots+\frac{1}{2n-1}$$ which can be written as $$\frac{1}{1}+\frac{1}{3}+\frac{1}{5}+\ldots+\frac{1}{2n-1}=\sum_{k=1}^{n}\frac{1}{2k-1}$$