Subcategories

• Module 3 Day 6 Challenge Part 1

  Comparing Binomial Coefficients

  0
  Topics
  0
  Posts
  No new posts.
• Module 3 Day 6 Challenge Part 2

  Formula for Binomial Coefficients, Pascal's Triangle

  0
  Topics
  0
  Posts
  No new posts.
• Module 3 Day 6 Challenge Part 3

  Finding an Entry in Pascal's Triangle Based on the Two Above It

  0
  Topics
  0
  Posts
  No new posts.
• Module 3 Day 6 Challenge Part 4

  Proof of Formula for an Entry in Pascal's Triangle

  2
  Topics
  4
  Posts

  T

  @The-Blade-Dancer Good question! Basically, we're modelling the number "\(x\) choose \(y\)" or \(\binom{x}{y}\) as the number of ways to check off \(x\) boxes, if there are \(y\) boxes that can be checked.

  Here, we have 6 boxes, and we want to find the number of ways to check 2 of them. Of course, you know that you can just do it using the formula for \(\binom{6}{2}\). But, we want to see if there is a different way to figure out this number, to find a different expression for this! That might lead to a new formula.

  Here we are with the 6 boxes:

  c151cc6f-8d2e-443b-b288-a40b3f6cb059-image.png

  You see the first box? We're either going to "check" it or not check it. There are the two possible "cases". If we count the number of ways in each of these two cases and add them together, we should get the total number of ways, \(\binom{6}{2}\).

  What happens when we check it?

  75f4520c-db24-475e-acb4-bd374684e94c-image.png

  In this case, if we know that we have to check the first box, how many ways are there to check off the rest? Well remember: We have to check 2 out of the 6 boxes. That means that we can only check off 1 more box. This means there are \(\binom{5}{1}\) ways to check off the rest, because we're really choosing 1 box to check out of the 5 boxes that remain. That's all for this case!

  What happens if we don't check it?

  799d5e95-9b8f-4037-9812-91f91b0a921d-image.png

  I'm putting a red X down to show that we are not allowed to check it in this case! But we still have 2 boxes left to check! And, there are 5 boxes remaining that we could check off. So, we need to choose 2 boxes to check from the 5 boxes remaining. That means there are \(\binom{5}{2}\) ways to check 2 boxes in this case.

  We got \(\binom51\) ways in the first case and \(\binom52\) ways in the second case. These account for all the possibilities. That means that there are \(\binom51+\binom52\) ways in total to check off 2 boxes out of the 6. But we already knew that there were \(\binom62\) ways to do this! We count the same thing in two different ways. That leads us to this cool little formula:
  $$\binom51+\binom52=\binom62$$
  Of course, this trick doesn't just work for \(\binom62\). It works for anything! In fact, we have this general formula, called Pascal's Identity:
  $$\binom{n-1}{k-1}+\binom{n-1}{k} = \binom{n}{k}$$
  The example in the video showed this when \(n=6\) and \(k=2\). Try to prove that this is true for all numbers! All you have to do is take cases, like we did for finding a way to compute \(\binom{6}{2}\) in another way. It's just that instead of numbers, we're only using variables.

  I hope that cleared things up!

• Module 3 Day 6 Challenge Part 5

  Symmetry in Pascal's Triangle

  2
  Topics
  14
  Posts

  A

  @victorioussheep No problem, it was a very intriguing question! 😄

• Module 3 Day 6 Your Turn Part 1

  Hockey Stick Identity

  1
  Topics
  2
  Posts

  N

  This is a little hard to explain with words, so let's look at some pictures and try to properly understand exactly what's going on here. I'm going to borrow Professor Loh's graphics once again:

  alt text

  The basic idea of Pascal's Triangle is that any number is the sum of the two numbers to the right and left in the row above it. How can we use that to our advantage if we want to compute the sum of a diagonal quickly?

  As Professor Loh states in the video, we use something called the Hockey Stick Identity. At the heart of it is the concept of a partial sum. Instead of instantly summing \( 1 + 3 + 6 + 10 + 15 \), we can sum \( 1 + 3 = 4 \) first, and then add the rest later. In this way, we can "baby step" our way through our full sum, and use Pascal's triangle to make our life easier.

  Let's turn back to our image, for a second.
  alt text

  How does this idea of a partial sum help us compute our overall sum? Well, at each step of the process, starting with the smallest numbers on our list, the partial sum of the numbers you've added so far is found down and to the right. $$1 + 3 = 4$$
  $$1 + 3 + 6 = 4 + 6 = 10$$
  $$1 + 3 + 6 + 10 = 4 + 6 + 10 = 10 + 10 = 20$$ and so on.

  At each stage, we're relying on the fact that our earlier partial sums are correct. However, it's not quite correct to say that our first partial sum is \(1 + 3 = 4\). What if we rewrite our sum as \(0+ 1 + 3 + 6 + 10 + 15 \)? Then our first partial sum is \(0+1 = 1\)! And sure enough, below and to the right of our 1, we find another 1. Now let's look at the question:

  alt text

  Our sum here, rewritten as above, is \(0 + 4 + 10 + 20\). But \( 0 + 4 \neq 5\)! We have a problem here. Since our very first partial sum is off by 1, the later ones will be off by 1 as well!

  So in short: for the Hockey Stick Identity to work properly, the first number we're summing must be equal to the number below and to the right of it. This only happens at the edge of Pascal's Triangle, so the Hockey Stick Identity can only be used along diagonals where the numbers reach all the way to the edge.

  Can you think of a way to adapt the Hockey Stick Identity so it's usable on any diagonal?

• Module 3 Day 6 Your Turn Part 2

  Another Explanation for Hockey Stick Identity

  3
  Topics
  5
  Posts

  L

  Does the hockey stick identity work when the "hockey stick" is placed horizontally?

  PS: I haven't proven or disproved it. Just a guess.