# Question About Proof

1. Jul 15, 2009

### JG89

1. The problem statement, all variables and given/known data

I was reading a question in a textbook that said, "Prove that $$\sum_{v=1}^{\infty} \frac{a_v^n}{v} = ln(n)$$ where $$a_v^n = 1$$ if n is not a factor of v, and $$a_v^n = -(n-1)$$ if n is a factor of v.

2. Relevant equations

3. The attempt at a solution

The author started his proof as follows:

Take the sum from v = 1 to v = mn:

$$\sum_{v=1}^{v=mn} \frac{a_v^n}{v} = \sum_{v \ne mn} \frac{1}{v} - \sum_{v=kn} \frac{n-1}{v}$$.

Didn't the author just rearrange the terms, even though the series cannot be absolutely convergent (this is easy to prove), and so he could have just changed the sum of the series?

Last edited: Jul 15, 2009
2. Jul 15, 2009

### Staff: Mentor

This series
$$\sum_{v=1}^{v=mn} \frac{a_v^n}{v} = \sum_{v \ne mn} \frac{1}{v} - \sum_{v=kn} \frac{n-1}{v}$$
is a finite series, so there is no question about convergence, hence no problem rearranging it in any way.

3. Jul 15, 2009

### JG89

That's what I was thinking, but say we then let m tend to infinity, the rearrangement won't change anything?

For example, consider the following two series:

1 - 1/2 + 1/3 + ... + (-1)^(n+1)/n

-1/2 + 1 - 1/3 + ... + 1/5 <--- where this series is the same as the above series, except for the rearrangement.

If we let n tend to infinity now, these two sums are going to be the same?

4. Jul 15, 2009

### Office_Shredder

Staff Emeritus
If you can find a way to re-arrange a subsequence of the partial sums and then take the limit, it won't change the value. The problem occurs when terms are moved 'arbitrarily far', so for example if I re-arrange the sequence 1-1/2+1/3-1/4+... such that it's now of the pattern

1+1/3-1/2+1/5+1/7-1/4 that is 2 positive terms then one negative term etc. then the negative terms have been shifted away from their original position without bound, and it's no longer possible to simply re-arrange the ordering in the partial sums to get this pattern. On the other hand if I just flipped each pair of positive and negative terms

-1/2+1-1/4+1/3-1/6+1/5... then the sum will stay the same, since I've simply re-arranged every other partial sum

In the case in the original post. the author has re-arranged the subsequence of every vmth partial sum, so the limit will remain the same

I'm not sure about your example above since 1) your 1/3 term changed sign (which is probably a typo but isn't clear) and 2) There's a 1/5 at the end? You can't have a last term for an infinite series

You can prove the stuff I posted above by noting that if two sequences an and bk converge, and there is an ordered subsequence of the naturals ij such that aij = bij that converge to the same value (this would correspond to a subsequence of the partial sum of the re-arranged series simply corresponding to re-arranged partial sums) then the original sequences must converge to the same value

Last edited: Jul 15, 2009
5. Jul 15, 2009

### JG89

Thanks for the detailed reply Office_Shredder!

I haven't got time now (I have to head out), but I shall thoroughly read your post when I get back home. This looks like it's exactly what I was looking for.

Last edited: Jul 15, 2009
6. Jul 15, 2009

### JG89

I THINK I understand what you are saying about the subsequences of partial sums. It's not too clear, but let's work through my next question, and hopefully that will clear some things up.

Suppose n = 3. Then

$$\sum_{v=1}^{v=3m} \frac{a_v^3}{v} = 1 + 1/2 - 2/3 + 1/4 + 1/5 -2/6 + ... + -2/mn$$.

According to the author, this is equal to

$$\sum_{v \nq mn} \frac{1}{v} - \sum_{v=mn} \frac{n-1}{v} = 1 + 1/2 + 1/4 + 1/5 + 1/7 + ... + 1/(mn-1) - (2/3 + 2/6 + 2/9 + 2/12 + ... + 2/mn)$$.

It seems as if the terms (2/3 + 2/6 + 2/9 + 2/12 + ... + 2/mn) have been moved arbitrarily far from (1 + 1/2 + 1/4 + 1/5 + 1/7 + ... + 1/(mn-1)) since if I let m tend to infinity, we will never 'reach' the terms (2/3 + 2/6 + 2/9 + 2/12 + ... + 2/mn).

Could you please elaborate on this example, and also elaborate on what you mean by 'finding a way to re-arrange a sub-sequence of the partial sums' ?

7. Jul 15, 2009

### JG89

Okay. You said the author re-arranged the subsequence of every vm'th partial sum.

Say we take m = 1 and n = 3.

Then $$\sum_{v=1}^3 \frac{a_v^3}{v} = 1 + 1/2 - 2/3$$.

With our rearranged series: $$\sum_{v \nq n} \frac{1}{v} - \sum{v=kn} \frac{n-1}{v} = 1 + 1/2 - 2/3$$

So the 3rd partial sum of both series contain the same terms, and so they are equal.

If we take m = 2, again with n = 3, then

$$\sum_{v=1}^6 \frac{a_v^3}{v} = 1 + 1/2 - 2/3 + 1/4 + 1/5 - 2/6$$

and

$$\sum_{v \nq n} \frac{1}{v} - \sum{v=kn} \frac{n-1}{v} = 1 + 1/2 + 1/4 + 1/5 - 2/3 - 2/6$$.

Again both arrangements of the 6'th partial sum is equal, and so the partial sums are equal.

Is this line of thinking correct?

8. Jul 15, 2009

### Office_Shredder

Staff Emeritus
You're not quite right, but for now, let's stick with the more technical details.

Given a series $$\Sum_{i=0}^{ \infty} a_i$$ this series has a sequence of partial sums we'll call $$(S_n)$$ If we re-arrange the $$a_i$$'s, this will give us a new sequence of partial sums which we will call $$(X_m)$$. Now, assume $$\lim_{ n \rightarrow \infty } S_n$$ and $$\lim_{m \rightarrow \infty } X_m$$ both exist. ALSO, there exist subsequences $$(S_{n_k})$$ and $$(X_{m_k})$$ (note that the kth index in each sequence are not equal, but can be) such that $$S_{n_k}=X_{m_k}$$ for each k.

THEN each of these subsequences must converge to what the sequences $$(S_n)$$ and $$(X_m)$$ converge to respectively, and since the subsequences converge to the same value (since they have equal kth terms), it must be the original sequences converged to the same value. Hence the re-arrangement didn't change anything. This can be used to show that re-arranging the series like the author does won't drastically change anything.

As to what the other stuff in my post was talking about: Even though it looks like the 1/(mn-1) term is stuck really far away from where it was, if you look at the sequence of re-arranged partial sums, the term 1/(mn-1) doesn't actually get added on until the mth sequence (since you need to have v=mn in the original sequence) so the situation fits what I described in the beginning of my other post. If you still don't see this, don't worry about it and stick with the technical stuff; I was just describing a way of heuristically spotting when re-arrangements are good and when they're bad

9. Jul 15, 2009

### JG89

Understood. Let's use the alternating harmonic series as an example again. Let S_n be the sequence of partial sums.

Then S_1 = 1, S_2 = 1 - 1/2, S_3 = 1 - 1/2 + 1/3, ...

Let us now re-arrange the series in the following manner (it's the same derangement that you posted):

-1/2 + 1 -1/4 + 1/3 - 1/6 + 1/5 + ...

Let X_m be the sequence of partial sums of the re-arranged series. Then X_1 = -1/2, X_2 = -1/2 + 1, X_3 = -1/2 + 1 - 1/4, X_4 = -1/2 + 1 - 1/4 + 1/3, ...

Now consider this subsequence of the S_n: S_2, S_4, S_6, ..., And the subsequence X_2, X_4, X_6, ... of the X_m...We'll call these two subsequences S'_n, and X'_m respectively

It is clear that S_2 = X_2, S_4 = X_4, and so on. Thus $$\sum_{v=1}^{\infty} \frac{(-1)^{v+1}}{v} = \lim_{n \rightarrow \infty} S'_n = \lim_{m \rightarrow \infty} X'_m$$.

This is correct, right?

EDIT: Going back to the original question, the vm'th partial sum of the original series is equal to the vm'th partial sum of the rearranged series (as you noted), and so the sum of the infinite series will not change.

Quick question though, when the author re-arranged the series, he was assuming that the original series converges (remember that we have to assume the original series converges as well as its re-arrangement). Shouldn't he prove first that the original series converges, then go on to prove that his re-arranged series converges, find the sum of the re-arranged series, and then from what we've just discussed this will equal the sum of the original series? Or does the convergence of the original series follow from the convergence of the re-arranged series?

Last edited: Jul 15, 2009
10. Jul 15, 2009

### Office_Shredder

Staff Emeritus
Your example is correct. I'd have to see the full proof to say exactly what the author did, but often the way you prove a series converges to a value is by assuming it converges, then finding out what the value is, and then proving that the series converges. Example for sequences:

$$a_0 = \sqrt{2}$$
$$a_{n+1} = \sqrt{2*a_n}$$

Then if the sequence converges to a say, taking the limit in the second condition gives us that

$$a = \sqrt{2a}$$ so $$a^2 = 2a$$ and hence a=0 or a=2. Then you go as follows:
1) Show the sequence is increasing
2) Show the sequence is bounded above by 2

So the sequence converges to either 0 or 2. It can't converge to 0 since it's positive and increasing, hence the sequence converges to 2. Doing the second step would be far more difficult (finding an upper bound) without having 'checked' what the sequence converges to first (which tells me what a definite upper bound is)