RARE PROOF of well-known sum

You have what it takes to defeat the evil Sir Chalkkington of Talc, just watch the next 3 videos all the way through the credits and you'll have defeated the dastardly Sir Chalkington of Talc

🌟Support the channel🌟

🌟my other channels🌟

🌟My Links🌟

🌟How I make Thumbnails🌟

🌟Suggest a problem🌟

[spaghetti]

Reindex the sum so it goes in reverse. Use the symmetry of binomial coefficients to recover n choose k. Add the two sums to factor out n. Use the fact that the row sum is 2^n then divide by 2.

[TwoGrids]

The wide range of topics covered is actually so valuable. Thank you!

[joelklein]

I discovered this channel maybe 2-3 days ago, and I'm still amazed at how nonchalantly you cover just about any topic. With no necessary end goal, leaving the viewers with open questions they can munch on. Just casually enjoying maths!

[noway]

Very nice. I like how whenever you do something nontrivial you explain and justify it (e.g. linear operator inside finite sum). Keep it up!

[jonatansvensson]

Another proof which I discovered solving a counting problem two different ways: The problem asks us to calculate the sum of |A| where we let A range over all elements in the power set of a set M with size n. One way to approach the problem is to consider how many subsets are of size k (which is n choose k) and then those subsets contribute with a total cardinality to our sum of k*(n choose k). When you sum over k from 0 to n you get the sum we want i.e the left hand side of the identity. Another way to look at the problem goes as follows. Notice that all elements from M get counted in the sum the same number of times due to symmetry. So the question is, how many times does a given element get counted in the sum? Well we count it once for every subset where it is included i.e 2^(n-1) times (the number of subsets of M including this element). We do this for n elements hence the sum should be n*2^(n-1) which is the right hand side of the identity.

[jakobr_]

I had this exact problem on a final exam, and was instructed to prove it in terms of “committees”, i.e. different ways to group people together. I basically figured it out the exact same way as the second method in this video. My thought was, “The committee is meeting at someone’s house, one of their own”. Either they choose the location first, then individually determine if each person is attending, or they choose the number of people first, then who’s chosen, then where they’re meeting. Same as in the video.

[algorithminc.]

Very very nice. Enjoyed the proof. Funny that sometimes - even for those of us over here who love proofs - we forget to look closely at the bits that we use every day. Thanks ... Cheers!

[seanfraser]

The general formula is:

n!/(n-r)!*2^(n-r) = sum_k=r^n [k!/(k-r)!*(nCk)],
where 0 <= r <= n.

This can be proven either using the rth derivative on the binomial expansion, or by counting the number of committees that can be formed from a pool of n candidates where there are r chairpeople in a committee.

[manucitomx]

I quite liked this.
Thank you, professor.

[jesusalej]

What is a Combo Notarial? Es acaso una oferta hecha por un notario para hacer la escritura de una casa y un terreno al mismo precio?

[schweinmachtbree]

1:49 Eh, I don't think using limits instead of evaluation is any cleaner - using limits, the "lim_{x→1}" gets carried all the way through on the left, whereas using evaluation, the "|_{x=1}" would likewise get carried all the way through on the right, so it's just a matter of left vs. right. Since students encounter limits after derivatives, and since limits are much more gnarly than evaluation 'under the hood' (∀ε∃δ∀y : 0<|y-x|<δ ⇒ |p(y)-p(x)|<ε), I think using them overcomplicates the argument/makes it less accessible.

[AngelMedina-ehrb]

Where did you purchase your chalkboard

[whozz]

Let (n, k) the be n choose k and S = Σ k*(n, k) [1]

Since finite sums can be summed backwards,
S = Σ (n-k)*(n, n-k). [2]

Given that (n, n-k) = (n, k), the sum of [1] and [2] is
2S = Σ n*(n, k)
2S = n2^n

Therefore,
S = n2^(n-1).

[rtheben]

And there is the obvious 3rd methods by cancelling k with the k in k! In the denominator, then factor out of the summation “n” to get get the bynomial expansion of (1+1)^(n-1)

[krisbrandenberger]

Hey, Michael! In order to prove the follow up exercises, you could just repeat the process as for the goal, by choosing x^(j-k) to be inside the summand of the same sum, but with respect to j.

[kristianwichmann]

Very nice. Some story proofs in the style of Joe Blitzstein would be super cool.

[fartoxedm]

We also can:
1) This sum counts how many 1s are in the truth table so, since there're 2^(n-1) 1s in each column then we have n * 2^(n-1) 1s in total(n columns)
2) (n, k) = n/k * (n-1, k-1)

[Fine_Mouche]

what about (X, A, P) ? X, and A the same, and P a Partition of {1, 2, ..., n} ?

[kilianklaiber]

My first intuition would be to prove this with mathematical induction. The first proof is really elegant. Thanks for sharing!

[samuelbam]

There is also a nice combinatorial proof of the formula sum_(k=0)^n \binom{n}{k}^2 = \binom{2n}{n} and I think this might be a good exercise, so I will not spoil the proof here (one can proof it with induction as well, but I don't like this proof as much)


Maybe a small hint: Consider Pascal's triangle.