1
00:00:00,006 --> 00:00:04,721
Coshi condensation.

2
00:00:04,721 --> 00:00:07,226
[MUSIC]

3
00:00:07,226 --> 00:00:13,360
Let's think back to the harmonics series.
Well here's the harmonic series.

4
00:00:13,360 --> 00:00:17,410
And we proved that it diverges.
And how do we do that?

5
00:00:17,410 --> 00:00:19,620
Well, we did this grouping trick.

6
00:00:19,620 --> 00:00:24,000
Here's the beginning of the harmonic
series and it keeps on going.

7
00:00:24,000 --> 00:00:27,890
What we saw was that we got a one here and
a half here.

8
00:00:27,890 --> 00:00:32,430
This third and this fourth can be grouped
together and the next four

9
00:00:32,430 --> 00:00:34,930
terms can be grouped together.

10
00:00:34,930 --> 00:00:38,770
And then the next eight terms will group
together and so on.

11
00:00:38,770 --> 00:00:42,520
But this this group here is at least a
half.

12
00:00:42,520 --> 00:00:46,360
because it's two terms that are each as
big as a fourth.

13
00:00:46,360 --> 00:00:49,980
This next group here is also at least a
half,

14
00:00:49,980 --> 00:00:53,430
because it's four terms that are each at
least an eighth.

15
00:00:53,430 --> 00:00:57,510
And then the next group of eight terms is
at least a half, and the next group

16
00:00:57,510 --> 00:00:59,320
of 16 terms is at least a half.

17
00:00:59,320 --> 00:01:02,870
So this is even worse than adding up 1
plus a half

18
00:01:02,870 --> 00:01:07,480
plus a half plus a half plus a half, and
that series diverges.

19
00:01:07,480 --> 00:01:10,050
So we're able to show that the harmonic
surge diverges by

20
00:01:10,050 --> 00:01:14,560
doing this grouping into piles with sizes
the power of two.

21
00:01:14,560 --> 00:01:17,410
This isn't just some one off trick, this
is

22
00:01:17,410 --> 00:01:21,180
a technique that we can generalize and
then apply broadly.

23
00:01:21,180 --> 00:01:22,510
That we used it for the

24
00:01:22,510 --> 00:01:25,450
harmonic series to show that the series
diverged.

25
00:01:25,450 --> 00:01:30,590
But we could also use the same kind of
thinking to show that a series converges.

26
00:01:30,590 --> 00:01:34,320
The name for this trick is Cauchy
Condensation.

27
00:01:34,320 --> 00:01:35,310
Here's how it goes.

28
00:01:35,310 --> 00:01:38,400
At least when using it to prove
convergence.

29
00:01:38,400 --> 00:01:41,260
Let's suppose that I've got a decreasing
sequence

30
00:01:41,260 --> 00:01:44,370
and that all of the terms are positive.

31
00:01:44,370 --> 00:01:47,540
I want to know does this series, the sum k
goes from one to

32
00:01:47,540 --> 00:01:54,840
infinity of a sub k converge or diverge?
I can group them by powers of two.

33
00:01:54,840 --> 00:01:57,810
So what I mean is I'll put a sub one by
itself.

34
00:01:57,810 --> 00:02:03,153
I'll group together a-sub-2 and a-sub-3.
I'll group together a-sub-4, a-sub-5,

35
00:02:03,153 --> 00:02:08,431
a-sub-6, and a-sub-7.
I'll group a-sub-8 alongside a-sub-9,

36
00:02:08,431 --> 00:02:13,536
a-sub-10, a-sub-11, a-sub-12, a-sub-13,
a-sub-14,

37
00:02:13,536 --> 00:02:17,280
a-sub-15.
And then I'll group a sub 16, a sub 17.

38
00:02:17,280 --> 00:02:20,190
I mean, I keep on going until I get a sub

39
00:02:20,190 --> 00:02:24,270
31 and then I start a new group at a sub
32.

40
00:02:24,270 --> 00:02:26,810
Now I'll overestimate the groups.

41
00:02:26,810 --> 00:02:29,290
Well, how big is a sub 2 plus a sub 3?

42
00:02:29,290 --> 00:02:34,550
The key fact here, is that the sequence of
the a sub k's is decreasing.

43
00:02:34,550 --> 00:02:37,110
That means that a sub 3 is smaller than a
sub 2.

44
00:02:37,110 --> 00:02:38,570
So, if I add a

45
00:02:38,570 --> 00:02:43,410
sub 2 and a sub 3, the result is less than
twice a sub 2.

46
00:02:43,410 --> 00:02:46,480
What about this next group.

47
00:02:46,480 --> 00:02:50,410
What's a sub 4 plus a sub 5 plus a sub 6
plus a sub 7?

48
00:02:50,410 --> 00:02:54,330
Well, a sub 5, a sub 6 and a sub 7 are all
less than a sub 4.

49
00:02:54,330 --> 00:02:56,190
Again, because the sequence is decreasing.

50
00:02:57,370 --> 00:03:00,840
So, if I add these 4 numbers up, the
result

51
00:03:00,840 --> 00:03:03,840
is less than if I just multiplied the
fourth term

52
00:03:03,840 --> 00:03:07,880
by 4.
What about the next eight terms?

53
00:03:07,880 --> 00:03:12,730
Well, these terms, from a sub 9 through a
sub 15, are all smaller than a sub 8.

54
00:03:12,730 --> 00:03:18,323
So these eight terms, all together are
less, than just

55
00:03:18,323 --> 00:03:24,380
copies of 8 sub 8.eight and it keeps on
going, right.

56
00:03:24,380 --> 00:03:28,870
The next 16 terms, if I were to group them
all together, would be less than

57
00:03:28,870 --> 00:03:31,640
16 copies of a sub 16 and so on.

58
00:03:31,640 --> 00:03:35,070
Let me write down a precise statement of
what we're doing.

59
00:03:35,070 --> 00:03:38,160
So here's how I can write down the
grouping in symbols.

60
00:03:38,160 --> 00:03:41,830
Look at the sum of the a sub k's, k goes
from

61
00:03:41,830 --> 00:03:45,120
1 all the way up to 1 less a power of 2.

62
00:03:45,120 --> 00:03:47,430
So 2 to the n minus 1 say.

63
00:03:47,430 --> 00:03:51,330
So this would be like adding up the first
seven

64
00:03:51,330 --> 00:03:54,580
terms, or the first 15 terms, or the first
31 terms.

65
00:03:54,580 --> 00:03:57,619
It's a collection of terms where I can
actually do the grouping.

66
00:03:58,660 --> 00:04:01,630
Well, this is less than or equal to, then,
the

67
00:04:01,630 --> 00:04:05,150
sum of what happens after I do the
grouping, right?

68
00:04:05,150 --> 00:04:09,590
Which is 2 to the k times a sub 2 to the
k.

69
00:04:09,590 --> 00:04:12,440
This is what I get when I do this
grouping.

70
00:04:12,440 --> 00:04:16,990
K goes from 0, all the way up to n minus
1.

71
00:04:16,990 --> 00:04:18,890
Why is this significant?

72
00:04:18,890 --> 00:04:19,860
So, we were originally

73
00:04:19,860 --> 00:04:21,610
interested in studying this series and

74
00:04:21,610 --> 00:04:24,580
determining whether this series converged
or diverged.

75
00:04:24,580 --> 00:04:27,740
And now, we're led to studying this
series.

76
00:04:27,740 --> 00:04:30,630
The sum k goes from 0 to infinity of 2 to

77
00:04:30,630 --> 00:04:34,480
the k times the 2 to the kth term in the
sequence.

78
00:04:34,480 --> 00:04:36,670
I'm going to call this series the

79
00:04:36,670 --> 00:04:40,820
condensed series associated to this
series.

80
00:04:40,820 --> 00:04:44,060
Now what if the condensed series
converges?

81
00:04:44,060 --> 00:04:44,610
So,

82
00:04:44,610 --> 00:04:50,829
if this condensed series converges right,
then what happens?

83
00:04:50,829 --> 00:04:52,633
Recall what I know.

84
00:04:52,633 --> 00:04:58,870
This condensed series is over estimating
the original series.

85
00:04:58,870 --> 00:05:00,840
So, if I'm trying to study something about
the

86
00:05:00,840 --> 00:05:03,920
partial sums of the original series, what
I know

87
00:05:03,920 --> 00:05:06,090
now is that those partial sums for the
original

88
00:05:06,090 --> 00:05:09,748
series are bounded above by the value of
the

89
00:05:09,748 --> 00:05:11,339
convergence condense series.

90
00:05:12,450 --> 00:05:15,040
I also know that the partial sums for the
original series are

91
00:05:15,040 --> 00:05:19,620
increasing and that's just because all of
the a sub k's are positive.

92
00:05:19,620 --> 00:05:21,800
So as I add up more and more of the

93
00:05:21,800 --> 00:05:24,500
a sub k's, I'm getting a bigger and bigger
number.

94
00:05:24,500 --> 00:05:27,380
So the sequence of partial sums is
increasing.

95
00:05:27,380 --> 00:05:29,340
That means the sequence of partial sums

96
00:05:29,340 --> 00:05:33,480
is bounded above and increasing and
therefore convergent.

97
00:05:33,480 --> 00:05:34,940
And what that means, then is

98
00:05:34,940 --> 00:05:38,930
that the original series that I'm
interested in converges.

99
00:05:38,930 --> 00:05:40,660
Let's summarize the theorem.

100
00:05:40,660 --> 00:05:44,060
So here's a statement of the Cauchy
Condensation test.

101
00:05:44,060 --> 00:05:48,630
You've got a sequence, which is decreasing
and all the terms are positive.

102
00:05:48,630 --> 00:05:54,140
Then the series, sum k goes from one to
infinity a sub k converges,

103
00:05:54,140 --> 00:05:59,150
if the condensed series converges.
That's what we just proved.

104
00:05:59,150 --> 00:06:00,130
And in

105
00:06:00,130 --> 00:06:04,870
fact, it's an if and only if.
So the fate of the condensed series is

106
00:06:04,870 --> 00:06:12,806
exactly the same as the fate of the
original series.

107
00:06:12,806 --> 00:06:19,739
[SOUND]