Login

Welcome, Guest. Please login or register.

March 29, 2024, 02:21:03 am

Author Topic: Inequality Induction  (Read 5686 times)  Share 

0 Members and 1 Guest are viewing this topic.

edmododragon

  • Trailblazer
  • *
  • Posts: 32
  • Respect: 0
Re: Inequality Induction
« Reply #15 on: October 07, 2016, 03:27:14 pm »
0
I have an excessive amount of inequalities questions that I dont understand.
Here is another one :)
Thank you so much

Like Rui said, these types of induction questions are uncommon even in the Ext2 course. They require you to consider what actually happens in the geometric conditions provided.
Here's my working for it.
Firstly, to create the "greatest" number of regions, none of the lines can be parallel (or the same line).
We want to somehow create a link between the number of regions and the expression given. To do this we want to establish a pattern. This can be done by simply drawing and seeing what happens to the number of regions for n amount of lines.
We get:
n=1 makes 2
n=2 makes 4
n=3 makes 7
n=4 makes 11
As we can see, each new line seems to add the amount of regions as the number of line it is, starting with 2 regions for 1 line. We can turn this into a pattern. The number of regions for n lines is 1 + (1 + 2 + 3... + n). Using the sum of an arithmetic series, this can be simplified to 1 + n(n+1)/2 = (n^2 + n + 2)/2. We got the expression given! So we're on the right track.
Now realise we haven't actually proven this expression for n is equal to the number of regions for n lines. we've just noticed a pattern for the first few cases. This is where the induction comes in. For case n=1, there are two regions. (1+1+2)/2 + 2. Proven for initial case.
Assume that for k lines, there are (k^2+k+2)/2 regions.
For the case for k+1 lines, we're trying to prove there are [(k+1)^2+k+1+2)/2 = (k^2+3k+4)/2 regions.
Now what happens when we have k+1 lines? We added an extra line in. As mentioned before, it seems to add k+1 regions. How do we prove this? Notice that the added line will cut k lines, since it isn't parallel to any of them. As it cuts each line, it will split each region the line is in, into two, essentially adding another region, however adding that line itself split the overall circle in two, which adds another region. This means that one region is added, plus one region for every line it crosses. That's k+1 regions added! So for the case n=k+1, the number of regions is equal to the number of regions in the case n=k and then with k+1 regions added.
That's (k^2+k+2)/2 + k + 1 = (k^2+3k+4)/2
True for n=k+1 when true for n=k
True for n=1
Proven by induction :)
I hope my working wasn't too hard to follow. You can see why they don't ask these questions anymore.

RuiAce

  • ATAR Notes Lecturer
  • Honorary Moderator
  • Great Wonder of ATAR Notes
  • *******
  • Posts: 8814
  • "All models are wrong, but some are useful."
  • Respect: +2575
Re: Inequality Induction
« Reply #16 on: October 07, 2016, 03:49:42 pm »
0
 Yes that proof is right. I revised over a proof I did recently and it's similar.


An observation to be made: The maximum number of lines is achieved when no three lines are concurrent as well as being non-parallel. That is to say, no three lines meet at the same point.

This is crucial - This is how we ensure that the maximum amount of regions is always achieved. It is how we ensure that the nth line divides out n new regions.

edmododragon

  • Trailblazer
  • *
  • Posts: 32
  • Respect: 0
Re: Inequality Induction
« Reply #17 on: October 07, 2016, 03:54:07 pm »
0
Yes that proof is right. I revised over a proof I did recently and it's similar.


An observation to be made: The maximum number of lines is achieved when no three lines are concurrent as well as being non-parallel. That is to say, no three lines meet at the same point.

This is crucial - This is how we ensure that the maximum amount of regions is always achieved. It is how we ensure that the nth line divides out n new regions.

Woops yeah I missed that. I've seen this question before without the "circle" and just lines forming regions on a plane.

RuiAce

  • ATAR Notes Lecturer
  • Honorary Moderator
  • Great Wonder of ATAR Notes
  • *******
  • Posts: 8814
  • "All models are wrong, but some are useful."
  • Respect: +2575
Re: Inequality Induction
« Reply #18 on: October 07, 2016, 04:09:16 pm »
0
Woops yeah I missed that. I've seen this question before without the "circle" and just lines forming regions on a plane.
Exactly. The proof is virtually identical to the one without the circle. It's basically trying to see how well you know your partitioning

These things were all taken out of the HSC in 2001.

I also realised that the question came out of the old Fitzpatrick textbook, which I don't like

Lottie99

  • Trailblazer
  • *
  • Posts: 41
  • More stressed than I seem
  • Respect: 0
Re: Inequality Induction
« Reply #19 on: October 07, 2016, 04:17:33 pm »
0
This has all just gone way over my head haha
I think I'll stick to just doing past Ext1 Papers

edmododragon

  • Trailblazer
  • *
  • Posts: 32
  • Respect: 0
Re: Inequality Induction
« Reply #20 on: October 07, 2016, 04:18:44 pm »
0
This has all just gone way over my head haha
I think I'll stick to just doing past Ext1 Papers

Haha that sounds like a good idea. You're not even close to likely to getting anything geometrical in your induction questions :)

RuiAce

  • ATAR Notes Lecturer
  • Honorary Moderator
  • Great Wonder of ATAR Notes
  • *******
  • Posts: 8814
  • "All models are wrong, but some are useful."
  • Respect: +2575
Re: Inequality Induction
« Reply #21 on: October 07, 2016, 05:33:29 pm »
0
Inequalities is the art of throwing out the garbage
Nice emphasis Jamon :P

jamonwindeyer

  • Honorary Moderator
  • Great Wonder of ATAR Notes
  • *******
  • Posts: 10150
  • The lurker from the north.
  • Respect: +3108
Re: Inequality Induction
« Reply #22 on: October 07, 2016, 07:59:52 pm »
0