0

Im trying to simplify the sum

$$ S_n = \sum_{1 \leq j < k + j \leq n} \frac{1}{k} $$

Attempt:

I can write

$$ (1 \leq j < k + j \leq n ) = (1 \leq j \leq n) \cap(j < k + j \leq n)= (1 \leq j\leq n) \cap (0 < k < n-j)$$

Thus,

$$ S_n = \sum_{j=1}^n \sum_{k=0}^{n-j} \frac{1}{k} = \sum_{k=0}^{n-j} \frac{1}{k} \sum_{j=1}^n1 = \sum_{k=0}^{n-j} \frac{n}{k} $$

And here I dont know how to continue. Is this correct so far?

Added:

My teacher said that

$$ (1 \leq j < k +j \leq n) = (1 \leq j)\cap (1 \leq n) \cap (j \leq n - k) \cap ( j < k +j \leq n ) = $$

$$ = (1 \leq j \leq n - k) \cap (0 < k \leq n -j ) = (1 \leq j \leq n -k) \cap {\color{red}{ ( 1 \leq k \leq n-1 ) }} $$

But, This seems false, how come the part is red follows?

Community
  • 1
ILoveMath
  • 10,694

1 Answers1

1

No, slight mistakes. You should have ($\leq$ at the end)

$$ (1 \leq j < k + j \leq n ) = (1 \leq j\leq n) \cap (0 < k \leq n-j) $$

and then the limits cannot be simply interchanged since $k$ depends on $j$. Instead, the conditions for $j$ and $k$ select an "area" in the $j$-$k$-plane and any way to count that area is fine. Since you want $k$ first, the area can be counted by $(1 \leq k\leq n-1) \cap (0 < j \leq n-k)$.

So $$ S_n = \sum_{k=1}^{n-1} \frac{1}{k} \sum_{j=1}^{n-k} 1 = \sum_{k=1}^{n-1} \frac{n-k}{k} = 1-n + n \cdot \sum_{k=1}^{n-1} \frac{1}{k} = 1 + n \cdot \sum_{k=2}^{n-1} \frac{1}{k} $$

Andreas
  • 15,175
  • why $k$ runs from $1$ to $n-1$. I thought it was $0 < k < n -k$. – ILoveMath Mar 19 '17 at 10:58
  • $0 < k < n -k$ ? I guess you mean $0 < k \leq n -j$. But, as I explained, this won't help, since you need k first, independent of j. Please draw on an j-k-plane the required index area, and then start counting over k (with j dependent on k). That should make it clear. – Andreas Mar 19 '17 at 11:04
  • I dont understand how $k$ depends on $j$. Im confused sir – ILoveMath Mar 19 '17 at 11:18
  • Did you draw it? – Andreas Mar 19 '17 at 11:41
  • Yes, I get the area is bounded by the lines $k=0$, $j+k=n$ and $j=1$ which is triangle in the $kj$ plane. Thus, $k$ goes from 1 to $n-1$ and $j$ from 1 to $n$. Is this correct? – ILoveMath Mar 19 '17 at 11:45
  • Almost: "bounded by the lines k=1, j+k=n and j=1 ". So, now start counting this triangle. Correctly, " k goes from 1 to n−1" but then, for every k, j goes from 1to n-k. – Andreas Mar 19 '17 at 11:54