B. Kliban

This post is motivated by a sub-discussion on another post. Mathematical induction is officially in the VCE curriculum (in Specialist 12), but is not there in a properly meaningful sense. So, if people want to suggest what should be done or, the real purpose of this blog, simply wish to howl at the moon, here’s a place to do it.

Mathematical induction has been “rarely” taught in Specialist Maths since the past 15 years.

I must admit that it is good mathematics, but never executed well.

1st generalisation from my experience (which may not be very accurate), teachers (not all of them) tend to teach the contents in Unit 1 and 2 that are more or less relevant to Unit 3 and 4.

2nd generalisation, neither had all teachers been rigorously equiped with sound mathematical background to teach this content, in reality, nor could our study design provide suitable and appropriate supports to us.

3rd generalisation, for some teachers who attempted to teach mathematical induction in Unit 1 and 2, either they are extremely confident and competent in their understanding of number theory and proofs, or they are just trying ‘new’ things out which becomes part of their ‘trial and error’ experience.

Here comes my main concern. If this bit “were to be stipulated in the new study design after 2021, for unit 3 and 4”, by my wild imagination, it would be a somewhat nightmare for many teachers. How do they assess mathematical inductions? For example, previously in IB HL Maths, anywhere you spot mathematical induction, a long question worth 8 ~ 10 marks is expected. How would you fit such a big monster in either paper 1 or paper 2, assuming no change or little change in the format and structure of external assessments? This will be disproportionate.

In the old times (mainly 90s), the number of Spesh kids could hit up to 6000 something. Walking into the 21st century, the enrolment number has been drastically less, which fluctuates around 4000. For a certain period before 1996, upon completion of core part in Spesh, students were required to complete one module out of four: mechanics, geometry, statistics, and Logics. From an old VBOS document, I witnessed the percentage of mechanics being the highest, more than 90%, statistics being the second, 4.5%, and the leftover were geometry and logics…

If mathematical induction were made elective, I am sure Marty’s statement above – “not there in a properly meaningful sense” – will be valid. If mathematical induction were made compulsory, this will discourage many kids and teachers and I suspect that more students will drop spesh and then choose methods (and/or further), which could provoke another decline in the enrolment numbers…

Hi P.N.!

You wrote: “Here comes my main concern. If this bit “were to be stipulated in the new study design after 2021, for unit 3 and 4”, by my wild imagination, it would be a somewhat nightmare for many teachers. How do they assess mathematical inductions? For example, previously in IB HL Maths, anywhere you spot mathematical induction, a long question worth 8 ~ 10 marks is expected. How would you fit such a big monster in either paper 1 or paper 2, assuming no change or little change in the format and structure of external assessments? This will be disproportionate.”

I’ve noticed that induction questions are usually excessively long as well, in papers that I’ve seen from the HSC. I don’t understand why. For example, if you are asking students to show that some formula for adding up certain terms is valid for all , then why not structure the question so that they complete one or two steps of the overall process?

For example:

Consider the formula

where is a natural number.

We may prove this by mathematical induction. First, the base case:

and

Therefore the formula holds for .

Your task is to finish this mathematical induction proof.

We must establish the inductive hypothesis, and then conclude. Assume that the formula holds for a natural number :

You must prove that

holds, and then conclude the validity of the formula at the start of the question (I would give it a tag, but I don’t think they work here) by using the principle of mathematical induction.

You can tweak these questions by giving more or fewer steps in the statement, to make longer or shorter questions. Or make the hypothesis more tricky to prove, or only give them part of the hypothesis. It depends on what you’re trying to achieve.

I guess my point is that induction questions don’t need to be long just because they are using induction.

Cheers

Glen

Hi, P.N.

Your first generalisation is close to a universal truth. Officially, Specialist 12 is an excellent subject, and I know a number of teachers who go to town with it. But most will play the game and treat it as Specialist 34 Lite. And Specialist 34 sucks balls.

Your second generalisation is almost certainly correct. I’ll note, however, that such concerns didn’t stop VCAA introducing Statistical Fucking Inference.

I think your concern about grading is valid, but I don’t think you can divorce it from the general issue of VCAA grading on all topics: it’s fucking lunacy.

As for the danger that including induction might frighten more kids away from Specialist, that is probably true and I couldn’t give a shit. All I care about is offering a decent, and the best possible, mathematics education to the greatest number of kids. If the kids, or their idiot advisors, or their idiot parents, or their idiots teachers, are then too stupid to appreciate the offer, that’s their problem.

I always have to re-teach it, which baffles me. Is the material provided to teachers so terrible that it is covered poorly? It would have to be really awful, because induction is one of those unusual mathematics topics that is very easy to teach (at least in my opinion).

A proof by induction is just shorthand for a derivation that can be constructed given a parameter. Like a self-writing computer program. The fact that it works is the main content of the principle of mathematical induction (that’s the theorem that I usually state). It’s really easy for kids to grasp this concept, even little kids. I showed some primary kids induction by starting with a proof that adding to itself times equals , which took about half an hour with all the fun bits. Then we did adding up the numbers from to . That was about an hour, but I took a scenic route.

Of course you don’t teach it in the framework of first-order logic. I have only rarely done that at uni (and not at all in the last ten years, and maybe I won’t ever do it again).

Or, maybe, induction just isn’t covered. That would make more sense. What a shame, it’s a really simple, fundamental technique.

Hi Glen, no idea what happens in NSW, but NSW has always (i.e for the last 50 years) been more pure than Victoria. In Victoria, induction is a Year 11 topic, but does not reappear in Year 12. And, thus …

…does not reappear in 12? How weird. I guess that’s what you guys mean with the whole Specialist 12 vs 34 talk (which I do not follow, sorry).

:/

If by “weird” you mean “idiotic” then, yes, it’s weird.

Specialist Yr 12 is Specialist Units 3&4

Specialist Yr 11 is Specialist Units 1&2.

I can see how referring to Specialist 12 might create some ambiguity/confusion (is it Specialist Yr 12 or Units 1&2?)

When it comes to the actual teaching of math. induction, I was never happy with the exercises we had to offer. They were either trivial (to a naive student) or too difficult. An example of the trivial is to prove (under appropriate conditions) that

where is differentiation. Then again, I have an ancient memory of self learning the topic from the Shaum outline “College Algebra” where the examples were meaningful.

I only ever taught math. induction to Computer Science students; the topic led nicely onto recursion programming where they could see (backwards) induction in action.

Would like to see a collection of nice examples. To get the ball rolling, here is one from my time with Arthur Erdelyi.

. Maybe a bit too abstract for Year 12?

PS Marty. Still struggling with your site. Every time I post it asks for my name which I seem to vary. Now it has concatenated these!

Hi Tom, I fixed your name in this comment. Not sure exactly why you are having trouble, but it may be an issue of having or not having a WordPress account. Other commenters here may be able to help.

When leaving your comment, you can click a little icon (a G if you have a google account, an F for facebook, a W for wordpress etc) that will sign you in. That’s all I do.

I’ve taught induction many times in both IB HL and Year 11 Specialist (which I know is not a prerequisite for the VCAA examined Specialist, but I’ve not had a student go into Year 12 Specialist without learning induction, contradiction and a few geometric and vector proofs).

My concern is never with the concept; I think it is actually quite clever.

My concern is that in some exams, it can become very predictable, for example Prove that is divisible by 3 for all positive integers n.

The IB HL had some really nice proofs when the IAs were set externally, but these too seem to have become a victim of the new curriculum structure.

Based on what I have seen in VCE Specialist exams, if induction were to be tested, it would be chosen from a very small selection of examples and would not really test much.

But if it were included at the expense of statistical inference, bring it on!

(Note: I really also like statistical inference and statistics in general, just not the way VCE assesses it)

Here is my almost off-the-cuff sample question. It’s a bit less hand-holding than Glen’s and I think it would be very suitable for a Specialist 3&4 course that included induction (but of course I’m biased):

Question 1 (9 marks)

(a) Prove the identity

.

4 marks

(b) Hence use proof by induction to prove that

.

3 marks

(c) Solve for .

2 marks

I think it’s possible to write many questions like this, so predictability is a non-issue if you have creative and competent writers. I’d particularly enjoy seeing all the questions the commercial organisations would write.

Not wanting to be nit-picky… but should your identity have an equivalence sign?

The answer to “Should that be an equivalence sign?” is pretty much always “No”.

JF, without working through the details of your specific question, that type of question would be great. And, as you say, there are plenty of them to be had.

As you say below, any formula with an n is open to an induction proof. That includes interesting trig sums, integrals, derivatives, …. Indeed a plentitude of seeds from which to grow great questions. And then you can ask a question where the result gets applied in some interesting (or, in my example, banal) way.

Yes, and actually more: technically, any formula with an n

requiresan induction proof.JF,

I like inductive proofs too but I think part (a) may stump many students under exam conditions unless they link part b) into a). Part c) would make a good MC question.

It would make a great investigative project though when teaching complex numbers and De Moivre

I have seen it proved by trig manipulation , conversion to exponential form using cos x= (e^ix +e^-ix)/2 etc, and also by noting the geometric series formula for z+z^2….+z^n = C + i S say when z not = 1 and equating real and imaginary parts

to obtain C and S as in link below

Steve R

Hi Steve.

I’d like to think that part (a) can be done as a – reasonably challenging – stand-alone ‘Prove the identity’ question.

Then, if induction has been taught properly, linking (b) into (a) should be obvious (particularly with the word

Hencedragging students by the nose).Part (c) is included to give the student an opportunity to apply the result in part (b) in a very simple way, and at the same time assess his/her ability to solve some simple trig equations. Again, it’s a stand-alone question. I think making it a MCQ and hence allowing the use of a CAS (such as

Mathematica!) to solve it would completely trivialise the question.I think to say that

“part (a) may stump many students under exam conditions unless they link part b) into a)”

is to lower the bar to unacceptable depths and to underestimate how induction would be taught. It should also be taken in the context of the resources I would hope were available to the student (decent textbook questions, trial exam questions etc)

I often have arguments with trial exam vettors about how

such-and-suchquestion is too difficult. I always reply that Specialist Maths students are meant to be reasonably strong mathematics students and that there needs to be questions for the strong students. Then I get the counter-reply “What about the weak Specialist Maths students, they won’t be able to get any marks for it” …. I contend that the expression ‘weak specialist maths student’ is (orshouldbe) an oxymoron. (As opposed to the oxygen breathing morons at VCAA).JF,

Thinking about my comment a little further I guess you right about the oxymoron …but I’d

I like to see this sort of question in a high school mathematics competition (With a few hints perhaps) as one of five to be answered in 2-3 hours say to sort the good candidates from the exceptional where time pressure is of less importance

Steve R

Hi Steve.

I’m genuinely curious – do you think part (a) is too difficult for a Specialist Maths Exam 1? And is too difficult even for a High School maths Competition without a few hints being given?

LHS

(this step is suggested by the form of the RHS)

and then it’s just a repeated application of the sum-to-product formula

on the stuff inside the square brackets (initially suggested by the products of sin and cos).

1 mark for the first step, 1 mark for

recognisingthat the sum-to-product formula needs to be used, and the final two marks for clear and correct usage of that formula.JF, it’s too difficult for most Specialist teachers.

Marty, that’s a very troubling assertion if true.

Yes, it is troubling.

JF ,

No as I had a similar example appeared in my high school highers math text for year 11 some time ago but I think the trig manipulation is technically tedious if you go down that route

Perhaps it would make a great start for a SAC on induction or other investigation within the constraints of the current tedious curriculum

Steve R

Hi, RF. I think you’re right. VCAA would make the induction formulaic in the same manner as everything else. Still, I’d much prefer formulaic induction to formulaic Statistical fucking Inference.

My LaTeX didn’t format quite the way I wanted it to, can someone remind me of the appropriate code here?

Thanks…

Did you mean to use the carat (^) for an exponent? So that it appears:

??

Ah, yes. Thanks.

Hi, RF. I changed it to exponential form. I can change it to exp(n) form if you like.

Thanks Marty, I was going for what Glen said… 7^n+2 is divisible by 3 for all integers n>=1.

goes to find LaTeX guide amid pile of booksDone.

To answer the question: what should be done? I have a few suggestions, none of which will amount to anything.

Restructure the exams. Paper 1 could be 10 short-answer questions and paper 2 could be 5 longer answer questions. All without calculators. This would allow part of one of the longer questions to include proof as a final step.

Restructure the SACs so that proof appears somewhere on at least one of them. This may require some up-skilling of teachers in a few schools where the SM teacher either hasn’t completed a degree with a major in Mathematics or did so a very long time ago and has forgotten the subtleties of rigorous proof.

Make SM12 content assessable in SM34 much like in Methods. This has always puzzled me anyway. FM I understand, because VCAA wants to allow students to (say) study MM12 and then MM34 and FM34 (I don’t agree, but I do understand their thinking, also totally disagree with it, but that is not the point) but SM not being a 2 year course in the way MM is just doesn’t make sense.

I don’t see any of this becoming a reality.

How about Exam1 short answer + multiple choice (byo pen/pecil only), Exam 2 say 6 extended problem of equal weight, choose 3 you like most, but all work must be shown, all detailed explanations and logic needed for full marks.

Let’s say Exam 2 optional, but maximum for Exam 1 only is C . It can test most skills/facts/basic logic.

Exam 2 only for ambitious, high flyers. MathInd would compete with other problems as for competent students it would be an easy piece.

Also , perfect scores virtually impossible, standardising to the highest score achieved.

Just dreaming…

One three-hour exam, with a mix of long and short, and no SACs.

And no calculators…

…or notes.

You could probably get away with a 2 hour exam with the SM content.

Yes and yes and, because it’s currently a shit subject, yes.

Hi,

For Specialist Students De Moivre’s Theorem is often proved by induction .

Eg https://en.m.wikipedia.org/wiki/De_Moivre%27s_formula

Steve R

Thanks, Steve. Officially any formula with an n requires an induction proof. Many proofs are of the “well, duh” variety, which is why I think Tom Peachey and others are expressing reservations. De Moivre for me is probably borderline. But, if induction were part of the Specialist medium, one could more freely, and valuably, refer to it in such contexts, even if one didn’t work through the nuts and bolts.

I have never understood why you introduce k as the new variable, and then prove the k + 1 case. Why not keep n and prove the n + 1 case? How does changing the variable affect anything? Thanks!

It’s a good question, Craig, and that aspect confuses many or most students. There is a point to it, but I’ll let the other guys reply in substance.

For my mind, the reason is that the phrase assume true for makes more sense than for .

You’re trying to prove that

ifthe statement is true for some given value of n (greater than the value used in the base case), say n= k, then it is true for the next value of n, namely k+1.So k is the value of n that the statement is assumed to be true for. You’re talking about an assumed value of n.

As a slight aside, the following might be of interest: https://www.amsi.org.au/teacher_modules/pdfs/Maths_delivers/Induction5.pdf

This question goes to the heart of how induction . Understanding this question will also allow you to understand the connection between induction and the fact that is countable. (For more in this direction, transfinite induction is a wonderful next topic, using which you can prove beautifully counterintuitive facts.)

When you are using the principle of mathematical induction, you are stating the following:

“Give me a natural number . Now, I claim the following:

My proof of this claim is the following:

plus

(this is an instantiation of the inductive hypothesis for equal to 1); plus

and so on, until we finally reach

Now we string these implications together and (using modus ponens times over) finally conclude

”

Take a look at this argument — how many times is the inductive hypothesis used? It depends on . That’s why there should be distinctive labels for these variables. The variable describes and is fixed in the proof. The variable is instantiated and re-used a number of times to the proof.

I hope that makes sense!

Cheers

Glen

Re: “The variable n describes

what statement you are trying to proveand is fixed in the proof. The variable k [provides anassumedinstance of when the statement is true] and [is] re-used a number of times toconstructthe proof.”Very nicely put, Glen. They’re more or less the words I was groping to find in my earlier comment. The meaning of “instantiated” might be a stretch for some readers (like myself) – I took the liberty of inserting my own phrase.

Thanks JF! As one student put it, I have chronic “jargonitis”: using technical language without realising it. I’m still recovering, and very happy for people to improve what I’m saying by getting rid of unnecessary technical terms, or defining those that people may not be familiar with.

It’s from hanging around with all those maths ed guys.

Just for completeness, several of the last comments at https://mathematicalcrap.com/2020/04/21/witch-36-sub-standard/ were directly referring to induction (leading to the creation of this Induction post).

An oldie but a goodie

Theorem: All horses are the same colour.

Proof (by induction); Let P(n) be the statement that “In any set with n horses, all horses are the same colour.”

P(1) is true – obvious.

Suppose that P(k) is true. Let S be a set with k+1 horses. Remove one and then the remaining k horses are all the same colour (by above supposition). Put the horse back and remove another one: they too are all the same colour. Hence, all k+1 horses are the same colour. By the principle of mathematical induction etc.

Terry,

Wonder if you can apply the same inductive fallacy to a set of spotted spherical cows?

https://en.wikipedia.org/wiki/Spherical_cow

steve r

And by a similar argument, everyone has the same birthday…

The assumption P(k) needs to be true for any group of size k otherwise the following step is logically invalid.

Euler’s rule is another really nice one that can be proven by induction in a couple of different ways. I personally like it as an example because it is not a number theory example as many of the early-encountered examples tend to be.

Bertrand Russell described mathematical induction in terms of an infinite train. When the first carriage is jerked into motion, this causes the second carriage to be jerked into motion. Stand beside any carriage and it will be eventually jerked into motion. Every carriage will be jerked into motion … but the whole train never moves. This is why you need to invoke the principle of mathematical induction.

A bit like VCAA.

Except with

thosejerks it’s called the principal of mathematicalreduction.