# Confusion with elimination of index variable if it does not appear in the summand - Concrete Mathematics, D.Knuth

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?

• 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$. – Mauro ALLEGRANZA Jun 19 '20 at 10:38
• Yes, I understood that, but I can't see why it's true and valid. – SAT Jun 19 '20 at 10:39
• 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 – SAT Jun 19 '20 at 10:44
• 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$ – SAT Jun 19 '20 at 11:14

## 2 Answers

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}$$

• Thank you! Could you refer me where I can find this "general rule"? – SAT Jun 19 '20 at 11:23
• @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. – trancelocation Jun 19 '20 at 11:31

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).$$

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