RE: The Mathematical Proof Thread
October 8, 2016 at 9:53 am
(This post was last modified: October 8, 2016 at 9:58 am by Kernel Sohcahtoa.)
Here's a pretty cool proof of the binomial theorem via mathematical induction
Ron Joniak
Here are some additional notes which may be helpful.
At 6:35, RonJoniak uses the concept of the index shift. Now, this may seem extraneous, but we actually need to use the index shift: this will eventually allow us to combine the two summations into one summation (after stripping out terms from the non-shifted summation); and once we get it into one summation, this will get us closer toward manipulating the left hand side of the proof into the right hand side of the proof. Here's a site that explains the concept of the index shift (the index shift material will be toward the middle/bottom of the page)
P.S. Toward the end of the video he actually puts the stripped out x^(m+1) and y^(m+1) terms back into the summation. Hence, when he does this, putting the x^(m+1) term back into the summation (using k=0) puts the lower limit of the summation back to zero. Likewise, when he puts the y^(m+1) term back into the summation (using k=m+1), this puts the summation's upper limit back to m+1, enabling us to reproduce the right hand side of the proof, which was the objective all along.
You will encounter index shifts in differential equations. In particular, you will need index shifts when finding series solutions to differential equations.
At 11:55, Ron Joniak mentions Pascal's rule. Pascal's rule is the following equation:
C(n+1,k)=C(n,k-1) +C(n,k). Assume that we have a set A={0,1,2,3,.....,n}. Then our set has n+1 elements (including the zero gives it an additional element), so the number of k element subsets in A can be represented as C(n+1,k) (note, if A={1,2,3...n}, then it would have n elements and it could be represented as C(n,k)). Another way to think about C(n+1,k) is that we are choosing k elements from a set with n+1 elements. For example, C(3,1) means that we are choosing one element from a set with 3 total elements).
P.S. Also, for the sake of curiosity, if we wanted to put C(n+1,k) into equation form then we would get C(n+1,k)= (n+1)!/(k!(n+1-k)!). However, this is not needed for the proof, as it is unnecessary.
Now, Pascal's rule states that "the number of k element subsets in A is equal to the number of k element subsets that contain zero plus the number of k element subsets that do not contain zero."(Hammack, Book of Proof, pg 78).
Please note that I used the form C(n+1,k)=C(n,k-1) +C(n,k) to illustrate Pascal's rule. In the video, the author uses a different form, but the two forms are just different ways of expressing the exact same idea; in this post, the form I used is easier to write via a keyboard, so my apologies for any inconvenience.
Ron Joniak
Here are some additional notes which may be helpful.
At 6:35, RonJoniak uses the concept of the index shift. Now, this may seem extraneous, but we actually need to use the index shift: this will eventually allow us to combine the two summations into one summation (after stripping out terms from the non-shifted summation); and once we get it into one summation, this will get us closer toward manipulating the left hand side of the proof into the right hand side of the proof. Here's a site that explains the concept of the index shift (the index shift material will be toward the middle/bottom of the page)
P.S. Toward the end of the video he actually puts the stripped out x^(m+1) and y^(m+1) terms back into the summation. Hence, when he does this, putting the x^(m+1) term back into the summation (using k=0) puts the lower limit of the summation back to zero. Likewise, when he puts the y^(m+1) term back into the summation (using k=m+1), this puts the summation's upper limit back to m+1, enabling us to reproduce the right hand side of the proof, which was the objective all along.
You will encounter index shifts in differential equations. In particular, you will need index shifts when finding series solutions to differential equations.
At 11:55, Ron Joniak mentions Pascal's rule. Pascal's rule is the following equation:
C(n+1,k)=C(n,k-1) +C(n,k). Assume that we have a set A={0,1,2,3,.....,n}. Then our set has n+1 elements (including the zero gives it an additional element), so the number of k element subsets in A can be represented as C(n+1,k) (note, if A={1,2,3...n}, then it would have n elements and it could be represented as C(n,k)). Another way to think about C(n+1,k) is that we are choosing k elements from a set with n+1 elements. For example, C(3,1) means that we are choosing one element from a set with 3 total elements).
P.S. Also, for the sake of curiosity, if we wanted to put C(n+1,k) into equation form then we would get C(n+1,k)= (n+1)!/(k!(n+1-k)!). However, this is not needed for the proof, as it is unnecessary.
Now, Pascal's rule states that "the number of k element subsets in A is equal to the number of k element subsets that contain zero plus the number of k element subsets that do not contain zero."(Hammack, Book of Proof, pg 78).
Please note that I used the form C(n+1,k)=C(n,k-1) +C(n,k) to illustrate Pascal's rule. In the video, the author uses a different form, but the two forms are just different ways of expressing the exact same idea; in this post, the form I used is easier to write via a keyboard, so my apologies for any inconvenience.