For more information, please see full course syllabus of Math Analysis

For more information, please see full course syllabus of Math Analysis

## Discussion

## Study Guides

## Download Lecture Slides

## Table of Contents

## Transcription

## Related Books

### The Binomial Theorem

- A
*binomial*is an expression that has__two terms__:a+b. - The
*binomial theorem*tells us what happens when we raise a+b to some arbitrary power n: (a+b)^{n}. - Notice that when we expand (a+b)
^{n}, it will always come out in the form

We call each of the blanks aa ^{n}+ a^{n−1}b + a^{n−2}b^{2}+ …+ a^{2}b^{n−2}+ a b^{n−1}+ b^{n}.*binomial coefficient*since they are the coefficients of the binomial expansion. -
__Binomial theorem:__When expanding (a+b)^{n}, the coefficient of the term a^{n−k}b^{k}is

[Remember, (n || k) is spoken as `n choose k'. We can also write it as⎛

⎝n

k⎞

⎠

= n! (n−k)!·k!

. _{n}C_{k}or C(n,k). We first learned about it in the lesson*Permutations and Combinations*. Also remember, `!' means `factorial': the value we get when we multiply a number by all the positive integers below it: 5! = 5·4 ·3 ·2 ·1. We define 0! = 1 for ease and other fiddly reasons.] - We can also find the binomial coefficients with
*Pascal's triangle*. We start with a 1 at the very top of the triangle for n=0, then each row below is created by diagonal addition. [This idea is hard to explain with words but makes a lot more sense in pictures. Check out the video for a diagram of what's going on and how to use it.] - If you're interested, this lesson has a proof of the binomial theorem at the end. Don't worry about watching it if you don't want to, but if you do, great! Working through proofs like this is good experience if you're interested in eventually studying higher mathematics.

### The Binomial Theorem

Lecture Slides are screen-captured images of important points in the lecture. Students can download and print out these lecture slide images to do practice problems as well as take notes while watching the lecture.

- Intro
- Introduction
- Understanding Binomial Coefficients
- The Binomial Theorem
- Proof of the Binomial Theorem
- Pascal's Triangle
- Pascal's Triangle, cont.
- Diagonal Addition of Terms
- Zeroth Row
- First Row
- Why Do We Care About Pascal's Triangle?
- Pascal's Triangle, Example
- Example 1
- Example 2
- Example 3
- Example 4
- Example 5
- Time for the Fireworks!
- Proof of the Binomial Theorem
- Proof, Base Case
- Proof, Inductive Step - Notation Discussion
- Proof, Inductive Step - Setting Up
- Proof, Inductive Step - Start
- Proof, Inductive Step - Middle
- Proof, Inductive Step - Checking In
- Proof, Inductive Step - Lemma
- Proof, Inductive Step - Nearly There
- Proof, Inductive Step - End!

- Intro 0:00
- Introduction 0:06
- We've Learned That a Binomial Is An Expression That Has Two Terms
- Understanding Binomial Coefficients 1:20
- Things We Notice
- What Goes In the Blanks?
- Each Blank is Called a Binomial Coefficient
- The Binomial Theorem 6:38
- Example
- The Binomial Theorem, cont.
- We Can Also Write This Expression Compactly Using Sigma Notation
- Proof of the Binomial Theorem 13:22
- Proving the Binomial Theorem Is Within Our Reach
- Pascal's Triangle 15:12
- Pascal's Triangle, cont.
- Diagonal Addition of Terms
- Zeroth Row
- First Row
- Why Do We Care About Pascal's Triangle?
- Pascal's Triangle, Example
- Example 1 21:26
- Example 2 24:34
- Example 3 28:34
- Example 4 32:28
- Example 5 37:12
- Time for the Fireworks! 43:38
- Proof of the Binomial Theorem 43:44
- We'll Prove This By Induction
- Proof (By Induction)
- Proof, Base Case 47:00
- Proof, Inductive Step - Notation Discussion 49:22
- Induction Step
- Proof, Inductive Step - Setting Up 52:26
- Induction Hypothesis
- What We What To Show
- Proof, Inductive Step - Start 54:18
- Proof, Inductive Step - Middle 55:38
- Expand Sigma Notations
- Proof, Inductive Step - Middle, cont.
- Proof, Inductive Step - Checking In 1:01:08
- Let's Check In With Our Original Goal
- Want to Show
- Lemma - A Mini Theorem
- Proof, Inductive Step - Lemma 1:02:52
- Proof of Lemma: Let's Investigate the Left Side
- Proof, Inductive Step - Nearly There 1:07:54
- Proof, Inductive Step - End! 1:09:18
- Proof, Inductive Step - End!, cont.

### Math Analysis Online

### Transcription: The Binomial Theorem

*Hi--welcome back to Educator.com.*0000

*Today, we are going to talk about the binomial theorem.*0002

*Long ago, when we studied polynomials, we learned that a binomial is an expression that has two terms.*0005

*For example, each of the below is a binomial, because it has two separate terms:*0011

*x + 7; 2l ^{3} - 5; 3y^{2} + √2z.*0015

*A binomial is anything that we can put in the form a + b, some a and some b.*0023

*All we are looking for to be a binomial is just having two terms.*0028

*What if we wanted to see what happens if we raise a binomial to some power?*0032

*If it was small, like (a + b) ^{2}, we could FOIL it; we could put one factor next to another factor,*0036

*and then we would just multiply them out by distribution and just work it out.*0041

*We are used to doing that; we have been doing that for years--it wouldn't be that difficult.*0044

*But what if it was really large, like (a + b) ^{7}, or even larger?*0047

*We could do it by just putting all of the factors out, but it is going to get really big and really messy really fast.*0052

*It is not going to be easy for us to multiply out (a + b) ^{7}, and it would be even worse if it was a larger value than 7.*0057

*So, in this lesson, we are going to learn how to expand a binomial for any arbitrary power n.*0064

*If we have any integer n, we will be able to use this to figure out how to expand (a + b) raised to the n.*0068

*To help us understand what we are working with, let's look at (a + b) ^{n} expanded for various values of n.*0076

*(a + b) ^{0} will just come out to be 1, because if you raise anything to the 0, you get 1.*0082

*(a + b) ^{1} comes out to be a + b; (a + b)^{2} would come out as a^{2} + 2ab + b^{2}.*0087

*(a + b) ^{3} would be a^{3} + 3a^{2}b + 3ab^{2} + b^{3}.*0094

*(a + b) ^{4} equals a^{4} + 4a^{3}b + 6a^{2}b^{2} + 4ab^{3} + b^{4}.*0100

*And (a + b) ^{5} would equal a^{5} + 5a^{4}b + 10a^{3}b^{2} + 10a^{2}b^{3} + 5ab^{4} + b^{5}.*0106

*We could keep going in this way; but we are starting to see a pattern at this point.*0115

*We can realize that there is a pattern going on, and we can use this pattern to let us figure out general things about a + b, to just any n whatsoever.*0118

*Let's look specifically at (a + b) ^{4} and (a + b)^{5} above*0127

*to help us see some properties about how binomials work.*0131

*We will be able to talk about (a + b) ^{n}, the general expansion of a binomial, by looking at these in specific.*0134

*So, looking at these two as stand-ins for the general way that (a + b) ^{n} expands, we notice various things.*0142

*The first thing is that the expansion of (a + b) ^{n} has n + 1 terms.*0149

*What I mean here is that (a + b) ^{4}--well, that would be n = 4;*0153

*we count how many terms come out in the expansion: 1, 2, 3, 4, 5: there are 5 terms total.*0157

*We started with n = 4; 4 + 1, n + 1, gets us 5; so we have 5 terms coming out of it.*0165

*The same thing happens with (a + b) ^{5}; we have 1, 2, 3, 4, 5, 6 terms total: 5 + 1 is 6 terms.*0174

*So, we end up getting n + 1 as the number of terms that come out.*0183

*The expression also has symmetry; powers of a decrease by 1 each step, every time we move forward a term, while powers of b will increase by 1.*0188

*If we have (a + b) ^{4}, for example, we start at a^{4}, because (a + b)^{4}...*0198

*well, the largest kind of a that it will be able to produce (largest in the sense that it will have the largest exponent) will be a ^{4}.*0203

*We manage to get a ^{4} out of it; and then the next one--we will end up having a^{3}*0210

*(it has just stepped down 1), and then the next term would be a ^{2} (step down again), a (step down again),*0214

*and finally it turns blank; and a blank is another way of saying a ^{0}, because a^{0} is just 1, so it disappears.*0219

*The same thing happens with the b's, except that it does the reverse process.*0227

*It increases; since it is blank, it doesn't appear here; that is b ^{0}, and then we have b^{1};*0230

*and then b ^{2}, and then b^{3}, and then finally b^{4}.*0235

*Our a's are decreasing by 1 each step, at the same time that our b's are increasing.*0240

*a starts at n; b starts at 0; and then click, click, click, click, click, click...until finally a is at 0 and b is at n,*0245

*and we have finished their expansion in terms of the a and b exponents.*0253

*The sum of the powers for each term comes out to be n.*0258

*Here, our n is 4; if we grab any term inside of this...we will end up seeing a ^{3}b^{1}:*0261

*if we add up the powers on these terms, 3 + 1 gets us 4.*0268

*If we grab another one, like a ^{2}b^{2}, 2 + 2 gets us 4.*0272

*Even at the extremes...a ^{0} and b^{4}: well, 4 + 0 gets us 4.*0276

*This ends up happening with (a + b) ^{5}, as well; if we grab any one of the terms here...*0283

*this is a 4; this is a 1; 4 + 1 gets us 5; so if we add the powers, we always end up getting n.*0288

*Whatever our (a + b) ^{n} is, adding the powers of the a and the b will always come out to be equal to the value of n.*0295

*And finally, the coefficients vary symmetrically; there is symmetry in how the coefficients are.*0305

*If we start in the middle, there is a 6 here by itself, because it is in the very middle, so it can't be symmetric with anything else.*0310

*And then, we have 4's matching on either side, and then we have 1's (effectively, the coefficient here is a 1,*0316

*because it doesn't appear at all, so its coefficient is 1); and the 1's match on either side, as well.*0323

*The same thing here: the 10's match, and the 5's match, and the invisible 1's match.*0328

*All right, so we end up seeing that the coefficients vary symmetrically; great.*0339

*With all of these ideas in mind, these properties, we see that any expansion of a binomial, (a + b) ^{n},*0344

*is going to have this form of a ^{n}, a^{n - 1}, a^{n - 2},*0351

*until we finally work down to a ^{2}, a, and then just a^{0} in here.*0356

*And we reverse that with the b's; we have b ^{0} at the beginning, and then it works up:*0362

*b ^{1}, b^{2}, working up...b^{n - 2}, b^{n - 1}, and b^{n}, finally.*0366

*So, we are always going to have this form; the only question is what goes in the blanks in front of it.*0372

*We call these blanks binomial coefficients, because they are the coefficients of the binomial expansion.*0377

*They are the number multiplying against that binomial having been expanded--*0383

*each one of the coefficients for the expansion of some a, some b, and powers on those a's and b's.*0388

*The only question we have at this point is what those coefficients will be.*0393

*We get this with the binomial theorem; if we want to know the binomial coefficients of some binomial expansion, we can use the binomial theorem.*0398

*The binomial theorem says that expanding some (a + b) ^{n}, the coefficient of the term a^{n - k}b^{k}*0405

*will be n choose k (and n choose k is just the same thing as n! over (n - k)! times k!)...remember, we talked about this n choose k,*0414

*this parentheses with the values n and k above each other; this is n choose k--we have talked about this before...*0426

*You can also write it as nCk, or c of n,k; but we still pronounce all of these spoken aloud the same way: "n choose k."*0434

*We first learned about this idea in the lesson Permutations and Combinations.*0443

*So, if you really want a lot more experience with how that works, you can go and look that up.*0447

*But really, we have enough, just for what we are looking for here, from what we will be able to get in just this lesson.*0450

*Also, remember: the exclamation mark means factorial, and factorial is the value that we get*0455

*when we multiply a number by all of the positive integers below it.*0460

*For example, 5! is equal to 5 times 4 times 3 times 2 times 1; we multiply those all together, and we get the value of 5!.*0464

*Finally, we define 0! as equal to 1; we just say 0! = 1; that is the end of the story, because it will help us out.*0473

*It makes things easier, and there are also some other reasons that we don't really need to go into.*0480

*You have to memorize that 0! = 1; that is just that.*0484

*All right, let's see the binomial theorem get used in an example, so we can see how it works.*0488

*For any (a + b) ^{n}, the coefficient of the a^{n - k}b^{k} term is n choose k*0493

*(which is the same thing as saying n!/(n - k)!(k!)).*0501

*For example, if we had (a + b) ^{7}, and we wanted to know the term containing a^{2}b^{5},*0506

*when expanded; that is going to show up, because 2 + 5 is 7;*0512

*so we know that a ^{2}b^{5} will show up in the expansion.*0516

*We could figure out what the term would be with the binomial theorem.*0520

*We know that it is going to be n choose k; so the only thing that we have to do is figure out what our n is;*0523

*well, it is (a + b) ^{7}, so it means that n = 7.*0527

*What is our k? Well, it is b ^{5}, so our k equals 5.*0530

*a ^{n - k}, b^{k}...we can also check, because it is n - k here, and this is 2;*0535

*well, if we take 7 - 5, sure enough, we get 2, which is this value right here.*0542

*So, it checks out; we are following the method of the binomial theorem.*0551

*We see how the binomial theorem works: we have a ^{7 - 5} times b^{5}; that is a^{2}b^{5}.*0555

*We know that the coefficient is going to be n choose k; our n is 7; our k is 5; so we have 7 choose 5.*0562

*That expands to 7!/2!(5!) times a ^{2}b^{5}.*0570

*And that will simplify to 21 times a ^{2}b^{5}; so we have been able to figure out what the coefficient is,*0577

*what the term would look like when it is fully expanded: we get 21a ^{2}b^{5}.*0583

*If you are not quite sure how we get the value of 21 out of that, we can figure it out,*0587

*because 7 choose 5...well, we wrote here already that that would be 7! divided by 7 - 5 (that is 2), factorial, times 5!.*0590

*7! is the same thing as 7 times 6 times 5 times 4 times 3 times 2 times 1.*0603

*We can also write 5 times 4 times 3 times 2 times 1 as just 5!.*0610

*And now we have things we can cancel out; 2! is just 2 times 1, so we can just leave that as 2; so it is 2 times 5!.*0614

*We have 5! and 5!; they cancel out; 7 times 6 over 2...6 cancels into 3 times 2, so our 2's cancel out; we have 7 times 3, or 21;*0620

*and that is how we end up getting the 21 for our coefficient.*0631

*And we know it will be a ^{2}b^{5}, because we figured out that it was the coefficient of the a^{2}b^{5} term.*0634

*Great; at this point, we can now know the coefficient of any term, which means that we can expand (a + b) ^{n} with relative ease.*0640

*(a + b) ^{n} will end up being n choose 0 a^{n}, because it is a^{k} of 0 there,*0649

*because b hasn't even shown up, so it is b ^{0}.*0654

*And then, next we would have n choose 1: a ^{n - 1}b^{1}; our k there is 1.*0657

*Next, we would have n choose 2 times a ^{n - 2}b^{2}.*0663

*And we would continue on in this fashion, until we have n choose n - 2; n minus (n - 2) comes out to be +2;*0668

*the minus on the -2 becomes positive when we get just +2 on our a; and k is n - 2 b ^{n - 2}.*0677

*n choose n - 1: ab ^{n - 1}; and finally, n choose n: it is now a^{n - n}, or a^{0}, so it just disappears; and b^{n}.*0684

*We can now expand out the whole thing with relative ease.*0695

*It will definitely still take some effort; we will have to figure out what each of these "choose" values comes out to be.*0698

*But we can write the whole thing out, expanded, and we will be able to get it out.*0702

*And it will still be easier than doing each term, and then multiplying (a + b) and (a + b) and (a + b) and (a + b), and trying to FOIL the whole thing.*0705

*Expanding factors like that would just be a real pain, if it was a large thing, like (a + b) ^{10}.*0713

*So, this is really useful if we are trying to expand a very large exponent, n.*0718

*Also, we can condense this in a really nice way.*0723

*This is a monster of an expansion; it would be a pain if we had to write this repeatedly.*0726

*We can use sigma (or summation) notation to condense this into a much smaller thing.*0729

*(a + b) ^{n} is equal to the sum of k = 0 to n of n choose k times a^{n - k}b^{k}.*0735

*If you want to check and make sure that that works--well, if we plug in k = 0, sure enough, we end up getting this term.*0744

*n choose 0: a ^{n - 0} is a^{n}; b^{0} just disappears, so we end up getting that.*0750

*And we work all the way through; here would be k = n; n choose n; a ^{n - n}b^{n}; we end up getting n choose n b^{n}.*0757

*And we end up seeing all of the terms here show up; there would be k = 1, k = 2, k = 3 next, k = 4...until we finally get to k = n - 2, k = n - 1, k = n.*0766

*We can write the whole thing with sigma/summation notation.*0778

*If this is really confusing, if you really haven't done much work with sigma/summation notation,*0780

*remember to check out the lesson Introduction to Series; we will talk about this.*0785

*We will have a much better understanding of sigma/summation notation (that is a mouthful) and how it works through.*0788

*So, make sure that you check out that lesson if this is really confusing and you have to use it.*0796

*Proof of the binomial theorem: Proving the binomial theorem is within our reach.*0802

*We could prove this; it is quite challenging, but it is an interesting proof.*0806

*And it will give us the chance to try out our shiny new proof-by-induction.*0810

*We will use proof by induction to prove this thing.*0814

*Working through it will really deepen our understanding of how mathematics works.*0816

*We will get a much better understanding of how some really complicated stuff in math works, by just working through it.*0819

*However, proving it won't directly help us see how to use the theorem.*0825

*If we work through it, it won't directly help us in any way for the kind of problems that you are likely to have to work on right now.*0830

*It will help us understand why the theorem works, but it is not likely to actually make anything easier that we actually have to do in class.*0836

*As such, the proof for the binomial theorem is in this lesson; it is here; but it is at the end, after the examples.*0843

*If you are interested, I encourage you to go ahead and check it out; it is some cool stuff.*0852

*You will get the chance to really flex your math muscles.*0855

*We are basically going to be looking at a college-level proof.*0858

*But I believe that, if you are interested in this sort of thing, and you put a little bit of effort*0860

*into watching it and working through it, you will totally be able to understand it.*0863

*So, if you are interested in this kind of math, go ahead and check it out; it is a really cool thing.*0867

*We will spend a while working through it and explaining it carefully.*0870

*But at the same time, if you are busy, or you don't really care--you are not that interested in math--*0873

*you are just working through this so that you can get a grade in your class, well, I would like for you to be interested in math;*0877

*but I am not going to be able to always make you interested in math.*0882

*So, I just want you to do well; but to be honest, you don't actually have to understand how this proof works*0884

*to do well in a math class at this level, or even in the next level.*0888

*This is more something for if you think you might be really interested in serious math or serious-level science courses.*0891

*You probably want to check this out; but that is still even going to be a couple of years away, if you are currently in a precalculus class like this.*0896

*All right, so check it out if you are interested; but if you are not, don't worry about it.*0903

*Pascal's triangle: we can arrange the binomial coefficients in a triangular pattern to make a thing called Pascal's triangle.*0907

*It is named after one of the people to have found it and discovered it.*0914

*We can have n = 0 as our first row (well, the 0 ^{th} row, we will call it), n = 1 as the next row (the first row),*0917

*n = 2 as the next row (what we will call the second row), n = 3, n = 4, and so on, and so on.*0925

*Notice: we have our n value at the top each time; so it is n = 0 and then n = 1, n = 2, n = 3, and so on and so on...*0930

*And then, we always have 0, and then 0, 1, 0, 1, 2, 0, 1, 2, 3...until it finally ends up having the number on top match the number on bottom.*0940

*And that is how we end up making the triangle.*0952

*Why is this interesting? We are going to see a really interesting pattern emerge when we replace each n choose k,*0954

*each of these like this, with what the value is that ends up coming out of it.*0961

*What does 2 choose 0 come out to be? We replace it, and we start to see a pattern emerge.*0965

*We replace it, and we end up getting this: n = 0 gets 1 for its row; n = 1 gets 1 and 1; n = 2 gets 1 2 1.*0970

*n = 3 is 1 3 3 1; n = 4 is 1 4 6 4 1; you might have seen this before.*0978

*Notice how each row can be created from the row above through diagonal addition of the terms.*0983

*For example, if we go out from n = 0, and we go out diagonally left and diagonally right,*0989

*1 added down would end up getting us 1 and 1.*0995

*Then, if we add diagonally again, down left, down right, and then the same thing for the other one--*0999

*down left and down right, well, 1 +...only by itself would come out as 1.*1005

*1 + 1 would get us 2; it is this one and this one, combined together, because it has both of the diagonals coming in through here.*1009

*And then, 1 only on itself would get us 1 here.*1018

*And we can keep going along with this pattern: 1 diagonally out, 2 diagonally out, 1 diagonally out...1 just by itself would get 1;*1020

*1 + 2 would get us 3; 2 + 1 would get us 3; 1 by itself would get us 1.*1028

*And we can keep going in this pattern: 1 on itself would get 1; 1 on 3 is 4; 3 on 3 is 6; 3 on 1 is 4; 1 by itself is 1.*1033

*So, by doing this, we can extend the triangle down to whatever value of n we are interested in considering.*1045

*Whatever value of n we are interested in considering, we can just get to by diagonal addition of terms.*1052

*For example, if we are interested in knowing what n = 5 is, then we just expand out diagonally like this, through diagonal addition.*1058

*And we can work it out: 1 added to itself just gets 1; 1 added to 4 gets us 5; 4 added to 6 gets us 10;*1066

*6 added to 4 gets us 10; 4 added to 1 gets us 5; 1 added to itself gets us 1.*1073

*And we have been able to create the row n = 5, the fifth row.*1079

*Since the first row is based off of n = 0, it is called the 0 ^{th} row.*1084

*So, here is the 0 ^{th} row; this will help keep us from having confusion later on.*1089

*The next row is called the first row, because it is based off of n = 1; so here is the first row.*1094

*We might think that the first row would be the one on top, but not with Pascal's triangle,*1101

*because it is really based off of n = 0, and then n = 1.*1104

*So, the second row would be the one connected to n = 2.*1109

*It is based on the number of the n, not the actual location of the row, so much as if you were just counting location of rows.*1114

*It is based on the n that it is connected to: n = 4 would produce the fourth row, and so on and so forth.*1121

*Why do we care about Pascal's triangle--why is this thing useful?*1128

*Because the n ^{th} row gives the coefficients to expanding (a + b)^{n}.*1131

*The way that we set this up in the first place was by using those binomial coefficients.*1138

*Remember: all of those binomial coefficients, the n choose k--we had that set up based off of which n we were on.*1142

*So, what we did was put down all of the binomial coefficients for a given n value,*1148

*which means what (a + b) ^{n} is...we have just talked about all of the coefficients for expanding some (a + b)^{n}.*1152

*It is really handy, if we have to expand the entire thing.*1159

*For example, since the n ^{th} row gives the coefficients*1162

*to expanding (a + b) ^{n}, we can expand (x + y)^{4} using the triangle.*1164

*If it is (x + y) ^{4}, then that means we are dealing with n = 4; so we care about this row of the triangle.*1169

*We work this out, and that means that it is going to be (x + y) ^{4}.*1176

*Well, we know that it is going to be some blank, and it will start with x ^{4}y^{0}...*1179

*plus _x ^{3}y^{1} (y goes up by 1; x goes down by 1) + _x^{2}y^{2}*1184

*+ _x ^{1}y^{3} + _x^{0}y^{4}.*1194

*At this point, we can now plug in each of our binomial coefficients: 1 will go here; 4 here; 6 here; 4 here; 1 here.*1202

*And we can also write the thing a little bit more simply.*1213

*1x ^{4}y^{0}: well, 1...we normally don't write a coefficient of 1; so we can just write this as x^{4},*1215

*because y ^{0} also just turns into a 1, and we don't normally write out the 1's.*1221

*x ^{4} + 4x^{3}y^{1}...we normally just write that as y, so we can write that like that;*1225

*plus 6x ^{2}y^{2} + 4x^{1} (we normally just write it as x) y^{3},*1232

*plus 1x ^{0}...well, we normally don't write 1's; x^{0} just becomes 1, so it will disappear as well;*1239

*and we are left with just y ^{4}; so we end up being able to expand all of (x + y)^{4},*1247

*using Pascal's triangle, which tells us the binomial coefficients for the associated n row.*1252

*We can use that triangle, and we can expand things pretty easily.*1259

*If we had tried to expand (x + y) ^{4} by hand, we would probably still be doing it.*1262

*It takes a while; and this was even through explaining it.*1266

*If we were just punching it out, we would be able to do this really quickly.*1270

*So, Pascal's triangle is really useful for when we have to expand some binomial quickly and easily, without having to take a whole bunch of time--pretty useful.*1273

*All right, we are ready for some examples.*1282

*Use the binomial theorem to give the coefficients for the term containing s ^{4}t^{7} from (s + t)^{11}.*1283

*The first thing that we want to identify is what the n we are working with is.*1291

*The n that we are working with is 11.*1294

*All we care about is s ^{4}t^{7}; we are asked to find the binomial coefficient for that term when we expand (s + t)^{11}.*1297

*We don't really care about all of the other terms; all we really care about is s ^{4}t^{7}.*1308

*What is that going to be? That is going to end up being some n choose k.*1312

*And if we wanted to have that, it would also be s ^{4}t^{7}.*1318

*So really, at this point, all that we need to find is what k is.*1321

*k is what? Well, it is normally...from the binomial theorem, we would have n choose k; a ^{n - k}b^{k}.*1325

*So, in this case, we have n choose k, but we are not using a and b; we are using s and t.*1338

*So, it will be s ^{n - k}t^{k}; what is our n?*1346

*We have 11 choose k, times s ^{11 - k}t^{k}.*1351

*Well, if we have t ^{7} and s^{4}, then it must be that k has to be equal to 7.*1358

*11 - 7 gets us 4, and k = 7 gets us t ^{7}.*1368

*So, we now know what k is; we now know what n is; so we can plug this in.*1373

*We have 11 choose 7, times s ^{4}t^{7}; that will be the s^{4}t^{7} term.*1376

*What comes out to be 11 choose 7? Let's go do that in a sidebar.*1383

*11 choose 7: well, that is going to be 11! over (11 - 7), 4, factorial, times 7!.*1386

*11!...well, we can write that as 11 times 10 times 9 times 8 times 7....*1398

*But we can also just write it as times 7! now; that is convenient, because we have 7! on the bottom.*1405

*So, 4! times 7!...we cancel out the 7!'s, and we have 11 times 10 times 9 times 8.*1410

*On the bottom, we can expand 4! as 4 times 3 times 2 times 1.*1419

*We will just leave the 1 off; 2 and 4 become 8, which cancels the 8 on top; 3 cancels with part of the 3 of the 9,*1424

*so we have times 3, because we cancel out one of the 3's from the 9.*1431

*11 times 10 times 3 comes out to be 330; 330 is our coefficient, so we get 330 times s ^{4}t^{7}.*1434

*That is what we get as the coefficient of the term containing s ^{4}t^{7}.*1446

*The coefficient is just the 330 part, and the whole term would be 330 times s ^{4}t^{7}, when we expand (s + t)^{11}.*1450

*Now, could you imagine how difficult that would be to do by hand?*1460

*That would be practically impossible for us to do by hand, because it would take so much time and effort.*1462

*But by using this n choose k business, we are able to figure out what the coefficient is relatively easily.*1467

*Use the binomial theorem to give the coefficient for the term containing x ^{10}y^{12} from (x^{2} + y^{3})^{9}.*1473

*The first thing that I want to point out: x ^{10}y^{12}: well, what we talked about before was:*1480

*if you take the exponents, and you add them together, well, what is our n?*1486

*Our n here is n = 9; but if we add 10 and 12 together, 10 + 12 is 22; what?*1491

*Wait, that doesn't make sense; what is going on here?*1500

*The issue isn't that it is x ^{10}y^{12}, because what we really have is a and b.*1502

*But what is our a and b? Our a and b are x ^{2} and y^{3}; a = x^{2}; b = y^{3}.*1508

*So, it is (a + b) ^{9}; so when we expand this out, what we are looking at is n choose k on a^{n - k}b^{k}.*1518

*But now we have called out a and b as x ^{2} and y^{3}, because that is what the actual two terms of it are.*1535

*It is not just x, and it is not just y; it is x ^{2} and y^{3}.*1541

*So, we have some n choose k; we will plug those in later.*1546

*And so, it is x ^{2} to the n - k, and b--what is b?--b is y^{3}, to the k.*1549

*So now, we need to figure out what value k has to be for us to be able to get x ^{10}y^{12}.*1561

*Well, if we have y ^{3} to the k, and we know that that ends up being the same thing as y^{12},*1569

*well, then k has to be equal to 4, because (y ^{3})^{4} would be 3 times 4, so y^{12}.*1577

*So, we end up getting y ^{12} from setting k equal to 4.*1584

*And similarly, 9 minus 4, since it is a ^{n - k} here...9, our n value here, minus 4, our k value here, would get us 5 for n - k.*1587

*And x ^{2} to the fifth does come out to be x^{10}; 2 times 5 is 10.*1601

*At this point, we now see what our k is; our k is 4; our n is 9; so we can plug those in.*1607

*And what we are looking at is 9 choose 4, times x ^{2} to the n - k, so in this case 5, y^{3}, to the fourth.*1615

*So, that is x ^{2} to the 5; that does become n; y^{3} to the fourth does become 12.*1630

*And 5 and 4 put together do become 9; so everything checks out--this makes sense.*1635

*At this point, we only need to figure out what 9 choose 4 is.*1639

*9! over (9 - 4), the top minus the bottom, that is 5, factorial, times just the bottom, factorial:*1643

*9!--we can write that as 9 times 8 times 7 times 6 times 5!, over 5!; look, that is convenient; they cancel;*1653

*times 4; and now let's expand 4!, as well: 4 times 3 times 2...we will omit the 1, because it doesn't do anything.*1663

*5! and 5! cancel; 3 and 2 cancel out the 6; 8 cancels with a 4 to make a 2 on top.*1670

*So, we have 9 times 2 times 7; 9 times 2 times 7 comes out to be 126.*1677

*There is our coefficient right there; or if we wanted to write out the whole thing, we would end up getting 126,*1684

*times x...not to the fifth; not squared; but x ^{10}, what it was, because it said the term containing*1690

*x ^{10}y^{12}, not the one where we have raised that part of the binomial to the fifth, but x^{10}y^{12}.*1696

*And what it asked for was the coefficient; the coefficient is 126; times x ^{10}y^{12}.*1704

*Great; the third example: Find the value of the coefficient c on the term cx ^{8} in the expansion of (2x^{2} - 3)^{7}.*1711

*Once again, we need to realize that this is 8, but what we have is an n = 7.*1720

*So, we realize that it is 2x ^{2}; that is the thing we are dealing with.*1728

*So, we have a = 2x ^{2}, and b equals...not just 3, but it has to be including the negative as well,*1732

*because normally it is a + b; so if it is a + b normally, but now it is a - b, then it must be that the b also has a negative inside of it.*1743

*So, our b is equal to -3; OK.*1751

*At this point, we want to figure out what number we have to raise 2x ^{2} to, to get x^{8} to pop out of that.*1754

*What number do we raise that to? If we have x ^{2} (we will consider just the x^{2} for a moment,*1764

*because the 2 won't affect what exponent the x has) to the ?, is equal to x ^{8};*1771

*well, then our question mark has to be 4, because 2 times 4 comes out to be 8.*1781

*So, x ^{2}, raised to the 4, equals x^{8}.*1786

*We know that whenever we do this expansion, n choose k, times 2x ^{2}, our whole a, to the n - k,*1791

*times our whole b, -3, to the k; now we need to figure out what our k is.*1801

*Well, our n was 7, so our k must be 3, if we are going to produce a 4 there.*1807

*n - k has to be 4, because we know that this value here has to match up with n - k here.*1815

*n - k there has to match up, as well; so our 7 is what we have for n; 7 - k = 4; 7 - k = 4 means that k has to be 3.*1823

*Now, we have figured out that k has to be 3; we are ready to plug everything in.*1834

*n choose k: 7 choose 3, times 2x ^{2} to the n - k (comes out to be 4); -3 to the 3.*1839

*n - k at 4...2x ^{2} to the fourth; sure enough, that would make some constant times x^{8}.*1855

*-3 to the 3: that is just going to also be part of that constant term, c.*1862

*At this point, let's figure out what it is; let's solve 7 choose 3; what does that value come out to be?*1866

*7! over (7 - 3), 4, factorial, times 3!...we have 7 times 5 times 6...sorry, 7 times 6 times 5; I'm not sure why I confused that order;*1872

*it doesn't matter, but I don't want to make you think that something weird happened;*1885

*7 times 6 times 5, over 4!, cancelled out with all of the rest of those...we have 3! on the bottom; that is just 3 times 2 times 1.*1888

*We will omit that; 3 times 2 cancels out with the 6; 7 times 5 gets us 35.*1895

*We can now swap that in for our 7 choose 3, and we have 35 times...*1900

*2x ^{2} becomes 2 to the fourth, x^{2} to the fourth; 2^{4} is 16; x^{2} is x^{8}.*1905

*-3 cubed is -27 (-3 times -3 times -3); we use a calculator to multiply 35, 16, and -27, and we get -15,120x ^{8}.*1913

*That means that our c must be equal to -15,120, because what we are looking for*1930

*was the coefficient c on the expansion of cx ^{8}, once the thing is fully expanded.*1937

*All right, great; we are ready to move on to Pascal's triangle, the fourth example.*1943

*Use Pascal's triangle to expand (p - q) ^{6}.*1947

*If we are going to the sixth, then that means n = 6; we are going to have to get down to the sixth row,*1951

*which is really the row that is 7 down (if we say that the row at the very top is one down); but we will just write n = 0,*1956

*so we don't get confused by this; so our 0 ^{th} is at a 1, and then n = 1 is the next one: 1 1;*1965

*n = 2: 1 2 1; n = 3: 1 3 3 1; n = 4: 1 4 6 4 1; n = 5: 1...1 + 4 is 5...4 + 6 is 10; 6 + 4 is 10; 4 + 1 is 5; 1 on itself is 1.*1975

*And finally, the one we care about, n = 6: 1 on itself is 1; 1 + 5 is 6; 5 + 10 is 15; 10 + 10 is 20; 10 + 5 is 15; 5 + 1 is 6; 1 on itself is 1.*1999

*Those are all of the coefficients that we care about at this expansion.*2011

*All right, if we are going to expand (p - q) ^{6}, we know that it is going to end up having some expansion*2016

*that looks like blank, this one first...well, this one is p; and this one, though, is actually -q; so it is going to be _p ^{6}*2023

*times (-q) ^{0}; and then we work the q part up and the p part down, one step at a time:*2037

*p ^{6} becomes p^{5} on our next step; (-q)^{0} becomes (-q)^{1};*2045

*plus _p ^{4}(-q)^{2}...and just continue on the next line...+ p^{3} times (-q)^{3}...*2050

*oh, there should be a blank after that plus, right here; + _p ^{2}(-q)^{4} +*2064

*(I will just bring this down to the next line, once again) _p ^{1}(-q)^{5} +*2077

*_p ^{0}(-q)^{6}; great--at this point, we can now swap in our values for our binomial coefficients.*2086

*So, we know 1 will go here; a 6 will go here; a 15 will go here; a 20 will go here; a 15 will go here; a 6 will go here; a 1 will go here.*2094

*See how they come in symmetrically?*2108

*At this point, we will now write it all on this line around here.*2110

*And we will also simplify it: 1p ^{6}(-q)^{0}: well, 1 just disappears;*2115

*we have p ^{6}; and (-q)^{0}--well, if you raise anything to the 0,*2120

*it just becomes 1; so we will have that disappear, as well.*2124

*6p ^{5}(-q)^{1}: well, that -q is going to show up now; it is going to come in.*2126

*So, it is not plus; it is now minus, because it is -q to the 1; so - 6p ^{5}q.*2132

*That -q here doesn't get cancelled out, because there is just one negative.*2141

*And next, we will have + 15p ^{4}(-q)^{2}; negative on negative cancels out, so we do have positive q^{2}.*2145

*Plus 20p ^{3}(-q)^{3}; negative, negative, negative means we still have a negative.*2156

*So, it is not a plus; it is a minus, because of the (-q) ^{3}.*2167

*So, we have q ^{3}; next, plus 15...that was the last one...this is what we are working on now:*2171

*15p ^{2}(-q)^{4}: well, the negatives will end up canceling there, because it is an even number, q^{4}.*2179

*Plus 6p ^{1}(-q)^{5}; well, (-q)^{5} is an odd, so it will be minus 6pq^{5}.*2186

*And then finally, (-q) ^{6}, with a coefficient of 1, is our very last term.*2196

*We just did this one here as our last term: 1p ^{0}...those things both disappear, and we have +q^{6}.*2201

*And the negative disappears, because it has an even exponent; great.*2207

*And there is our full expansion; it is still not super fast, but it is much, much better than if we had tried to expand that whole thing out by hand.*2212

*If we did that whole thing by hand, it would be taking forever; but this goes relatively quickly, by using Pascal's triangle.*2221

*The final example: Use Pascal's triangle to expand (√3u ^{2} + 1/2√p)^{4}.*2227

*At this point, what is our n? Our n equals 4, so we need to get down to the n = 4 row.*2235

*We start at n = 0: 1; n = 1: 1 1; n = 2: 1 2 1; n = 3: 1 3 3 1; n = 4 (finally, the row that we actually care about): 1 4 6 (3 + 3 is 6); 3 + 1 is 4; and 1.*2241

*Great; so that is the row that we will actually end up using, because our n equals 4.*2264

*So that we don't end up getting cramped, I am not going to end up writing here.*2268

*I am going to end up doing the expansion down here.*2271

*Our first thing will be some blank, times...well, what is our a?*2275

*That is the good thing to identify: √3u ^{2} is what our a is equal to; a + b to the some n...*2279

*so in this case, the a is all of √3u ^{2}, and the b is all of 1/2√p; OK.*2287

*We are now ready to do this; the first one will be √3u ^{2} to the n = 4.*2296

*And then, 1/2√p to the 0...I won't even write that one there;*2304

*plus _(√3u ^{2})^{3}(1/2√p)^{1} + _(√3u^{2})^{2}(1/2√p)^{2}*2308

*+ _...let me break that down to the next line, just so that we can have plenty of room...*2326

*+ _(√3u ^{2})^{1}(1/2√p)^{3} + _(√3u^{2})^{0},*2331

*so we can just make that entire thing disappear; times (1/2√p), all to the 4.*2348

*Great; I want you to notice here: Don't get confused by the fact that it is u ^{2} or √p.*2357

*The fact that there are exponents on stuff inside of the binomial doesn't matter.*2362

*We still do this part where the one exponent steps down with each step, and the other exponent,*2366

*the one that starts at 0, steps up with each step of the terms that we work through.*2374

*Great; at this point, we can now plug in our binomial coefficients:*2379

*a 1 for our first blank, a 4 for the next blank, a 6 for the next blank, a 4 for the next blank, and a 1 for our final blank.*2382

*At this point, we can now finally actually simplify this one; well, let's do it in two steps.*2390

*1...we will just have that disappear; (√3u ^{2})^{4}: well, √3 squared is 3; so √3 so the fourth is 3^{2}.*2395

*So, √3 to the fourth is the same thing as 9.*2403

*u ^{2} to the fourth is u^{8}; plus 4 times...√3 cubed is going to be 3√3.*2406

*(u ^{2})^{3} is u^{6}; (1/2√p)^{1} is just 1/2√p.*2414

*Plus...6(√3u ^{2})^{2}: √3 squared is 3; u^{2} squared is u^{4}.*2421

*Times...1/2√p squared will be 1/4 (1/2 squared is 1/2 times 1/2, so 1/4); √p squared is p.*2430

*Break the line once again; plus...next is 4(√3u ^{2})^{1}; well, that just stays as √3u^{2}.*2441

*Times...(1/2√p) ^{3}: 1/2 to the 3 is 1/8; times √p cubed is p√p.*2452

*And then finally, plus 1 times 1/2√p to the fourth; that is going to be 1/16; (√p) ^{4} is going to come out as p^{2}; great.*2462

*Now, we can simplify this whole thing and do the last of the simplification.*2473

*9u ^{8} +...4 times 3√3 times 1/2...1/2 cancels the 4 down to a 2;*2477

*we are left with 6√3u ^{6}√p, plus...we have 1/4 here, so this will become 1/2;*2486

*this will become 3; 6 times 1/4 becomes 3 times 1/2; so 3 times 3 is 9, divided by 2...we have 9/2 as the coefficient there, u ^{4}p.*2499

*Plus...4√3u ^{2}1/8p√p...that is a lot of things; so 1/8...that will cancel to 2,*2514

*when it knocks out this 4; and so we have (√3/2)u ^{2}p√p.*2523

*And finally, our last term is 1/16p ^{2}.*2531

*And there is the full expansion; it is about as difficult as any expansion with Pascal's triangle will end up being.*2537

*But still, notice how much faster that ended up making it than if we had tried to do this whole thing by hand--*2544

*doing √3u ^{2} + 1/2√p, times √3u^{2} + 1/2√p,*2549

*times √3u ^{2} + 1/2√p, times √3u^{2} + 1/2√p...*2553

*We would still be working through it, and still have a lot more to go.*2557

*So, it makes things faster.*2559

*We have to be careful, and make sure that...there are a couple of things that we have to pay attention to.*2560

*We really have to make sure that our n, the row that we are using of Pascal's triangle, matches to the exponent we are raising to.*2564

*We have to pay attention to what our whole a is and what our whole b is.*2570

*It has to be the entire term, not just the u, not just the p, but the entire term of something + something.*2575

*And if it is a minus, it has to be something plus a negative something.*2582

*And then, we set it up with this step down/step up pattern, the blanks; and then, we can just slot everything in.*2586

*If it is a simpler problem, you might be able to do it without having to take such careful steps.*2591

*But if it is a big, complicated problem, I really recommend doing the careful steps.*2594

*It will make it easy to not make a mistake and make the problem just slow and easy.*2598

*All right, that finishes the examples; if you are leaving now, we will see you at Educator.com later; goodbye!*2602

*But if you are staying around for the proof to the theorem, it is time for the "bonus round."*2608

*All right, we are ready to tackle a proof of the binomial theorem.*2620

*First, let's phrase the theorem as, "For any n = 0, 1, 2...and so on and so on" so that is all natural numbers,*2623

*"(a + b) to the n is equal to the sum, going from k = 0 to n, of n choose k times a ^{n - k}b^{k}."*2632

*So, notice that that is just putting all of the binomial coefficients added together, for a fully expanded term.*2641

*We are going to prove this by induction; so, just in case you haven't watched the previous lessons,*2646

*but you are really interested in this proof, we will be using mathematical induction.*2651

*And we will also be using a fair bit if sigma (that is, summation) notation.*2655

*So, if you are not familiar with mathematical induction or sigma/summation notation, watch the lesson on mathematical induction,*2659

*and watch the lesson on Introduction to Series, where we will talk about sigma/summation notation,*2664

*because those things will definitely be necessary prerequisites.*2669

*And before we get into this, I really want to stress: what we are about to go through is a pretty challenging proof.*2671

*This is definitely a college-level proof for a reasonably good math class.*2676

*So, don't be shocked if you find this a little bit challenging to work through.*2682

*This isn't going to be super easy to understand the first time; and that is perfectly OK.*2688

*Math is a puzzle to be worked through and understood over time.*2692

*So, watch through this; if you have difficulty understanding what is going on, moment-to-moment,*2696

*I highly recommend that you take a piece of paper and actually write what is happening on-screen*2699

*as we are working through it in the lesson.*2705

*By working through it yourself, you will be able to understand the steps better,*2707

*because you will have to internalize them, because you yourself will have to be understanding and working through it.*2711

*If at some point a step happens where you have no idea how that step happens,*2715

*pause the video and try to understand what just happened on your paper.*2718

*Figure out how you can get from one step to the next step.*2722

*If you still can't figure it out, back it up; hopefully I will explain through it.*2724

*I will explain a lot of this; we will be working through it slowly and carefully.*2727

*But a really great trick is to work through it on paper.*2731

*It really makes things make a lot more sense, just getting it down on paper, so that is not just "rattling around" in your head.*2733

*You can actually see it, think about it, and have it in front of you.*2739

*It is a really great way to work.*2742

*I really recommend this any time that you are trying to work through a math textbook and things get confusing in the math textbook.*2744

*Just take a piece of scratch paper and write what is going on in the math textbook.*2748

*Writing it out for yourself, understanding it step-by-step, when you write it out in your own hand,*2751

*will end up making most issues that you end up having clear up so much faster,*2756

*because you are having to work through it yourself; you are not just trying to read someone else's language.*2760

*You are putting it in your own language before you are moving on.*2764

*All right, let's get started; this is really good--this is what math is really about, in my opinion.*2768

*Math lets us do all sorts of things; but for me, the cool thing about math is the fact that is puzzles,*2774

*that it is logic; it is something that we can believe in, and it is just there--real logic, real proof.*2779

*This stuff actually comes together and can be shown very clearly.*2786

*All right, let's get to it: proof by induction: begin by noticing how nicely the theorem lends itself to being written*2789

*as some p _{n} statement, some statement for some value of n.*2796

*We have n = 0, 1, 2...so it is just stepping up, one at a time, at (a + b) ^{n} equals this sum here.*2801

*That is what the binomial theorem says; so we can just say that the n ^{th} statement is (a + b)^{n} equals that sum; great.*2808

*It is really easy to write out in this statement idea.*2815

*Our base case: now, before we prove the base case, notice that there is this slight issue.*2819

*The theorem doesn't start at n = 1; it starts at n = 0.*2823

*When we first talked about mathematical induction, we always set our base case at n = 1.*2829

*But with this one, we can't set our base case at n = 1; we actually need to start at p _{0}.*2833

*So, it is not p _{1}, but p_{0}, because the theorem starts at n = 0.*2838

*If we think about this, though, we realize that this isn't really an issue.*2843

*It is just that we need a starting point to work out of.*2846

*It needs to be the first stepping-stone that we then walk forward from, using that inductive step.*2849

*That is what the inductive step is: that is taking one step after another,*2854

*and guaranteeing that future stepping-stones will be there, as long as we have this first stepping-stone.*2857

*So, it doesn't really matter if this stepping stone starts at n = 0 or starts at n = 15 or starts at n = 1.*2862

*It just needs to be some integer value that we can then step forward from.*2867

*n = 0 is a perfectly fine thing to set our base case at.*2871

*We work through this: a base case of p _{0} would end up giving us (a + b)^{0}.*2876

*Is that equal to (we are saying this as a question; we don't know if this is true yet;*2881

*we are checking to make sure that the two sides are true)...it would be equal to the sum*2885

*(if this is true) of k = 0 summed to 0 of 0 choose k, a ^{0 - k}b^{k}.*2889

*So, our left side...well, (a + b) ^{0}...anything raised to the 0 just comes out to be 1.*2896

*Our sum, k = 0, going up to 0...well, that means that where we start is where we stop.*2902

*So, there is only one term in this series when we expand this summation, this sigma notation.*2908

*It just turns into 0 choose 0; we plug in our k; we plug in the k here, 0 - 0, and plug in the k here, b to the 0.*2912

*So, what does that come out to be?*2920

*Well, a ^{0 - 0} just comes out to be 1; b^{0} just comes out to be 1.*2922

*0 choose 0 is going to be 0!/(0 - 0)!, so 0! times 0!.*2927

*So, we have this here, 0!/0!(0!): well, remember: when we set up 0!, we just stated 0! = 1.*2932

*We simply define it that way; that means 0!/0!(0!) turned out to be 1, so our entire right side is 1.*2941

*Our entire left side is 1, as we already figured out early on.*2950

*So that means, indeed, that this does check out; the base case is true; we are good with the base case.*2953

*On to the inductive step: now, here is where things get a little bit tricky, just for understanding notation.*2959

*There is a minor issue with notation here: when we first saw induction, we always had some general statement, p _{n}, this (a + b)^{n} = stuff.*2966

*Now, what we did for the inductive step was assumed...we said, "If p _{k} is true,*2978

*then we have to show that p _{k + 1} is true."*2984

*If this thing is true, then the next one must be true.*2987

*But we have this problem; the way that we usually write the binomial theorem, we use k.*2991

*k shows up as the index in the sum; we are using this all over.*2998

*So, we cannot use p _{k}; this means we cannot use p_{k}...*3003

*if we use p _{k}, we will end up having to re-index and change around variables.*3010

*So, we cannot use p _{k} without re-indexing and changing around variables.*3016

*If we had to use p _{k} and then p_{k + 1}, we would have to come out with some new variable*3019

*to swap out for all of these k's up here, and then it would get confusing,*3023

*because that is not how we are already used to ending up working with the theorem.*3026

*And so, it is going to change its ways, and it just makes things confusing.*3029

*What we are going to do, to avoid confusing ourselves with new variables:*3033

*to avoid confusion, we are going to prove the following for this step:*3037

*if p _{n} is true for some n, then we will show that p_{n + 1} is true, as well.*3041

*So, up here, this is the general statement of p _{n}, and we are trying to show that it is true for all n.*3048

*Any natural number n is what we are trying to show for our general statement.*3054

*But what we are going to do is say, "Sure, let's assume that it is true for some specific n."*3058

*We don't need to name what that specific n is; but it is just one value of n.*3063

*And then, we are going to show that, if it is true for that one value, it has to be true for the next value, n + 1, as well.*3066

*This is OK; before, we talked about p _{k} and then p_{k + 1}.*3072

*But it doesn't really matter what symbol we use; all that matters is that, if it is true at one step, it must be true at the next step.*3076

*If it is true here, it has to be true at the next step.*3085

*If it is true at p _{k}, then it has to be true at p_{k + 1}.*3088

*If it is true at p _{z}, it has to be true at p_{z + 1}.*3091

*If it is true at p _{n}, it has to be true at p_{n + 1}.*3095

*That is different than our general statement of "it is true for all n, forever."*3098

*We are saying, "Let's say that it is true for some specific n; and then let's show that it has to be true for the next one in line."*3102

*This might be a little bit confusing; but really, it is OK to end up using this p _{n}, then p_{n + 1},*3109

*because what we are not doing is assuming that it is always true for all n.*3113

*We are just saying, "Let's say it is true for some n," and then we will show what would happen for the next n, n + 1.*3117

*And that is what we will do to avoid having to get all of this notation confusion*3122

*of having to use letters other than n, of having to use letters other than k,*3125

*because then it would be not what we are used to seeing.*3129

*And while we could work through it, it makes it a lot easier if it is something that we are used to seeing, used to working with.*3131

*We will end up avoiding notation confusion by keeping n and k in this,*3136

*and just sort of knowing what is going on, on a personal level.*3140

*All right, we are ready to actually work through this.*3144

*Let's set this up: for our inductive step, we start by assuming our inductive hypothesis.*3146

*We assume that, for some n, p _{n} is true; that is, (a + b)^{n} is equal to the sum of k = 0 to n of n choose k times a^{n - k}b^{k}.*3151

*Now, what we want to show is that p _{n + 1} must also be true of p_{n} is true.*3163

*Assuming p _{n}, p_{n + 1} must be true; that is what we are working towards.*3170

*We don't know it yet; we are working towards it.*3174

*So, how would p _{n + 1} be stated? Well, that would be stated as (a + b)^{n + 1}*3176

*equals...and now we swap out the n here for n + 1, and the n here for n + 1, and the n here for n + 1;*3182

*and that would be the p _{n + 1} version; up here is the p_{n} version.*3190

*So, what we want to show is that this here is true.*3194

*Thus, if we can show that the left side of p _{n + 1} is just the same thing as the right side--*3199

*that they are just two different ways...writing the left side and the right side, that they are clearly equivalent,*3207

*by manipulating it through "Well, we can do this, and we can do this, and we can do this..."*3211

*and they are all clearly equal, and we can make it from one side to the other side; we will have shown that this statement is true.*3215

*If we can show that the left side is the same thing as the right, we will have shown that, indeed, the statement is true.*3221

*So, what we want to do is see how we can manipulate (a + b) ^{n + 1}.*3227

*Well, in a proof by induction, we always want to toss our inductive hypothesis into this.*3231

*So, our first question is, "Is there a way to turn (a + b) ^{n + 1} into something where we can use our hypothesis?"*3234

*We want to see if there is a way to turn (a + b) ^{n + 1} into the right side of p_{n + 1}.*3244

*Our first question is going to be, "How can we apply our hypothesis--how can we apply p _{n}, (a + b)^{n} = that sum?"*3249

*We look at it: if we look at (a + b) ^{n + 1}, it is pretty easy to get (a + b) to the n to show up; we just split it:*3257

*(a + b) ^{n + 1} is just the same thing as (a + b)(a + b)^{n}.*3264

*At this point, we can now swap out (a + b) ^{n} for the other side of our inductive hypothesis.*3269

*We swap it out; we now have (a + b) times the sum k = 0 to n of n choose k (a ^{n - k}b^{k}).*3276

*We have just swapped out for our inductive hypothesis.*3282

*Now, at this point, we have a + b over here; we can distribute that: a + b distributes onto that sum.*3285

*And we will have a times the sum, plus b times the sum.*3293

*Well, a and b don't vary once we have expanded the thing; they just end up being the same thing.*3300

*So, what we can do is actually bring them inside of the sum.*3304

*They have no direct connection to the index, so we can bring them inside of the sum.*3307

*So, a will apply onto the a ^{n - k}; a^{n - k} times a will be a^{n - k + 1}, which we can write as a^{n + 1 - k}.*3312

*The same thing happens over here: b applied to b ^{k} becomes just b^{k + 1}; great.*3327

*At this point, let's expand these sigma notations.*3335

*The sigma notations are a great way of keeping things compact, but it is a little hard to tell what is going on inside of the notation.*3338

*So, let's expand them, so we can see what is going on better.*3344

*If we expand this, we will have k = 0 here; we will plug that in here first, so we will have n choose 0*3346

*times a ^{n + 1 - 0}, so a^{n + 1}, and b^{0} (that just disappears).*3352

*And then, next, we will go up one step, and choose 1; a ^{n}b...great.*3358

*And we will work our way up, until finally we get up to n; and so, we will have n choose n.*3362

*And it will be a ^{n + 1 - n} when we are plugging in n.*3367

*a ^{n + 1 - n} gets us just 1, so we have a to the 1 here; and b^{n} now, because we are swapping in n for k; and we have b^{n} here.*3372

*Great; so that is what we end up getting from this sum on this side.*3381

*And we can do basically the same thing and expand this sum over here.*3386

*We start at k = 0; we will get n choose 0, a ^{n}b^{1} (if we plug in k at 0, we will have 0 + 1, so b^{1}).*3388

*We work our way up; we get to n - 1, one before our last one.*3397

*n choose n - 1; we will have a ^{n - n - 1}; if you are not sure why that comes out as n - n - 1,*3401

*well, this becomes minus n plus 1, so we get a ^{1} here.*3408

*k + 1...well, if we are plugging in n - 1 for k, n - 1 + 1 gets us ab ^{n}.*3412

*And then finally, our last one, when we plug in n: swap that in for our k; n - k (n - n for our a here) will end up just disappearing entirely.*3422

*We will have a to the 0, so we just omit that.*3430

*We will have n choose n, and b, plugging in k for n...n + 1 here, so we get n + 1 here.*3432

*So now, we have expanded these two sums; now we can start working with them.*3439

*What we want to do first is notice that there are some similarities between these things.*3443

*In fact, we have this really great similarity going on here: a ^{n}b and a^{n}b match up.*3447

*ab ^{n} and ab^{n} match up; in fact, we would end up having this match-up*3454

*between all of the things inside of those ellipses; the pattern of matching will continue throughout.*3459

*The only things who don't fit this matching pattern are the ones at the far ends, the a ^{n + 1} and the b^{n + 1}.*3464

*Notice: the only terms that don't match up of these a to the something, b to the something terms are the first and last terms, respectively.*3274

*If we separate them out, we can relate the sums; we can have this connection.*3481

*We pull them out: n choose 0, a ^{n + 1}; n choose n, b^{n + 1} on the two ends.*3484

*And then, we end up having the matching going on here: n choose 1, a ^{n}b;*3492

*that will match up to n choose 0, a ^{n}b.*3496

*And then, n choose n, ab ^{n}, will match up to ab^{n} with an n choose n - 1 times ab^{n}.*3499

*We have this nice matching going on here.*3507

*The matching will also continue in here with the same thing of the top*3510

*being above the bottom by 1 on its bottom and above the bottom by 1 on its bottom, every time; great.*3514

*So, if that is the case, we can combine the parts in brackets.*3520

*If n choose 1, n choose 0, are both multiplied by a ^{n}b, well, then we can combine them: a^{n}b...*3523

*and we end up having n choose 1 plus n choose 0, all of that times a ^{n}b.*3532

*We pull out the a ^{n}b when we put them together.*3539

*The same thing happens over here: n choose n, ab ^{n}, n choose n - 1, ab^{n}:*3541

*we pull out the ab ^{n}, and we end up getting n choose n plus n choose n - 1, that quantity, times ab^{n} here.*3547

*And inside of it, we will end up having the same pattern go on with the n choose something plus n choose (1 less than that something),*3553

*times the ab stuff; so that pattern will end up continuing throughout.*3561

*And we still have our things on the end; if you are not sure how they transformed from n choose 0 and n choose n,*3565

*to just the a and b, well, n choose 0 is just 1 (if you are not sure about that n choose 0, well,*3571

*that is equal to n! over (n - 0)!, so n!, times 0!; 0! is just 1; n! and n! cancel out;*3578

*so we end up just getting a 1 here, so it disappears and we are just left with a ^{n + 1}).*3587

*The exact same reasoning works for n choose n becoming 1, as well, on the b ^{n + 1}; and we get b^{n + 1} here, as well.*3591

*At this point, we can put this giant sum in sigma notation.*3600

*a ^{n + 1} just stays around; b^{n + 1} just stays around.*3604

*The thing we care about is this giant sum here, which we broke on lines, because it is too much to write on a single line.*3607

*We can do that as the summation from k = 1 to n of n choose k plus n choose k - 1, as a quantity, times a ^{n + 1 - k} times b^{k}.*3614

*Let's check and make sure that this works.*3627

*If we did, indeed, plug in k = 1, yes, that checks out; 1 for k here, k - 1, 1 - 1; that does get us 0.*3628

*a ^{n + 1 - 1} would get us a^{n}; b^{1} would get us b; so that checks out there.*3637

*If we were to do n, that would end up checking out here, as well.*3644

*This is probably one of the hardest steps to see.*3646

*If you work through it slowly, you can see that, yes, what we are doing is that this whole sum*3649

*is just the same thing as what we have this in these giant brackets, this giant bracketed-off portion.*3654

*That is the same thing here; so we can put the whole thing in sigma notation.*3663

*At this point, let's check in with our original goal.*3667

*We have gotten pretty far with this thing; what we have is a ^{n + 1} plus the big sum plus b^{n + 1}.*3669

*Now, compare that to what we are trying to get the whole thing to look like.*3677

*We started with the left side, and we are trying to get it to turn into what its right side was.*3681

*And its right side was a summation: k = 0 to n + 1 of n + 1 choose k, times a ^{n + 1 - k}b^{k}.*3684

*This stuff here matches really closely to this.*3693

*And n + 1, k is not too far off from what is here.*3697

*And n and k = 1...that is not too far off, either.*3700

*There are some similarities; we are starting to get there.*3704

*What would be great is if we could somehow show that what we have here is the same thing as what we have here,*3706

*that n choose k + n choose k - 1 is just the same thing as n + 1 choose k.*3714

*If we could somehow show that that is the same thing, we would be really close*3721

*to showing what we are trying to show-- what we want to show--getting to our goal.*3726

*So, since that would be so useful if it were true--this n choose k plus n choose k - 1 equals n + 1 choose k-- let's go ahead and try to prove it.*3730

*What we will do is create a lemma; a lemma is basically just a mini-theorem.*3739

*A mini-theorem is something that we use to prove another larger theorem that we are interested in.*3744

*It is basically like a thing that we can use to make a short hop to some more useful conclusion.*3749

*It deserves being proven on its own, because it is not just something we can do in a single line.*3754

*But it makes sense, and it is something that we will use towards another theorem.*3759

*It is something that we make on the way towards another theorem.*3762

*That is a lemma; so what we want to do is show that that is true, as a lemma.*3765

*Our lemma is that, for any natural numbers r and s, r choose s plus r choose s - 1 is equal to r + 1 choose s.*3769

*Now, if we want to use our lemma, we have to prove anything that we want to use.*3777

*This is a proof, after all; so let's get to proving it.*3781

*Let's investigate the left side, r choose s plus r choose s - 1.*3784

*We break that down: our r choose s becomes r! over (r - s)!(s!), plus...r choose s - 1 becomes r! over (r + 1 - s)!(s - 1)!.*3789

*And the only thing that you might be confused about is that r + 1 - s.*3802

*Well, remember: r - (s - 1), because it is this quantity here, would end up coming out to be...*3804

*and that part will be factorial; that is what matches up here...r - (s - 1)...that becomes plus; that becomes minus; that becomes positive.*3812

*So, that is why we end up getting the r + 1 and the - s there; that is how we get that.*3818

*What we want to do now is get these things over a common denominator.*3824

*Any time we are trying to simplify and work with expressions, if we have two fractions,*3828

*and we are trying to show that they are something else, well, we put them together, and we see what happens.*3831

*If we are going to get these over a common denominator, let's look at them for a second.*3835

*Well, we have (r - s)!(s!) and (r + 1 - s)!(s - 1)!; well, notice: (r + 1 - s)! is just one more than (r - s)!.*3838

*r - s + 1 is the same thing as r + 1 - s.*3849

*Similarly, (s - 1)! is the same thing as one more going up to s.*3852

*So, we are trying to get s - 1 up by 1, and r - s up by 1; we want to get this to go up, and we want to get this to go up.*3858

*If we can get them to each increase by 1 inside of the factorial, we will be able to have a common denominator.*3867

*And notice: based on how a factorial works, we have the following way to increase a factorial by multiplication: x! times (x + 1) equals (x + 1)!.*3871

*In case you don't see that, consider if we had 6!.*3883

*Well, that would be the same thing as 6 times 5 times 4 times 3 times 2 times 1.*3885

*Well, if we came along and multiplied 6 by 6 + 1, that is, 7, times 6!; well, that would be the same thing as 7 times...*3891

*the expansion of 6!, 6 times 5 times 4 times 3 times 2 times 1.*3898

*Well, now we have 7 all the way down to 1; so we can write that as 7!.*3903

*So, if we have x!, and we multiply it by one more than that x, we will end up increasing.*3908

*we will hop up one more step for our factorial, and we will go (x + 1)!.*3912

*That idea is what we will use to increase (s - 1)! up to s!, and to increase (r - s)! up to (r - s + 1)!, or (r + 1 - s)!.*3916

*All right, to do this, we will multiply the left side by (r + 1 - s)/(r + 1 - s).*3929

*We can't just multiply the bottom; we have to multiply with a fraction on top and bottom.*3934

*And we will multiply over here by s and s, because they match up, too; increasing s - 1 + 1 gets us s; r - s + 1 gets us r + 1 - s.*3938

*OK, we work that out; on the top, r! times r + 1 - s will just be r! times (r + 1 - s).*3946

*On the bottom, the (r - s) times one more will end up increasing to (r + 1 - s)!; the s! remains the same.*3954

*On the other side, the r! times s is just still r! times s; they can't really combine.*3962

*On the bottom, though, we have s - 1 times s; that is s - 1 + 1, so that becomes s!.*3969

*And the left side doesn't change: r + 1 - s!.*3976

*At this point, we now have a common denominator; the denominator here is the exact same as the denominator here.*3979

*So, we can combine them; we combine them, and we have r! times (r + 1 - s), r! times s, up here;*3984

*our denominators are just the same thing, because they just combined by addition.*3992

*But on the top, what we can do is pull out the r!'s; they pull out to r! times what the factors they were being multiplied against were.*3997

*That is (r + 1 - s), and then + s; the - s cancels with the + s, and we are left with r!(r + 1).*4007

*And r + 1 times r!...well, that just means it bumps up by 1; so now we have (r + 1)!.*4017

*We can also toss some fancy parentheses around this to help us see it.*4023

*We have (r + 1)! on the top, and (r + 1 - s)!(s!), which is just the exact same thing as r + 1 choose s.*4026

*(r + 1)! on the top, times (r + 1 - s)!(s!)--that is how r + 1 choose s works.*4039

*So, what we have done is: we have now shown that the left side and the right side are exactly the same thing.*4048

*We have set out to show that the left side and right side of our original thing are equivalent.*4054

*Our original lemma is that they are the same thing: so r choose s plus r choose s - 1 is equal to r + 1 choose s.*4059

*We have now completed our lemma; great; let's go and apply that lemma.*4066

*So, here is our lemma, right here; and where were we before?*4071

*Where we left off with our proof was: we had a ^{n + 1} and b^{n + 1} on the two extremes,*4074

*and then the big one that we really care about the most, the sum in the middle:*4081

*the sum of k = 1 to n of (n choose k plus n choose k - 1) times a ^{n + 1 - k}b^{k}; great.*4085

*But at this point, we now have that nice, handy lemma; we have r choose s plus r choose s - 1.*4096

*Well, that matches up to n choose k and n choose k - 1; so we will get n + 1 choose k out of it.*4105

*We just used our lemma; we are on our way to ending this thing--just a little bit more effort, and we will be done.*4111

*At this point, we are really, really close; this one here looks practically just like what we want to show in the end.*4117

*The only difference is that we need to have our upper and lower summation limits be 0 and n + 1.*4123

*We want to get this to become a 0, and we want to get this to become n + 1.*4129

*How are we going to get that to happen?*4134

*Well, on the way to doing that, we also have to deal somehow with this a ^{n + 1} and this b^{n + 1}.*4136

*They are also in the way; they weren't in our finished thing.*4142

*Maybe these things can be done together; maybe we can somehow shove these into that sigma notation--*4146

*shove them into the sum, and in doing so, get the 0 and get the n + 1 that we want to appear in that.*4151

*Indeed, we can figure out a way to do that.*4157

*Notice: 1 is equal to n + 1 choose 0; also, 1 is equal to n + 1 choose n + 1.*4159

*Now, you can go along and multiply anything you want by n.*4165

*So, since you can multiply anything by 1, then we can multiply a 1 here and a 1 here.*4170

*Well, we know that 1 is just the same thing as n + 1 choose 0; so we swap that out for n + 1 choose 0.*4174

*And 1 is also just the same thing as n + 1 choose n + 1, so we swap that out here, as well.*4179

*So now, we have something that we can mash into our summation.*4185

*They fit the format of the summation; so we can fit them into the sigma notation, to obtain k = 0 to n + 1.*4188

*If we plug in k = 0 on this n + 1 choose k, well, that would be n + 1 choose 0 for k = 0.*4198

*And a ^{n + 1 - k}, a^{n + 1 - 0}, would be a^{n + 1}b^{k}.*4205

*b ^{0} would be something that doesn't exist.*4211

*And then, the same exact thing happens over here: if we had k equal to n + 1, then we would have n + 1 choose n + 1.*4215

*And we would have a to the n + 1 minus...k is n + 1, so n + 1 - (n + 1).*4223

*Well, that would cancel; a ^{0}...and so we have the thing that doesn't show up here.*4229

*It doesn't show up, either; it just disappears.*4232

*And b ^{n + 1} for our k...*4235

*And so, we see that they mash in; we can pull them in.*4237

*Everything else ends up staying the same; n and k = 1 aren't affected, because they do that.*4241

*It is just that these fit the format of the summation, so we can pull them in on the bottom and pull them in on the top.*4245

*We can fit them into the sigma notation, and we obtain this.*4251

*We have managed to show what we were trying to show from the beginning.*4253

*After much effort, we have finally shown that, assuming our inductive hypothesis, p _{n}, we now know that p_{n + 1} is true.*4256

*That is, (a + b) ^{n + 1} is equal to the sum of k = 0 to n + 1 of n + 1 choose k times a^{n + 1 - k}b^{k}.*4265

*That checks out; we have finished showing our inductive step.*4275

*At this point, we know that the base case is true--we showed that from the beginning;*4278

*and we have now finished showing that the inductive step is true.*4282

*So, with some p _{n}, we know that p_{n + 1} must be true.*4284

*Since that works as our inductive step, we now know, combining that with our base case, that p _{n} is true for all n.*4288

*In other words, for any n equal to 0, 1, 2...we have the binomial theorem completely finished proving.*4295

*We have finished proving the binomial theorem; we are done--pretty cool.*4302

*So, once again, I want to say: what you just saw is not easy.*4307

*From the precalculus-level work that you are currently doing (or whatever the class that you are currently working in is),*4312

*this is 2 or 3 years ahead--doing these kinds of proofs.*4317

*But I honestly believe that, if you are really interested in this sort of stuff, you should be exposed to it now.*4321

*You totally have the chance to be able to understand this stuff and work through it.*4326

*It won't be easy like the sort of work that you are used to doing.*4329

*If you are in the kind of position where you want to understand this sort of thing,*4332

*the work that you are normally doing in your precalculus class probably isn't terribly difficult for you.*4336

*But this right here is a really interesting thing that lets us see how far math gets out--*4340

*what kind of stuff math is really like at the college level, when we are really studying serious-level math.*4345

*I think that this stuff is really cool, absolutely beautiful, and a great chance to just see logic in its purest form--*4351

*being able to make an argument that is really ironclad; I think that is really cool.*4358

*It is not for everybody; if you think this is just absolutely awful, and you watched the whole thing,*4362

*just because...I don't know why you watched the whole thing...but if you watched through it,*4365

*and you really didn't like it, that is OK; there are lots of things to do out there in the world.*4368

*But if you thought this was really cool, that is awesome; I think it is really cool, too.*4371

*And you can go ahead and study math, if you are interested.*4375

*You can study something like computer science, where you talk about algorithms like that, as well.*4377

*There are lots of things that will let you have the same idea of well-argued proof, of things building on top of each other-- these really interesting conceptual ideas.*4383

*All right, we will see you at Educator.com later--goodbye!*4390

1 answer

Last reply by: Professor Selhorst-Jones

Tue Mar 3, 2015 5:34 PM

Post by Jamal Tischler on March 1, 2015

It is great you focus on proofs, it realy helps me.

0 answers

Post by Saadman Elman on December 23, 2014

It was very helpful. Thanks.

3 answers

Last reply by: Professor Selhorst-Jones

Wed Nov 20, 2013 1:02 PM

Post by Linda Appling on July 31, 2013

could you slow down in your lectures?