WEBVTT

00:00.540 --> 00:05.400
Welcome to another video about binomial coefficients.

00:06.100 --> 00:11.600
In this topic, the concept must be understood in the first place.

00:13.360 --> 00:16.420
Computers can calculate much better than we do.

00:16.520 --> 00:20.880
Once you have understood what a binomial coefficient is, you can very

00:20.880 --> 00:29.140
quickly answer the question why for every natural number n, 2n over n

00:29.140 --> 00:33.860
is equal to the sum of the squares of the binomial coefficients n over

00:33.860 --> 00:37.400
k, where k is the sum of 0 to n.

00:39.320 --> 00:41.240
Now what is the left side, i.e.

00:41.340 --> 00:42.740
2n over n?

00:43.540 --> 00:48.300
If you have seen the video on understanding or calculating binomial

00:48.300 --> 00:52.580
coefficients, you know that this binomial coefficient is equal to the

00:52.580 --> 00:57.460
number of all binary 2n tuples with exactly n ones.

00:58.560 --> 01:02.700
Specifically, this is a binary 10 tuple with 5 ones.

01:03.460 --> 01:06.340
If you assign 10 things to the 10 places of this tuple seen from left

01:06.340 --> 01:15.520
to right, numbered from 1 to 10, this tuple indicates via the 1s that

01:15.520 --> 01:20.620
the things 1, 5, 6, 8 and 10 have been selected.

01:21.680 --> 01:25.140
Binary n-tuples therefore describe partial quantities of quantities.

01:26.160 --> 01:30.120
Why is 2n over n equal to the sum of the squares of the binomial

01:30.120 --> 01:31.180
coefficients n over k?

01:33.380 --> 01:37.460
This equation screams for a case distinction.

01:37.460 --> 01:44.340
We distinguish the binary 2n tuples with n ones by how many of the

01:44.340 --> 01:49.640
ones are at the first n places and we call this number k.

01:50.720 --> 01:53.420
k can assume any value from 0 to n.

01:54.860 --> 01:58.920
What is the product of these two binomial coefficients?

01:58.920 --> 02:04.560
Well, it is the number of all binary 2n tuples with exactly k ones at

02:04.560 --> 02:11.520
the first n places and exactly n minus k ones at the last n places.

02:12.240 --> 02:17.660
The binomial coefficient n over k is the number of possibilities to

02:17.660 --> 02:19.820
select k for ones from the first n places of the tuple.

02:21.840 --> 02:27.740
For each such selection, there are then n over n minus k possibilities

02:27.740 --> 02:31.960
to select n minus k for ones from the last n places.

02:32.860 --> 02:36.260
This means that there are exactly n ones in the 2n tuple.

02:37.540 --> 02:45.700
If we now consider the equation n over n minus k equals n over k

02:45.700 --> 02:48.380
created by flipping the 1s and 0s, the claim follows, because in the

02:48.380 --> 02:51.320
case distinction we have to sum over the values of k.

02:53.680 --> 02:58.580
Of course, one can try to prove the above equation with the help of

02:58.580 --> 03:05.560
complete induction, but one does not get any insight into why this

03:05.560 --> 03:06.460
equation applies.