3
$\begingroup$

Got confused by the statement as the author does not provide any details regarding this property. So in the book "Concrete Mathematics" the authors state:

An index variable that doesn’t appear in the summand (here j) can simply be eliminated if we multiply what’s left by the size of that variable’s index set (here $n-k$).

Then the authors use this property in evaluating the particular sum:

$ \begin{equation} S_n = \displaystyle\sum\limits_{1 \le j < k \le n}^{}{\frac{1}{k-j}} \end{equation} $ = $ \begin{equation} S_n = \displaystyle\sum\limits_{1 \le j < k+j \le n}^{}{\frac{1}{k}} \end{equation} $ - replacing $k$ by $k+j$

$ \begin{equation} S_n = \displaystyle\sum\limits_{1 \le k \le n}^{} \displaystyle\sum\limits_{1 \le j \le n-k}^{}{\frac{1}{k}} \end{equation} $ -summing first on j

$ \begin{equation} S_n = \displaystyle\sum\limits_{1 \le k \le n}^{}{\frac{n-k}{k}} \end{equation} $ - the sum on $j$ is trivial

I have underscored what makes me so confused. According to the authors' note, this is valid, however I seek for the clear explanation or proof that allow to eliminate the index variable by simply multiplying the summand by the upper bound. Could anyone shed more light on that?

$\endgroup$
4
  • $\begingroup$ 2nd line, inner sum: "summing first on $j$". Because the "term" is $\dfrac 1 k$ and does not depend on $j$, summing it on $j$ means to sum $n-k$ times the term $\dfrac 1 k$. Thus: $\Sigma_{1 \le j \le n-k} \dfrac 1 k = (n-k) \dfrac 1 k$. $\endgroup$ – Mauro ALLEGRANZA Jun 19 '20 at 10:38
  • $\begingroup$ Yes, I understood that, but I can't see why it's true and valid. $\endgroup$ – SAT Jun 19 '20 at 10:39
  • $\begingroup$ Yes, everything that I have out there is clear, however I don't understand why the third line is true and works for every summation if the index variable is not present in the summand $\endgroup$ – SAT Jun 19 '20 at 10:44
  • $\begingroup$ I see, but I still can't prove to myself that summing on j when the "term" is not present means multiplying by $n-k$ $\endgroup$ – SAT Jun 19 '20 at 11:14
3
$\begingroup$

In the last line the following general rule is used:

$$\sum_{j=1}^m c_k = \underbrace{c_k+\cdots + c_k}_{m \times c_k} = mc_k$$

Nevertheless, there is a mistake in the index $k$. When replacing summation indices it is better not to use the same index as it happened in your book:

So, let $d:= k-j$. Then,

$$1\leq d \leq \color{blue}{n-1} \text{ and } 1 \leq j \leq n-d$$

It follows

$$S_n = \displaystyle\sum\limits_{1 \le j < k \le n}^{}{\frac{1}{k-j}} = \sum_{d=1}^{n-1}\sum_{j=1}^{n-d}\frac 1d = \sum_{d=1}^{n-1}\frac{n-d}{d}$$

$\endgroup$
2
  • $\begingroup$ Thank you! Could you refer me where I can find this "general rule"? $\endgroup$ – SAT Jun 19 '20 at 11:23
  • 1
    $\begingroup$ @SAT This is actually a direct consequence of the definition of the sum symbol. If you have $m$ equal summands, then the sum is equal to the $m$-fold of the summand. $\endgroup$ – trancelocation Jun 19 '20 at 11:31
2
$\begingroup$

Let $f(\cdot)$ be a function that does not depend on $i.$

We prove that $$\sum_{1\le i \le n} f(\cdot) = nf(\cdot)$$ by induction on $n$.

If $n = 1$, then $$\sum_{1\le i \le 1} f(\cdot) = f(\cdot).$$

Suppose that $$\sum_{1\le i \le n-1} f(\cdot) = (n-1)f(\cdot),$$ then $$\sum_{1\le i \le n} f(\cdot) = \Big(\sum_{1\le i \le n-1} f(\cdot)\Big) + f(\cdot) = (n-1)f(\cdot) + f(\cdot)=nf(\cdot).$$

$\endgroup$
1
  • $\begingroup$ Thank you for your answer, it's much more clear now! $\endgroup$ – SAT Jun 19 '20 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.