Hi Primenewtons, I just wanted to say how much I have enjoyed your maths videos over the years. I start my Maths degree next week and wanted to thank you for all your support and inspiration during my A-levels.
(n Choose k) is the coefficient of x^k in the polynomial (x+1)^n. (n Choose (k-1)) is the coefficient of x^k in the polynomial x*(x+1)^n. Adding the coefficients is equivalent to adding the polynomials and we get: x*(x+1)^n + (x+1)^n = (x+1)*(x+1)^n = (x+1)^(n+1), which has coefficients ((n+1) Choose k) at x^k. QED
Another way you can proof this is by looking at Pascal's Triangle. N choose k and n choose (k+1) are the consecutive numbers of the nth row of the triangle, and (n+1) choose k is directly below Pascal's triangle. So n choose k + n choose (k+1) = (N+1) choose k
Yeah but why is pascal triangle the representation of n choose k then ? Why does the addition keep this representation ? The proof you want to explain is based on the proof that n choose k + n choose (k+1) = (n+1) choose (k+1) so it doesn’t really hold
its crazy how ive found myself improving at math every time i watch your videos! knew from the get go we would be using ncr formula and manipulation! thanks man!! 🙏😁
Fix one element of the set of n+1. n choose k is the number of ways of choosing a set of k that excludes that element and n choose k-1 is the number of ways including that element. Done.
With this idrentity you build Pascal's triangle so some people call it Pascal's identity I can give you two or three finite sums witth binomial coefficients to calculate
This was a very easy problem, in India we do such kinds of problems in 11th grade and in cram schools this may be practiced in 9th and 10th grade so... 😅
From a recursive point of view (n+1 choose k) can be thought as this... : To choose k things from n+1 things, we can either Include/choose the first thing and there are still (k-1) things to choose still out of n things left to choose from, i.e. (n choose k - 1) OR Exclude the first thing, i.e. we have not chosen anything yet, we still need to choose k things, but because we excluded 1 thing already, there are only n candidates left to choose from, i.e. (n choose k) Since we have an OR situation, we add. therefore (n+1 choose k) = (n choose k-1) + (n choose k) -------------------------------------------------------------------------------------------------------- We can extend this recursive idea to subfactorials or derangements. Deranging n objects = !n Say we have n people and n hats, and we want to make sure each person does not get their own hat back. Either, we choose a person "i" and a hat that is not theirs (say hat "j") and we make sure person "j" receives hat "i", that is they swap hats. This means in this case, there are still (n-2) people and (n-2) hats left to derange, i.e. !(n-2). However, still recall that there are (n-1) ways for person "i" to choose hat "j" (not their own hat). Combining these two together we get ((n-1))(!(n-2)) OR we choose person "i" and a hat that is not theirs (say hat "j") and make sure person "j" DOES NOT receive hat "i". This means we can temporarily assign "hat i" as if it belongs to "person j". so we have person j and (n-2) other people to derange still since we do not want "hat i" to be in person's "j" possesion. i.e. we have to derange (n-1) things. But recall person "i" initially could choose an arbitrary hat "j" that is not theirs (there are n-1 ways to do this), so we get ((n-1))(!(n-1)) Putting this together, we get: !n = ((n-1))(!(n-2)) + ((n-1))(!(n-1)) !n = (n-1)(!(n-2) + !(n-1)) !n = (n-1)(!(n-1) + !(n-2))
@PrimeNewtons hello sir I like your content. I'm from South Africa, and I'm doing grade 11, there's a problem that I want to send and I want you to solve it because you make things simple for me by demystifying maths problems. How can I get in touch with you?
@@nerdomatic8077 yes but there are many other beautiful ways, one is a combinatorics approach and counting the number of arrangements, which is extremely beautiful
Initially I thought you'd be showing a real combinatorial proof, and now I'm a bit disappointed to only see some convoluted algebraic manipulations of the defining expression. 😢 The actual combinatorial proof is much shorter (just about two or three sentences actually!) and much more intuitive. 😊 By the way, the object you manipulated is called the Binomial Coefficient. I know it's common knowledge and I'm saying this only because you didn't mention it once in the whole video.
@@PrimeNewtons What you showed as a proof is completely ok and effective, I just wouldn't call it a "combinatorics" proof, because it doesn't use combinatorial arguments IN THE PROOF ITSELF. This is what may raise different expectations on the viewer's side. That's what I meant to say; I enjoyed the video nonetheless. 😃 The combinatorics argument goes something like this: When choosing k out of n+1 elements, and fixing one choice to a specific element (of the n+1), how many ways are there to choose the other k-1 elements out of the remaining n? And now, when I'm not using this one specific element at all in my choice of k elements, how many ways are there? Finally, add these two numbers, because their resulting combinations are disjoint.
well that looks like a Fibonacci definition. n * n-1 = then next Fibonacci number. so F(n+1)= F(n) +F(n-1). Here we are just saying to select k options form the list of Fibonacci. Not a real proof at all, but just a weird observation of the pattern.
