Login

Welcome, Guest. Please login or register.

March 28, 2024, 08:59:57 pm

Author Topic: Induction and the Binomial Theorem: The Weirdest Stuff in Extension  (Read 2827 times)  Share 

0 Members and 1 Guest are viewing this topic.

jamonwindeyer

  • Honorary Moderator
  • Great Wonder of ATAR Notes
  • *******
  • Posts: 10150
  • The lurker from the north.
  • Respect: +3108
Hello once agin everyone! This will be the last of Extension guides  :-[ but we get to finish with the fun stuff! Induction and binomial theorem. These are perhaps the strangest parts of the Extension 1 course; they don't really fit in with anything else (the binomial theorem does have applications in more advanced probability questions), and they offer some of the hardest questions you'll face in an exam scenario. While it is impossible to go through everything that can be asked, I'll go through some common examples, and this guide will hopefully act as a nice refresher before Trials!

I highly recommend the notes available for HSC Math , free! They are awesome and super handy to have! You can also register for an account to post in these forums and share in each others expertise! Share the love  8)

Okay, we'll begin with induction. Induction is a cool process in mathematics which is used to prove a variety of results. In the HSC, it is usually restricted to equality, inequality, and divisibility proofs. For all three, the process is reduced to three steps.

Step One: Prove the result for the smallest integer in the domain. For example, if it is asked to prove for \(n\ge 1\\ \), then you would prove for \(n=1 \).

Step Two: Assume the result true for \(n=k \), where \(k\)is an integer in the domain. Use this assumption to prove the result for \(n=k+1 \).

Step Three: Make a statement resembling the following: Therefore the result is true for \(n=k+1 \). Since it is true for \(n=1\)(from Step 1), it is true for \(n=1+1=2 \), \(n=2+1=3 \), etc, for all \(n\ge 1\\ \).

Again, there are three main types of induction. The first is equality proofs of sum results.

Example One: Prove that \(\sum _{ r=1 }^{ n }{ \left( 4r+1 \right)  } =n\left( 2n+3 \right)  \), for all positive integers.

We first prove the result for the smallest positive integer. When \(n=1 \):
\(\sum _{ r=1 }^{ 1 }{ \left( 4r+1 \right)  } =5\\\\ \quad \quad \quad \quad \quad \quad \quad \quad =1\left( 2+3 \right)  \)
\(\therefore\)the result is true for \(n=1 \)

Next we assume that: \(\sum _{ r=1 }^{ k }{ \left( 4r+1 \right)  } =k\left( 2k+3 \right)  \), ie, the result is true for \(n=k \). We then tie this into the proof for \(n=k+1 \). Remember, we seek to prove that: \(\sum _{ r=1 }^{ k+1 }{ \left( 4r+1 \right)  } =\left( k+1 \right) \left[ 2\left( k+1 \right) +3 \right]  \).

\(\sum _{ r=1 }^{ k+1 }{ \left( 4r+1 \right)  } =\sum _{ r=1 }^{ k }{ \left( 4r+1 \right)  } +\left[ 4\left( k+1 \right) +1 \right] \\ \\ =\quad k\left( 2k+3 \right) +\left( 4k+5 \right) \\ \\ =2{ k }^{ 2 }+7k+5\\ \\ =\left( k+1 \right) \left( 2k+5 \right) \\ \\ =\left[ k+1 \right] \left[ 2\left( k+1 \right) +3 \right]  \)

So the result is proven! And we just copy the statement from above as appropriate. No tricky math here! Just a bit abstract, lots of people struggle with proving a result with an assumption. But it is allowed, and extremely useful. Besides sum results, another common one is divisibility results. The trick with these is coming up with the condition. This is easy. If we want to prove something is divisible by 5 (for example), we are trying to prove it is equal to \(5M \), where M is some integer. This proves divisibility by five. Check out the example below.

Example Two: Show that \({ 3 }^{ 2n }-1\)is divisible by eight for all positive integers n.

So, we want to prove that \({ 3 }^{ 2n }-1=8M \). Subbing in n=1 yields a correct result, so lets get to the good stuff.

Assume that \({ 3 }^{ 2k }-1=8M\)where k is some positive integer.

Now let \(n=k+1 \), and using the assumption above:
\({ 3 }^{ 2k+2 }-1={ 9\left( { 3 }^{ 2k } \right)  }-1\\ =9\left( 8M+1 \right) -1\\ =72M+8\\ =8(9M+1) \)
which is divisible by 8. Thus, the result is true by mathematical induction (again, in an exam scenario, insert a concluding statement like the one above).

The final type are inequality proofs, which operate on the same principles as above. They aren't common in the HSC, but I'll quickly run through one.

Example Three: Prove that \({ \left( a+b \right)  }^{ n }\ge { a }^{ n }+{ b }^{ n }\)for all positive integers n. \(a>0\)and \(b>0 \).

Again, the result can be proven for \(n=1 \), and we assume true for \(n=k \):

\({ \left( a+b \right)  }^{ k }\ge { a }^{ k }+{ b }^{ k } \)

Now using this result:

\({ \left( a+b \right)  }^{ k+1 }=\left( a+b \right) { \left( a+b \right)  }^{ k }\\ \ge \left( a+b \right) \left( { a }^{ k }+{ b }^{ k } \right) \\ \ge { a }^{ k+1 }+a{ b }^{ k }+{ a }^{ k }b+{ b }^{ k+1 }\\ \ge { a }^{ k+1 }+{ b }^{ k+1 } \)

This proof is actually a little strange, check you understand it. We tie in the inequality from the assumption. In the last line, we omit terms, which we can do since both a and b are positive (since, if the result is greater than the result in the third line, it is definitely bigger than the result in the fourth, which is what is required). Let me know if there is any issues with this, because it is a bit weird. But again, the result is proven.

Induction is a cool process which is really, assuming the question isn't absolutely terrible, fairly easy marks! Treat the process like an essay, be clear and logical. Most of the marks lost will be lost from the marker not following your working.

Moving on now to binomial theorem, the general form of which looks like this (excuse the poor formatting):

\({ \left( a+b \right)  }^{ n }={ a }^{ n }+\overset { n }{ \underset { 1 }{ C }  } { a }^{ n-1 }b+\overset { n }{ \underset { 2 }{ C }  } { a }^{ n-2 }{ b }^{ 2 }...+\overset { n }{ \underset { n-1 }{ C }  } { a }{ b }^{ n-1 }+{ b }^{ n } \).

This is an extremely useful theorem with ties into probability and other aspects of mathematics. Questions in the HSC will either be linked to probability, or abstract number proofs. In probability questions, a is the probability of one event occurring, and b is the probability of the other. Thus, \(a+b=1 \). Say for example, you were looking at basketball shots. You want the probability of getting 6 shots out of 10 when the chance of getting one is 60%. So, you set a as 0.6, b as 0.4, and n as 10, in the binomial expansion above. The probability of getting six shots is defined by the term where a has a power of six. Easy.

\(P=\overset { 10 }{ \underset { 4 }{ C }  } .\left( { 0.6 }^{ 6 } \right) \left( { 0.4 }^{ 4 } \right) \\\\ \approx 0.25 \)

The more difficult questions come in the form of tricky proofs. Now, there are literally infinite numbers of things they could ask you here, here is one of the slightly easier ones to get the feel of what the questions look like:

Example Four: Use the binomial theorem to show that \(0=\overset { n }{ \underset { 0 }{ C }  } -\overset { n }{ \underset { 1 }{ C }  } +\overset { n }{ \underset { 2 }{ C }  } -...+{ \left( -1 \right)  }^{ n }\overset { n }{ \underset { n }{ C }  }  \).

This seems unusual, but actually very easy. The terms on the right represent a binomial expansion of \({ \left( 1-1 \right)  }^{ n }=\overset { n }{ \underset { 0 }{ C }  } -\overset { n }{ \underset { 1 }{ C }  } +\overset { n }{ \underset { 2 }{ C }  } -...+{ \left( -1 \right)  }^{ n }\overset { n }{ \underset { n }{ C }  } \)

And of course, \(1-1=0 \), and \({ 0 }^{ n }=0 \), therefore the result is proven!

Once the theorem makes its way to the back of the paper, things get nastier. 2013, for example, required a complicated binomial expansion proof in multiple steps. However, you are lead through, and given the opportunity to continue with given results even if you can't prove them yourself. Do this if you need too! It is way better to get some marks than none at all, don't skip any questions! Some tips for tackling these terrible, monstrosities of questions:
  • Having to differentiate or integrate both sides is common. Check if this may be what is needed in the proof (you may be able to tell by examining what would happen to the powers)
  • Linking to this, binomial proofs are one area where you may have to manipulate both sides to make a proof work. Using calculus as listed above is an example of such a case.
  • Remember that \(\overset { n }{ \underset { a }{ C }  } =\overset { n }{ \underset { n-a }{ C }  }  \), it may come in handy with some proofs!

The best way to prep for these sorts of questions is to practice. Feel free to post any specific questions you wanted me to go over in the forums below! The examples in these guides are definitely not as tough as you could get, they are there as a quick refresher of questions of average difficulty. Make sure you are attempting the harder questions if you want to aim high, and again, let me know if I can help!

Well, that wraps up these series of guides. I hope they are helpful! I'm looking forward to doing material for other subjects, stay tuned!

Remember, if you need extra revision, check out the notes , which go into more detail than I do, designed for more detailed revision rather than refreshers/tips like these guides are. Be sure to register to get access to the notes, and be able to ask me questions! I'm here to help!

Ciao  ;D
« Last Edit: September 23, 2016, 10:27:27 am by jamonwindeyer »