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!! 🙏😁
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
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))
