13
$\begingroup$

Much mathematics is intimately tied to recursion, be it in definitions (like factorials and integer powers) and proofs by induction. This is also very relevant in computer science and programming. However, it is my experience that students have a hard time to understand what is going on, and even more to see where and how to apply the techniques. My impression is that by now, through decades of daily use, I'm not able anymore to see where the student's dificulties are. When presented with a problem asking for a induction proof, most are able to write down a reasonable answer, but is seems they still feel unconfortable with it. Unless specifically directed to use it, they will very rarely explore it's applicability.

Are there any suggestions on what to emphasize, what symptoms alert of particular types of misunderstandings?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
9
$\begingroup$

Suppose you give a kid an input/output table such as {(0,1), (1,3), (2,7), (3,13)}, and ask your students to find a rule for this table. My experience has been that some students will try to find a closed-form rule, while others will instead notice something like a recursive pattern in the outputs. What's hard for students about recursion, I find, isn't the recursive reasoning in definitions, but instead the way of representing that in function notation. I've found it productive, in the past, to have kids informally state recursive definitions, and then validate those sloppy, informal definitions before formalizing them in accurate language and notation.

Also, I have a really great Precalculus textbook (from the CME Project) that builds a students understanding of proof by induction on top of their understanding of offering recursive definitions. It's a great textbook with a lot of fantastic ideas for teaching math, even if you're teaching more advanced material.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ The other thing I'd add is that there are some philosophers of math who think that proofs by induction are not explanatory in the way that many other styles of proof are. So a certain amount of difficulty is to be expected. See here: philosophy.unc.edu/people/faculty/marc-lange/… $\endgroup$
    – Michael Pershan
    Mar 14, 2014 at 13:52
8
$\begingroup$

For a long time, I felt like induction was silly - because of the way most textbooks deal with it - giving inductive proofs for things that have more useful constructive proofs. Teach recursion through examples that need it. I would love to accumulate some good examples here.

I've seen better examples in programming courses (which I taught long, long ago) than in math courses. I once tried to figure the odds of winning the dice game of Craps. That is best done recursively, I believe.

Improve this answer
$\endgroup$
4
  • $\begingroup$ The CME Precalculus textbook uses a bunch of geometric results for their applications of proof by induction. For example, the triangulation of polygons. They ask kids to offer a proof for a Two-Color Theorem, inspired by the more famous Four-Color version. They also have a bunch of fun problems where inductive reasoning in misused, which really gives you a chance to dig into the assumptions of the proof technique. Basically, I'm a huge CME fan. :) $\endgroup$
    – Michael Pershan
    Mar 14, 2014 at 13:59
  • 1
    $\begingroup$ @Michael, you've convinced me. What is the title of this textbook, so I can try to find an inexpensive copy to buy? $\endgroup$
    – Sue VanHattum ♦
    Mar 14, 2014 at 14:03
  • $\begingroup$ CME Project: Precalculus. You can find it for about 30 bucks used on Amazon. cmeproject.edc.org $\endgroup$
    – Michael Pershan
    Mar 14, 2014 at 14:11
  • 1
    $\begingroup$ Done. $22 at abebooks. Used bookfinder.com to find cheapest. $\endgroup$
    – Sue VanHattum ♦
    Mar 14, 2014 at 14:19
1
$\begingroup$

Let's remember that there are even advanced mathematicians still trying to work out inductive proofs. its a complex topic at the heart of math/CS also. Suggest studying the Fibonacci sequence. Suggest studying the different formulas for it, constrasting the recursive one versus Binet's formula.

Suggest studying it from a CS point of view. Show computer experiments that compute recursive formulas/functions and then show "debug output" of them running. Show how an inductive proof is like a recursive program running. another great area for recursion/induction analysis is sorting e.g. quicksort and other recursive sort algorithms.

There are many ideas/exercises in the following book, one of the classics that focuses on the tight coupling between induction & recursion in CS/math: Structure & Intrepretation of computer programs Abelson/Sussman MIT which uses Scheme, a variant of Lisp (and built out of Lambda calculus).

It might help to study induction across different math fields, e.g. show an inductive proof in calculus, number theory, computer science one right after the other and show the basic "architecture" of the concept.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I love SICP, but it is a complete waste of time on beginning undergraduate students (my target audience) precisely because they run away screaming bloody murder if you say "recursion"... $\endgroup$
    – vonbrand
    Jun 16, 2014 at 12:01
  • 1
    $\begingroup$ Fascinating. I learned about recursion (in LOGO, which is also a dialect of Lisp, btw) when I was - I don't know - maybe 13 or so. No idea why people find it difficult... Proofs by induction, yes - maybe because of the fact that the hypothesis and the statement. But with recursion you don't have this formalism... $\endgroup$
    – mbork
    Jun 16, 2014 at 20:46
  • 1
    $\begingroup$ @mbork it seems that some people will "get" recursion naturally, others won't ever understand it. $\endgroup$
    – vonbrand
    Jun 20, 2014 at 7:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.