Video Transcript
Write 𝑛 choose 𝑟 plus 𝑛 choose
𝑟 plus one in the form 𝑎 choose 𝑏.
Initially, we might look at these
combinations and think we should expand them with the factorial formula to add them
together. And while it’s possible to use this
method, there’s a much more straightforward approach. Instead, we can use the recursive
property for combinations. This tells us that 𝑛 minus one
𝐶𝑟 plus 𝑛 minus one 𝐶𝑟 minus one is equal to 𝑛 choose 𝑟.
Now at this point, we’re looking at
our combination and thinking, how does this help us since we don’t have any
instances of 𝑛 minus one in our sum of combinations? But we know that we’re looking for
something in the form 𝑎𝐶𝑏. So first, we convert our recursive
property to include 𝑎’s and 𝑏’s in place of the 𝑛’s and 𝑟’s. And we have 𝑎 minus one choose 𝑏
plus 𝑎 minus one choose 𝑏 minus one is equal to 𝑎 choose 𝑏. We can then use this to try and
work backwards.
Notice that in the recursive
property, we’re adding two combinations with the same set size. That’s 𝑎 minus one. And in one combination, we’re
choosing a certain value, that’s 𝑏, and in the other combination, we’re choosing
one less than that, 𝑏 minus one. So now going back to our sum of
combinations, we have 𝑟 plus one and 𝑟, which is one less than 𝑟 plus one. And since 𝑟 is one less than 𝑟
plus one, we swap the terms in the recursive property around so that our 𝑟
corresponds to 𝑏 minus one. And our 𝑟 plus one corresponds to
𝑏.
Since we’re dealing with addition,
it’s fine to change the order and the sum is still equal to 𝑎 choose 𝑏. Doing all this gives us 𝑛 equal to
𝑎 minus one. Now if 𝑛 equals 𝑎 minus one,
adding one to both sides gives 𝑛 plus one equals 𝑎. So with 𝑎 equal to 𝑛 plus one and
𝑏 equal to 𝑟 plus one, we have 𝑎 and 𝑏 in terms of 𝑛 and 𝑟. And this means we’ve been able to
write the two combinations in our sum as a combination in the form 𝑎 choose 𝑏. So we have 𝑛 choose 𝑟 plus 𝑛
choose 𝑟 plus one is equal to 𝑛 plus one choose 𝑟 plus one.
