induction | College Math Teaching

February 5, 2016

More fun with selective sums of divergent series

Filed under: advanced mathematics, calculus, induction, infinite series, number theory, sequences — Tags: divergent series, harmonic series, select sum of a series — collegemathteaching @ 1:56 am

Just a reminder: if $\sum_{k=1}^{\infty} a_k$ is a series and $c_1, c_2, ...c_n ,,$ is some sequence consisting of 0’s and 1’s then a selective sum of the series is $\sum_{k=1}^{\infty} c_k a_k$ . The selective sum concept is discussed in the MAA book Real Infinite Series (MAA Textbooks) by Bonar and Khoury (2006) and I was introduced to the concept by Ferdinands’s article Selective Sums of an Infinite Series in the June 2015 edition of Mathematics Magazine (Vol. 88, 179-185).

There is much of interest there, especially if one considers convergent series or alternating series.

This post will be about divergent series of positive terms for which $lim_{n \rightarrow \infty} a_n = 0$ and $a_{n+1} < a_n$ for all $n$ .

The first fun result is this one: any selected $x > 0$ is a selective sum of such a series. The proof of this isn’t that bad. Since $lim_{n \rightarrow \infty} a_n = 0$ we can find a smallest $n$ such that $a_n \leq x$ . Clearly if $a_n = x$ we are done: our selective sum has $c_n = 1$ and the rest of the $c_k = 0$ .

If not, set $n_1 = n$ and note that because the series diverges, there is a largest $m_1$ so that $\sum_{k=n_1}^{m_1} a_k \leq x$ . Now if $\sum_{k=n_1}^{m_1} a_k = x$ we are done, else let $\epsilon_1 = x - \sum_{k=n_1}^{m_1} a_k$ and note $\epsilon_1 < a_{m_1+1}$ . Now because the $a_k$ tend to zero, there is some first $n_2$ so that $a_{n_2} \leq \epsilon_1$ . If this is equality then the required sum is $a_{n_2} + \sum_{k=n_1}^{m_1} a_k$ , else we can find the largest $m_2$ so that $\sum_{k=n_1}^{m_1} a_k + \sum_{k=n_2}^{m_2} a_k \leq x$

This procedure can be continued indefinitely. So if we label $\sum_{k=n_j}^{m_{j}} a_k = s_j$ we see that $s_1 + s_2 + ...s_{n} = t_{n}$ form an increasing, bounded sequence which converges to the least upper bound of its range, and it isn’t hard to see that the least upper bound is $x$ because $x-t_{n} =\epsilon_n < a_{m_n+1}$

So now that we can obtain any positive real number as the selective sum of such a series, what can we say about the set of all selective sums for which almost all of the $c_k = 0$ (that is, all but a finite number of the $c_k$ are zero).

Answer: the set of all such selective sums are dense in the real line, and this isn’t that hard to see, given our above construction. Let $(a,b)$ be any open interval in the real line and let $a < x < b$ . Then one can find some $N$ such that for all $n > N$ we have $x - a_n > a$ . Now consider our construction and choose $m$ large enough such that $x - t_m > x - a_n > a$ . Then the $t_m$ represents the finite selected sum that lies in the interval $(a,b)$ .

We can be even more specific if we now look at a specific series, such as the harmonic series $\sum_{k=1}^{\infty} \frac{1}{k}$ . We know that the set of finite selected sums forms a dense subset of the real line. But it turns out that the set of select sums is the rationals. I’ll give a slightly different proof than one finds in Bonar and Khoury.

First we prove that every rational in $(0,1]$ is a finite select sum. Clearly 1 is a finite select sum. Otherwise: Given $\frac{p}{q}$ we can find the minimum $n$ so that $\frac{1}{n} \leq \frac{p}{q} < \frac{1}{n-1}$ . If $\frac{p}{q} = \frac{1}{n}$ we are done. Otherwise: the strict inequality shows that $pn-p < q$ which means $pn-q < p$ . Then note $\frac{p}{q} - \frac{1}{n} = \frac{pn-q}{qn}$ and this fraction has a strictly smaller numerator than $p$ . So we can repeat our process with this new rational number. And this process must eventually terminate because the numerators generated from this process form a strictly decreasing sequence of positive integers. The process can only terminate when the new faction has a numerator of 1. Hence the original fraction is some sum of fractions with numerator 1.

Now if the rational number $r$ in question is greater than one, one finds $n_1$ so that $\sum^{n_1}_{k=1} \frac{1}{k} \leq r$ but $\sum^{n_1+1}_{k=1} \frac{1}{k} > r$ . Then write $r-\sum^{n_1+1}_{k=1} \frac{1}{k}$ and note that its magnitude is less than $\frac{1}{n_1+1}$ . We then use the procedure for numbers in $(0,1)$ noting that our starting point excludes the previously used terms of the harmonic series.

There is more we can do, but I’ll stop here for now.

January 14, 2016

Trimming a divergent series into a convergent one

Filed under: calculus, induction, sequences, series — Tags: divergent series, harmonic series, selected sums — collegemathteaching @ 10:28 pm

This post is motivated by this cartoon

which I found at a Evelyn Lamb’s post on an AMS Blog, this fun Forbes math post by Kevin Kundson and by a June 2015 article in Mathematics Magazine by R. John Ferdinands called Selective Sums of an Infinite Series.

Here is the following question: start with a divergent series of positive terms which form a decreasing (non-increasing) sequence which tends to zero, say, $\sum^{\infty}_{k =1} \frac{1}{k}$ . Now how does one select a subset of series terms to delete so as to obtain a convergent series? The Kundson article shows that one can do this with the harmonic series by, say, deleting all numbers that contain a specific digit (say, 9). I’ll talk about the proof here. But I’d like to start more basic and to bring in language used in the Ferdinands article.

So, let’s set the stage: we will let $\sum a_k$ denote the divergent sum in question. All terms will be positive, $a_{k} \geq a_{k+1}$ for all $k$ and $lim_{k \rightarrow \infty} a_k = 0$ . Now let $c_k$ represent a sequence where $c_k \in \{0,1\}$ for all $k$ ; then $\sum c_ka_k$ is called a selective sum of $\sum a_k$ . I’ll call the $c_k$ the selecting sequence and, from the start, rule out selecting sequences that are either eventually 1 (which means that the selected series diverges since the original series did) or eventually zero (just a finite sum).

Now we’ll state a really easy result:

There is some non-eventually constant $c_k$ such that $\sum c_ka_k$ converges. Here is why: because $lim_{k \rightarrow \infty} a_k = 0$ , for each $n \in \{1,2,3...\}$ one can find a maximal index $n_j, n_j \notin \{n_1, n_2, ...n_{j-1} \}$ so that $\frac{1}{2^n} > a_{n_j}$ . Now select $c_k = 1$ if $k \in \{n_1, n_2, n_3,... \}$ and $c_k =0$ otherwise. Then $\sum \frac{1}{2^k} > \sum c_ka_k$ and therefore the selected series converges by comparison with a convergent geometric series.

Of course, this result is petty lame; this technique discards a lot of terms. A cheap way to discard “fewer” terms (“fewer” meaning: in terms of “set inclusion”): Do the previous construction, but instead of using $\frac{1}{2}$ use $\frac{M}{M+1}$ where $M$ is a positive integer of choice. Note that $\sum^{\infty}_{k=1} (\frac{M}{M+1})^k = M$

Here is an example of how this works: Consider the divergent series $\sum \frac{1}{\sqrt{k}}$ and the convergent geometric series $\sum (\frac{1000}{1001})^k$ Of course $\frac{1000}{1001} < 1$ so $c_1 = 0$ but then for $k \in \{2,3,....4169 \}$ we have $(\frac{1000}{1001})^k > \frac{1}{\sqrt{k}}$ . So $c_k = 1$ for $k \in \{2,3,4,....4169 \}$ . But $c_{4170} = 0$ because $(\frac{1000}{1001})^{4170} < \frac{1}{\sqrt{4170}}$ . The next non-zero selection coefficient is $c_{4171}$ as $(\frac{1000}{1001})^{4170} > \frac{1}{\sqrt{4171}}$ .

Now playing with this example, we see that $\frac{1}{\sqrt{k}} > (\frac{1000}{1001})^{4171}$ for $k \in \{4172, 4173,....4179 \}$ but not for $k = 4180$ . So $c_k = 0$ for $k \in \{4172,....4179 \}$ and $c_{4180} = 1$ . So the first few $n_j$ are $\{2, 3, ....4169, 4171, 4180 \}$ . Of course the gap between the $n_j$ grows as $k$ does.

Now let’s get back to the cartoon example. From this example, we’ll attempt to state a more general result.

Claim: given $\sum^{\infty}_{k=1} c_k \frac{1}{k}$ where $c_k = 0$ if $k$ contains a 9 as one of its digits, then $\sum^{\infty}_{k=1} c_k \frac{1}{k}$ converges. Hint on how to prove this (without reading the solution): count the number of integers between $10^k$ and $10^{k+1}$ that lack a 9 as a digit. Then do a comparison test with a convergent geometric series, noting that every term $\frac{1}{10^k}, \frac{1}{10^k + 1}......, \frac{1}{8(10^k) +88}$ is less than or equal to $\frac{1}{10^k}$ .

How to prove the claim: we can start by “counting” the number of integers between 0 and $10^k$ that contain no 9’s as a digit.

Between 0 and 9: clearly 0-8 inclusive, or 9 numbers.

Between 10 and 99: a moment’s thought shows that we have $8(9) = 72$ numbers with no 9 as a digit (hint: consider 10-19, 20-29…80-89) so this means that we have $9 + 8(9) = 9(1+8) = 9^2$ numbers between 0 and 99 with no 9 as a digit.

This leads to the conjecture: there are $9^k$ numbers between 0 and $10^k -1$ with no 9 as a digit and $(8)9^{k-1}$ between $10^{k-1}$ and $10^k-1$ with no 9 as a digit.

This is verified by induction. This is true for $k = 1$

Assume true for $k = n$ . Then to find the number of numbers without a 9 between $10^n$ and $10^{n+1} -1$ we get $8 (9^n)$ which then means we have $9^n + 8(9^n) = 9^n (8+1) = 9^{n+1}$ numbers between 0 and $10^{n+1}-1$ with no 9 as a digit. So our conjecture is proved by induction.

Now note that $0+ 1 + \frac{1}{2} + ....+ \frac{1}{8} < 8*1*1$

$\frac{1}{10} + ...+ \frac{1}{18} + \frac{1}{20} + ...+ \frac{1}{28} + \frac{1}{30} + ...+ \frac{1}{88} < 8*9*\frac{1}{10}$

$\frac{1}{100} + ...\frac{1}{88} + \frac{1}{200} + ....\frac{1}{888} < 8*(9^2)\frac{1}{100}$

This establishes that $\sum_{k=10^n}^{10^{n+1}-1} c_k \frac{1}{k} < 8*(9^k)\frac{1}{10^k}$

So it follows that $\sum^{\infty}_{k=1} c_k \frac{1}{k} < 8\sum^{\infty}{k=0} (\frac{9}{10})^k = 8 \frac{1}{1-\frac{9}{10}} = 80$ and hence our selected sum is convergent.

Further questions: ok, what is going on is that we threw out enough terms of the harmonic series for the series to converge. Between terms $\frac{1}{10^k}$ and $\frac{1}{10^{k+1}-1}$ we allowed $8*(9^k)$ terms to survive.

This suggests that if we permit up to $M (10-\epsilon)^k$ terms between $10^k$ and $10^{k+1}-1$ to survive ( $M, \epsilon$ fixed and positive) then we will have a convergent series. I’d be interested in seeing if there is an generalization of this.

But I am tried, I have a research article to review and I need to start class preparation for the upcoming spring semester. So I’ll stop here. For now. 🙂

Comments (1)

March 6, 2010

The Principle of Mathematical Induction: why it works

Filed under: induction, logic, transfinite induction, Uncategorized — collegemathteaching @ 11:03 pm

For those who prefer a video:

I am writing this post because I’ve seen that there is some misunderstanding of what mathematical induction is and why it works.

What is mathematical induction? It is a common proof technique. Basically, if one wants to show that a statement is true in generality and that one can index the set of statements via the integers (or by some other appropriate index set), then one can use induction.Here is a common example: suppose one wants to show that
$1 + 2 + 3 + ....+ k = (1/2)*(k)*(k+1)$ for all positive integers $k$
(for example, $1 + 2 + 3 + 4 + 5 = (1/2)*(5)*(5+1) = 15$ ).

Initial step: $1 = (1/2)*(1)*(1+1)= 1$ so the statement is true for $k = 1$ .

Inductive step: assume that the formula holds for some integer $k$ .
Finish the proof: show that if the formula holds for some integer $k$ , then it holds for $k+1$ as well.

So $1 + 2 + 3 +....+ k + (k+1) = (1 + 2 + ...+ k) + (k+1) =(1/2)*(k)*(k+1) + (k + 1)$
(why? because we assumed that $k$ was an integer for which
$1 + 2 + 3 + ....+ k = (1/2)*(k)*(k+1)$ . )

so $1 + 2 + 3 +....+ k + (k+1) = (1/2)*(k)*(k+1) + (k + 1) = ((1/2)*k + 1)*(k+1)$ (factor out a k+1 term)
$= (1/2)*2*((1/2)*k + 1)*(k+1) = (1/2)*(k+2)*(k+1)=(1/2)*(k+1)*(k+2)=(1/2)*(k+1)*(k+1 + 1)$
which is what we needed to show. So the proof would be done.
Why does induction “prove” anything? Mathematical induction is equivalent to the so called “least positive integer” principle in mathematics.
What is the least positive integer principle? It says this: “any non-empty set of positive integers has a smallest element”. That statement is taken as an axiom; that is, it isn’t something that can be proved.
Notice that this statement is false if we change some conditions. For example, is is NOT true that, say, any set of positive numbers (or even rational numbers) has a smallest element. For example, the set of all numbers between 0 and 1 (exclusive; 0 is not included) does NOT have a least element (not according to the “usual” ordering induced by the real number line; it is an easy exercise to see that the rationals can be ordered so as to have a least element). Why? Let $b$ be a candidate to be the least element. Then $b$ is between 0 and 1. But then $(1/2)b$ is greater than zero but is less than $b$ ; hence $b$ could not have been the least element. Neither could any other number.

Note that the set of negative integers has no least element; hence we need the condition that the integers are positive.

Notice also that there could be groups of positive integers with no greatest element. For example, Let $x$ be the largest element in the set of all even integers. But then $2x$ is also even and is bigger than $x$ . Hence it is impossible to have a largest one.
What does this principle have to do with induction? This is what: an induction proof is nothing more than a least integer argument in disguise. Lets return to our previous example for a demonstation; that is, our proof that $1 + 2 + ....+ n = (1/2)n(n+1)$ We start by labeling our statements: $1 = (1/2)(1)(1+1)$ is statement P(1),
$1 + 2 = (1/2)(2)(2+1)$ is statement P(2), … $1+2+...+ 5 = (1/2)(5)(5+1)$ is statement P(5) and so on.

We assume that the statement is false for some integer. The set of integers for which the statement is false has a least element by the least element principle for positive integers.

We assume that the first integer for which the statement is false is $k+1$ . We can always do this, because we proved that the statement is true for $k = 1$ , so the first possible false statement is $k = 2$ or some larger integer, and these integers can always be written in the form $k + 1$ .

That is why the anchor statement (the beginning) is so important.

We now can assume that the statement is true for $n = 1,....n = k$ since $k+1$ is the first time the statement fails.

Now when we show “if statement P( $k$ ) is true then P( $k+1$ ) is also true (this is where we did the algebra to add up $1 + 2 + .....+ k + (k+1) = ((1/2)k(k+1)) + (k+1) )$ . This contradicts that statement P( $k+1$ ) is false.

Hence the statement cannot be false for ANY positive integer $k$ .
Weak versus strong induction. As you can see, the least positive integer principle supposes that the statement is true for all statements P(1) through P( $k$ ), so in fact there is no difference (when inducting on the set of positive integers) between weak induction (which assumes the induction hypothesis for some integer $k$ ) and strong induction (which assumes the induction hypothesis for $n = 1$ through $n = k$ ).
Other index sets: any index set that one has to induct on has to have the “least element principle” to its subsets. Also, if there is a cardinal w that has no immediate predecessor, then one must “reanchor” the induction hypothesis as $k = w$ prior to proceeding.