My Favorite Theorem

Evelyn Lamb: Hello, and welcome to My Favorite Theorem, the math podcast with no quiz at the end. I'm Evelyn lamb, one of your hosts. I'm a freelance math and science writer in Salt Lake City, Utah, currently enjoying very beautiful spring mountains, which my guest and my cohost can see behind me in my Zoom background. And this is my co host.

Kevin Knudson: Hi, I’m Kevin Knudson, professor of mathematics at the University of Florida. My wife and I are off to California this weekend. So, you know, she's she's a book artist, and there's a there's a big biannual, every two years is biannual, right? Or is that semiannual?

EL: Maybe?

KK: Who knows?

EL: Biennial is also a word. Maybe they’re the same word? [Editor’s note: dictionary.com says biannual can mean the same thing as biennial (every two years) or semiannual (twice a year). The Oxford English Dictionary, on the other hand, says biannual means twice a year and biennial means every two years.]

KK: Every two years. Except that this two years is this two years is three years, because two years ago was, well, anyway.

EL: Right.

KK: So yeah, so it's called CODEX, and she is exhibiting there, and I am tagging along because I like Berkeley.

EL: Fun!

KK: And we're going to do stupid things like spend too much for a meal at Chez Panisse.

EL: That sounds great.

KK: Yeah, we're really looking forward to it. So anyway, but let's talk math.

EL: Yes. And we are excited today to be talking with Tien Chih. Tien, would you like to introduce yourself?

Tien Chih: Hi, my name is Tien Chih, and I'm currently an assistant professor of mathematics at Montana State University Billings, which is a comprehensive teaching school in the middle of Montana. But later on this fall, I will be joining the faculty of Oxford College at Emory University. Oxford is college separate from the main campus of Emory that's a small liberal arts spin off, so students can do a small liberal arts experience with the first two years of their undergraduate degree at Emory and then go to the main campus to finish, so I'm really excited for that.

KK: Yeah. And that's that that's a little bit outside of town, right? So Emory itself is in Decatur, correct? And the Oxford College is where? I know it's not right there.

TC: Oxford, Georgia, about a half hour or 45 minutes or so east, I think.

KK: Okay. Nice.

EL: Yeah. Well, I am excited that we got you while you're still in Montana, because I just love having guests who are also in the Mountain Time Zone because that they don't think I'm, you know, a layabout because I never want to do anything before 11am.

KK: This is a common problem we have.

EL: Yeah, I am excited, I'll be going to Glacier, or I'm working on planning a trip to Glacier National Park for this summer, which I know isn't actually that close to Billings, because Montana is enormous. But I think it will be very beautiful. Some of the pictures that you post sometimes are really beautiful with the scenery up there in Montana. I'm sure, maybe you're a little behind us on the spring timeline, but similar mountain beauty.

TC: Yeah, I went to graduate school, actually at the University of Montana in Missoula, which is much closer to Glacier. So while I was a grad student I managed to go up there a couple of times, and you're in for a really good time this summer.

EL: Yeah, I'm excited.

KK: Excellent.

EL: Yeah, well, let's dive into the math. What math would you like to talk about today?

TC: Okay, so my favorite theorem is not exactly a theorem, or is a theorem, depending on your point of view. But my favorite math concept that I'm going to talk about today is mathematical induction. There are a couple of reasons why I chose this. One is that I am a combinatorialist/graph theorist. In our field, we don't have a lot of big foundational theorems or theories. In our line of research, we tend not to build skyscrapers, we tend to sprawl. And so because of that there aren't like these big foundation things, so it's hard to point at, like, one theorem and say this is a key theorem in our discipline, but the idea of induction is always present in our work, and especially in my work. Another reason I like induction is because I do a lot of math outreach kind of things. I'm involved in the Math Circle community quite heavily. I run a student circle here at MSU Billings. And mathematical induction is one of those things that almost all students, even children, intuitively understand. The actual mechanisms and formal logic, of course, is not something most people are familiar with. But this idea of if you have something that's true, and you know, you can do this thing, and it's still true, that this means that it just keeps being true, that’s something that students inherently just grasp right away, especially if you compare it with visuals. So I think there's a lot of concepts in math that are like this, that are technically kind of difficult results to articulate, but intuitively, everyone already understands them to some extent.

KK: Right.

EL: Yeah. And you mentioned visuals. So what are some of the visuals you might use to describe induction?

TC: So one of the classic induction proofs that you would give as an example or an exercise in an intro to proofs class is the proof that the sum of the first n odds is n squared. And very often with as presented, that's done with the usual algebra, and the flip, and then the 2k+1 and all of that. But you can easily show that if you take a square, and you take a two by two square, you have to draw a one by one by one extra L around the original square to get the two by two square. And then you get the three by three square by drawing a two by two by one L around the two by two square. And then you just say, Okay, you keep doing that, right. And most students or people without formal mathematical training will recognize, oh yeah, that just keeps happening. But the “keeps happening” is induction, right? That's what we don't say out loud, but that's inherently in this reasoning.

KK: That’s a good visual, because as you say, the algebra — I mean, so when we teach our sort of intro to proofs course, this is where students really get their first taste of induction. And I think it's kind of cold, right? So you say, okay, yeah, so it works for the base case: check. You know, so 1=1. All right, we understand that. And then you say, assume it's true for k and then show it's true for k+1. And I think students learn this mechanically, but I'm never sure that they really grasp what's going on.

EL: Yeah, well, and you if you've learned it by manipulating, you know, like k+1, and, you know, multiply that out to square it or something, that sometimes does remove you from actually thinking about the concepts. I mean, it's an important way to be able to work, but if you have pennies that you're arranging on a desk, or cards, or something in a square, that can be a lot more like, yeah, look what's happening. Here's the next odd number, here we go. Yeah. So just maybe to back up for a moment. Maybe we should actually, state, you know, what induction is? Because it is I mean, it as you said, it's an idea that a lot of people will intuitively feel is correct, but might not have have actually seen as you know, this like packaged, you know, with a little definition bow on the top kind of thing.

TC: Right. So the idea of induction is you need two prerequisites. One is a statement, at least one typically integer value for which that statement is true. So you have a statement, let's say capital P, at an integer k, and we verify that P(k) is true. And then we couple that with an argument that shows that anytime something is true for, say, an n, it must also be true for n+1. So P(n) implies P(n+1), then starting at k, the statement is true for all n greater than or equal to k, so for k and then k+1, and then the implication gives you k+2, and so on. And then you keep going.

KK: And so the visual that I sometimes use with students is you know, it's imagine you have an infinite line of dominoes. If you knock down the first one, they're all going to fall down, right? Which isn't exactly correct, but it's a reasonable visual.

EL: There’s this TV show — not to derail totally, but I'm about to — I think, I don't remember if it's called Domino Wars, or Domino Masters, or something like that it [Editor’s note: It is called Domino Masters, and mathematician Danica McKellar is one of the hosts]. We were in a hotel room flipping through channels, and we saw this and they make these domino things, and in fact, sometimes not all the dominoes fall down when you push the first domino because there's some sort of problem in the the domino line of implications there. But in mathematics, the dominoes are all set up at you know, just the right distance or angle that they do fall down.

KK: Ideal dominoes, right?

EL: Yes.

TC: Although sometimes the dominoes, you can find arguments that that end up skipping a step in some of the dominoes. And so I don't know if you've ever seen these induction, like non-proofs. But I give this one as a challenge to my discrete math students: All cows have the same color.

KK: Yes.

TC: Yes.

EL: I don't think I — so this sounds familiar, but I don't remember what it is.

KK: Well, I’ll let Tien tell us, but I have a story about this. So when I was an undergrad at Virginia Tech and MAA members almost universally heard of Bud Brown, who was very well-known among the MAA community and really entertaining and won the Polya award several times for the things he wrote. And this was his standard joke about induction. He used horses instead of cows. But yeah, let us let us hear the theorem that all cows are the same color.

TC: So let's prove via induction that all cows are the same color. So we start with a base case, n=1, and we say, all right, if we have one cow it’s the same color as itself, ergo for a size of set n=1, all cows are the same color. And then, all right, we assume that it’s true for a set of size k and say, all right, so let's take a set of k+1 cows. Well, by induction, we know the first k cows are the same color. And by induction, we also know the last k cows have the same color. And so ergo the k−1 cows in the overlap, they're also the same color. And more importantly, the first cow has to be the same color as the k−1. The last cow must also be the same color as the k−1. So all k+1 cows are the same color, right?

EL: Yeah. Convinced me.

KK: Sure.

EL: We only see one color of cow.

KK: Right? But you know, for Bud’s joke, it was somehow he made this work where it's like, well, that's a horse of a different color. And now the trick, of course, is to get your students to understand why that proof doesn't work. Because it seems convincing. Right?

TC: Yes.

KK: It feels pretty good. So why don't you explain to our readers why it doesn't work.

TC: So it is a true statement at a certain point that this first cow — in a sense, a true statement that the first call has to be the same color as the middle k−1, as does the last cow. But of course, if k is 1 as in the base case, then that’s zero cows, so it's vacuously true. So the first and the second cow are not not the same color as the middle k−1. But that’s not useful information. So this is what what pops into my — visually, how I interpret this, is as that missing domino, right? We actually took away the second domino, right, the n=2 case, and so because that domino is missing, that induction obviously does not carry through and we have more than one color of cow on this planet.

KK: Yeah. And what's fun about induction is you never stop using it. So you know, you're a combinatorialist, you're clearly going to use it all the time. I'm teaching graduate algebraic topology this term and just maybe two weeks ago, I used induction. I was computing the cohomology of the Eilenberg-MacLane spaces of type K(Z,n). And it's a double induction, because you know case 1 and so you pull yourself from something odd to something even. And then it's a different argument for something even to something odd. So, it just never stops.

EL: So I guess I'm going to betray my naivety about like what combinatorialists do, but as a combinatorialist are you kind of mostly using like the regular induction, not transfinite or you know, some spicier flavor of induction. I don't know, do you have to induction — I’m even forgetting, there are a few different ones that you know go for, like different types of sets. So rather than the integers, you can do induction on real numbers, right, if you set things up right. But are you basically just doing it on the integers mostly? That's the only place I would want to do it.

TC: Yeah. Don't feel bad if you don't know what combinatorialists are doing. Most of us don't know what each other are doing. Right? Again, the sprawl that we talked about. Yes. So in my case, I try not to even deal with infinite things that aren't countable. I have to for some of my constructions, but I would prefer not to have to do anything uncountable. And so yeah, I'm only doing, me in particular, I'm only doing induction on integers. I'm certain if you define graphs on uncountable sets, or this sort of thing, then it would make sense possibly to invoke Zorn's lemma or those other kinds of induction-ish things, but that's not what I do.

EL: So well, the base version is powerful enough, I mean, I don't want to besmirch the fine name of induction. So you know, of course, this is important in your work. My big experience, really learning about induction in my first heavy-duty proofs class in college was a transformative moment, for me, in really being able to work with axioms and stuff. So it's also really important to me, maybe from a pedagogical — I mean, I was the one being pedagog’d at — but, you know, from a pedagogical point of view, I think it is also really important. Do you find that too? Is this a really important moment for your students?

TC: I think so. I think — again, like I said, the idea of induction is something that’s inherent in us, I think, but it's like this idea that you're able to keep doing something. And so when I cover induction, I kind of also use it as maybe one of the first examples where you try to you try to formalize what your intuition told you to do anyway. And there is often a tendency I notice when teaching entrance to proofs type classes that because the idea of writing proofs is such a new thing, that somehow, it's totally like — when they write these proofs, they want to use a lot of jargon, and symbols and theorems maybe that they learn. And it sometimes can get away from their actual understanding of what it is they're trying to prove. So when we start with induction, it’s like, look, you tell me why this is true without trying to prove it, just tell me why it's true. And our goal is to turn that into math, and then also clean up any loose bits or cases or whatever, along the way. But that's really what we're trying to do. So if we're trying to improve that, you know, again, the sum of the first n odds is n squared. It's like, all right, why is that? Tell me why I keep adding these rows, and it still keeps being a square. Okay, now what we need to do is just make that concrete. And that's such an important skill throughout, right, because you can't reasonably prove anything unless you have some idea of why this thing might be true. And then all we're trying to do with the formal writing is just say that. Say exactly what you're thinking, but very, very, very, very carefully.

KK: Yeah. So another thing we like to do on this podcast is ask our guests to pair their theorem with something. So what pairs well with induction?

TC: Let’s see if there's a couple of different pairings I could go with.

KK: You’re allowed more than one.

TC: Okay, sure.

EL: And if you have one, and then you have n of them, you're allowed to have n+1 of them.

TC: I don't think I want to go through the gamut of naturals. So when I first learned induction, I was an undergraduate, and I think I was drinking a lot of whiskey at the time.

KK: That sounds illegal, but we’ll allow it.

TC: And so that's one possible pairing. In the math outreach stuff that I do, back when we used to have it in person, I would often buy little granola bars and little single-serving bags of chips for the students to snack on while we're working on this stuff. And so that's a pairing I would give for working with induction with middle school students, which is the target audience for our circle here. And then, in my current work now as a grownup mathematician, I am making a lot of homemade noodles recently. And I’ve been really enjoying them. And so maybe that's what I would pair for for the induction that I'm doing right now in my own stuff.

EL: I like that. I mean, I would like to try your homemade noodles also. That’s always a lot of work, I think, to to make those at home. But yeah, I like the potato chips idea a lot too. Because, of course, there's the Lay's slogan. I don't know if it's still in their branding, “You can't eat just one.”

KK: Yep.

EL: Which works really well. Plus, for me personally, every potato chip tastes like one more potato chip.

KK: That’s right. Yeah, it truly is. You have wide and then you have to have another one. Forever.

EL: Yeah, but noodles. Noodles, I think are good too. Because, like, it’s hard to count the number of noodles there are. Plus delicious. Is there a noodle dish that isn’t delicious?

KK: What do you do with your noodles? How do you prepare them?

TC: So far I've stir-fried them and I've also made a beef noodle soup with them. Which are both excellent. And they're actually much easier to make than I would have thought.

KK: Do you have one of those pasta maker things where you crank them out? Or?

TC: No, I just roll them into a rectangular-ish sheet. And then I just dust it and fold it up and then

KK: You just cut it?

TC: Cut it with a knife.

KK: Okay, excellent.

TC: Yeah. So they come out a little thick, but I do prefer it that way anyway, so that works for me.

KK: All right. So I think Evelyn I already looking up flights to Billings.

EL: I’ll just drive. Yeah, I could be there—

KK: You’ll “just” drive? I mean, look.

EL: I'll be there in eight hours. I don't know how long it is from where I am.

KK: It’s got to be more than that.

TC: I’m closer to one of you now, but in a few months, I will be closer to the other one.

KK: That’s right. It’s like five hour to Atlanta.

EL: Yeah, well, this has been great. I really glad that we've we got to talk about induction which really has deserved an episode of My Favorite Theorem for quite a while. Would you like to let people know how to find you online or any anything you're involved in that you'd like to plug to make sure people know about it, anything like that?

TC: You can find me on Twitter at @TienChihMath.

EL: We’ll include a link to that.

TC: As you both know, I am a co-organizer for the online seminar Talk Math With Your Friends, which has collaborated with this podcast previously in the past for a live taping. And I don't have too much going on right now. Again, I'm in that very odd phase where I'm in between things, but I am very involved, like I said, in math outreach, in teaching, undergraduate research, that sort of thing, a very teaching-focused kind of career. And so I'm certain that I will have things along those lines happening soon in the future, once I get settled at my new position, so I'm really looking forward to all that.

KK: Alright, sounds great. Well, Tien, thanks for joining us.

TC: Thank you for having me. It was a blast.

[outro]

In this episode, we talked with Tien Chih, who will soon be starting a position at Emory University's Oxford College, about mathematical induction. Here are some links you might enjoy with the episode.
Chih's website and Twitter profile
Talk Math With Your Friends, the online math colloquium series he co-organizes (and with which My Favorite Theorem has collaborated!)
A wikipedia page dedicated to the proof by induction of the statement that all horses are the same color
Domino Masters, a TV show about dominoes