1
00:00:00,280 --> 00:00:02,945
Powers versus factorials

2
00:00:02,945 --> 00:00:03,930
[SOUND].

3
00:00:03,930 --> 00:00:05,110
Seen

4
00:00:09,050 --> 00:00:14,540
the convergence of some series that
involved both powers and factorials.

5
00:00:14,540 --> 00:00:17,680
Seen that this series that some angles
from 1 to infinity

6
00:00:17,680 --> 00:00:21,270
of n factorial over n over 2 to the nth
power.

7
00:00:21,270 --> 00:00:25,420
Converges but this series, the sum n it
goes from 1 to

8
00:00:25,420 --> 00:00:30,800
infinity of n factorial over n over 3 to
the nth power diverges.

9
00:00:30,800 --> 00:00:35,040
Well, this says something about the
relative sizes of n factorial and

10
00:00:35,040 --> 00:00:37,320
n over 2 to the nth power.

11
00:00:37,320 --> 00:00:40,870
Now, since this is a convergent series,
the limit

12
00:00:40,870 --> 00:00:44,570
of the nth term must be equal to 0.

13
00:00:44,570 --> 00:00:47,310
So we know that the limit as n approaches
infinity of

14
00:00:47,310 --> 00:00:50,850
n factorial over n over 2 to the nth power
is 0.

15
00:00:50,850 --> 00:00:55,490
And that's also the case if we look at the
limit over here.

16
00:00:55,490 --> 00:01:00,380
The limit of n factorial over n over 3 to
the nth power as n approaches infinity

17
00:01:00,380 --> 00:01:01,290
is infinity.

18
00:01:01,290 --> 00:01:04,590
Not just because this series diverges but
because of the way

19
00:01:04,590 --> 00:01:08,990
in which we showed this series diverge by
applying the ration test.

20
00:01:08,990 --> 00:01:10,940
So 2 is too small.

21
00:01:10,940 --> 00:01:15,290
In that case, the denominator ends up
overpowering the numerator.

22
00:01:15,290 --> 00:01:16,940
And 3 is too big.

23
00:01:16,940 --> 00:01:20,550
In that case, the numerator ends up
overpowering the denominator.

24
00:01:20,550 --> 00:01:26,260
These two forces are balanced.
When two and three are replaced by e.

25
00:01:27,860 --> 00:01:30,390
So if I look at this sequence, the
sequence a sub

26
00:01:30,390 --> 00:01:34,520
n equals n factorial over n over e to the
nth power,

27
00:01:34,520 --> 00:01:37,520
in that case, the limit as n approaches
infinity of the

28
00:01:37,520 --> 00:01:42,110
ratio between the n plus first and the nth
term is 1.

29
00:01:42,110 --> 00:01:46,640
So the limit of the ratio between
subsequent terms is 1.

30
00:01:46,640 --> 00:01:49,450
And that means if you were to look at the
series and

31
00:01:49,450 --> 00:01:53,110
try to apply the ratio test, the ratio
test would be silent in

32
00:01:53,110 --> 00:01:54,350
this case.

33
00:01:54,350 --> 00:01:58,220
But still I think this is a really
interesting sequence to consider.

34
00:01:58,220 --> 00:02:02,990
Let me just warn that these facts do not
imply that the

35
00:02:02,990 --> 00:02:07,810
limit of a sub n approaches infinity as 1,
that's not even true.

36
00:02:07,810 --> 00:02:08,030
Right?

37
00:02:08,030 --> 00:02:10,930
But what am I trying to get at here,
right?

38
00:02:10,930 --> 00:02:13,940
What we've seen is that n factorial must
be way

39
00:02:13,940 --> 00:02:18,850
smaller than n over 2 to the nth power
because this

40
00:02:18,850 --> 00:02:20,525
limit was equal to 0.

41
00:02:22,080 --> 00:02:26,830
We've also seen that n factorial must be a
ton bigger than n over 3 to the nth power.

42
00:02:27,850 --> 00:02:30,930
And the question now is if n factorial is

43
00:02:30,930 --> 00:02:32,920
way smaller than n over 2 and n
factorial's way

44
00:02:32,920 --> 00:02:35,310
bigger than n over 3, how then does n

45
00:02:35,310 --> 00:02:39,218
factorial really compare to n over e to
the n?

46
00:02:39,218 --> 00:02:44,020
We can analyse this sequence a sub n a
little bit more if we're willing to use

47
00:02:44,020 --> 00:02:45,600
an interval.
Okay.

48
00:02:45,600 --> 00:02:51,130
So, let's evaluate log of n factorial, at
least approximate it.

49
00:02:51,130 --> 00:02:56,560
Log of n factorial, that's log of 1 times
2 times 3 all

50
00:02:56,560 --> 00:03:01,990
the way up to n but that's log of a
product which is the sum of the logs.

51
00:03:01,990 --> 00:03:07,660
So this is the sum, k goes from 1 to n.
I'm just log of k.

52
00:03:07,660 --> 00:03:09,630
Now you can approximate

53
00:03:09,630 --> 00:03:14,680
this sum with an integral, this is
approximately the integral from 1 to n.

54
00:03:16,360 --> 00:03:18,980
of log x dx.

55
00:03:20,610 --> 00:03:23,390
I gotta figure out what is this definite
integral.

56
00:03:23,390 --> 00:03:26,990
I need to know an anti derivative for log
x.

57
00:03:26,990 --> 00:03:35,530
But it turns out the derivative of x log x
minus x is equal to log x.

58
00:03:35,530 --> 00:03:38,460
So there is an anti derivative of log x
and

59
00:03:38,460 --> 00:03:42,190
I can use that anti derivative to evaluate
this integral.

60
00:03:42,190 --> 00:03:45,489
So this integral is, let me write down the
anti derivative, x.

61
00:03:46,530 --> 00:03:53,140
Log x minus x evaluated at n and 1 and
take the difference.

62
00:03:53,140 --> 00:03:57,750
So this is n log n minus n, it's what I
get when

63
00:03:57,750 --> 00:04:00,470
I plug in n, minus what I get when I plug
in 1,

64
00:04:00,470 --> 00:04:05,970
which is 1 times log 1 minus 1.
Well

65
00:04:05,970 --> 00:04:10,465
this is n log n minus n log 1 is 0 minus

66
00:04:10,465 --> 00:04:15,990
negative 1 plus 1.
this is approximately

67
00:04:15,990 --> 00:04:21,620
n log n minus n.
Now we can simplify this.

68
00:04:21,620 --> 00:04:23,290
Okay.
So I've got.

69
00:04:23,290 --> 00:04:26,080
Log of n factorial is

70
00:04:26,080 --> 00:04:31,200
approximately n log n minus n.
Let me rewrite this side.

71
00:04:31,200 --> 00:04:35,480
Instead of n log n I'll write that as log
of n to the n.

72
00:04:35,480 --> 00:04:41,820
And instead of minus n I"ll write minus
log e to the n.

73
00:04:41,820 --> 00:04:45,290
You know this is a difference of logs,
which is the log

74
00:04:45,290 --> 00:04:49,900
of the ratio, n to the n, over e to the n.

75
00:04:49,900 --> 00:04:51,352
Which I could

76
00:04:51,352 --> 00:04:56,268
also write as log of n over e to the nth
power.

77
00:04:56,268 --> 00:04:59,628
So I've got log of n factorial is
approximately

78
00:04:59,628 --> 00:05:01,859
log of n over e to the nth power.

79
00:05:01,859 --> 00:05:02,595
So then,

80
00:05:02,595 --> 00:05:03,055
[LAUGH]

81
00:05:03,055 --> 00:05:06,551
you hope that I just conclude that n
factorial

82
00:05:06,551 --> 00:05:10,490
is approximately n over e to the nth
power.

83
00:05:10,490 --> 00:05:13,240
So how good is this approximation?

84
00:05:13,240 --> 00:05:14,660
Well, we can look at some numerical

85
00:05:14,660 --> 00:05:17,640
evidence, I mean, here, I calculated 10
factorial.

86
00:05:17,640 --> 00:05:20,540
It's about 3 times 10 to the 6th.

87
00:05:20,540 --> 00:05:24,650
And here I've got ten over e to the 10th
power and it's not so far off.

88
00:05:24,650 --> 00:05:27,360
Let's try it with some bigger numbers as
well.

89
00:05:28,380 --> 00:05:34,740
Here's 25 factorial.
It's about 1.55 times 10 to the 25th.

90
00:05:34,740 --> 00:05:41,486
And it's 25 over e to the 25th power.
Well it's 1.23 about times 10 to the 24th.

91
00:05:41,486 --> 00:05:44,870
That's not so terrible.

92
00:05:44,870 --> 00:05:47,730
This is usually called Sterling's
approximation.

93
00:05:47,730 --> 00:05:50,750
A better approximation is this.

94
00:05:50,750 --> 00:05:53,390
That n factorial is approximately n over e
to

95
00:05:53,390 --> 00:05:59,552
the nth power.
Times this factor, the square

96
00:05:59,552 --> 00:06:05,349
root of 2 pi n and this usually goes by

97
00:06:05,349 --> 00:06:11,146
the name Stirling's approximation

98
00:06:11,146 --> 00:06:12,536
[SOUND].