Welcome to episode 35. This is the college algebra math 1050 class, and I'm Dennis Allison. Today we have a quite different topic. We're going to talk about something called mathematical induction, and this is actually a process for proving infinitely many cases of a theorem. Now, let me just begin with a few comments here before we go to our list of objectives. If you can go to the green screen, I want to write down a few words here. You know, if you took a course in logic, you'd find out that the term proposition or statement have the same meaning in logic, oops, statement, and that is that these are statements that can be given a true or a false truth value. So if I say a proposition or a statement in mathematics, I'm referring to something that can be termed to be true or false. OK, and now let's go to our list of objectives, and we're going to see how this has an effect on our discussion today. Today we're going to look at how we can prove that a number pattern holds for infinitely many choices of that number. Then we'll look at the principle of mathematical induction, and then we'll look at some examples of mathematical induction. Now, let's go to the next graphic, and we'll see a list of propositions. First of all, we say 1 equals 1. I think we could agree that's true. The next one says 1 plus 3 is 4. Yeah, that proposition's true. Then 1 plus 3 plus 5 is 9. That's true, I think. And then 1 plus 3 plus 5 plus 7 is 16. Now, you notice on the left-hand side, what I'm doing is adding up consecutive odd numbers, beginning with 1. 1, 1 plus 3, 1 plus 3 plus 5. And what about the numbers on the right? The sums, what do you notice about them? They're the squares. Those are squares. Yeah, we have 1 squared, 2 squared, 3 squared, and 4 squared. So in other words, we have what seems to be a number pattern that says if you add up consecutive odd integers, beginning with 1, then you get a square. And by the way, you notice that the number that's squared is the same as the number of odd integers on the left-hand side. So on that fourth line, for example, 16 is 4 squared, and I'm adding up four odd integers. So I guess we might begin to wonder, is it true that if you add up the first, say, n odd integers, would you get n squared? And so that's the question that I ask, is the sum of the first n consecutive odd integers always n squared? Now, if this is true, how could I go about proving it? Now, you see, I think the difficulty here is that we have infinitely many cases to consider, and how can I prove this for infinitely many cases without writing them all down? And to write them all down would take, I guess, an infinite amount of time. So it seems like it might be an impossible problem to actually prove or to disprove.  Well, I was thinking if you make this like a square and say blocks or something as you're looking at them, it always takes two more each time to fill it up. You know, as a matter of fact, we're gonna be looking at a model for some of these problems using blocks, so I think you have a good idea. And I think you'll see that come up on a graphic here in just a minute. Okay, I'll tell you what, I'm gonna go over here to the whiteboard and let's try examining this problem, see how we'll prove it. Okay, now, you see, we have the first proposition, I'm gonna call it proposition number one, and that is that one equals one. And I think that's certainly true. Okay, and then I'm gonna say proposition number two, so I'll just call it P, proposition number two, says that if you add up the first two integers, you get two squared, or in other words, four. And I think that's true, one plus three is four. And then I have proposition three, let's see, what would be proposition three? One plus three plus five. One plus three plus five, yeah, would equal three squared? Three squared, yeah, three squared, and I'll just put a nine there. And that is true, by the way. And I think the last one that we showed on our graphic was proposition four. And Susan, what does proposition four say? One plus three plus five plus seven is 16. Equal 16, yeah, four squared is 16. And let's see, that's true, because seven plus three is 10, and then six more is 16, so that one's true. Now you might say, well, Dennis, looks like it worked in four cases, it must always be true, but somehow that doesn't sound like a logical argument to me. Just say it worked four times, so it must always work. Let's just try this one more time and see what it would say. I should write down the first five odd integers on the left-hand side, and put five squared on the right-hand side. So one plus three plus five plus seven plus nine. Okay, so I've got five odd integers. And on the right-hand side, 25. Now let's see, is that really 25? Well, nine and one is 10, seven and three is 10, 20, and then five more is 25, so that was true. Well, now we're getting more confident all the time, but I don't see how we could take this leap of faith and say, it must always work for every positive integer in. So instead, I'm gonna have to find some approach that will prove this for all cases. So what I'm gonna do is to start over again, but I'm gonna write down what I'll call proposition in for the nth case, proposition in. Now, piece of n would be the case where I write down n odd integers on the left, and I'll put n squared on the right because that'd be how many odd integers there would be. So that'd be one plus three plus five plus seven. Now, I claim that the nth odd integer is two n minus one. I'll come back and explain that in just a minute. And then this sum should equal what? If the proposition, if the pattern continues to hold. N squared? It should equal n squared, okay? Now, I think people at home and students in the class here may wonder, well, is that really n odd integers? You put two n minus one. Well, I tell you what, just to count them, I'm gonna add one to every one of those numbers and just list it right below here. Two, four, six, eight. And if I add one to that one, that would be two n. Now, obviously, this isn't the same sum as that because all of these numbers have gotten bigger. I'm just wondering how many numbers there are here. Now, I'm gonna divide by two all the way through that. And I have one plus two plus three plus four up to, if I divide by two, that last number will be n. So how many numbers have I listed right there? One, two, three, up to n. How many numbers can I say there are there? N. N numbers, okay? Now, there are just as many numbers here because all I did is divide by two but I didn't delete any numbers. So there must be n numbers there and that means there must be n odd numbers up above because I didn't delete any there. All I did is add one to each of the odd numbers to make them even. So if I have n numbers here, then I have n numbers there and therefore I do have n odd integers up above. Okay, so I've kind of gone all the way around the world to explain that that really is n odd integers. Okay, so my goal then is to prove that this is true for every positive integer n. Okay, so we want to prove that the proposition p of n is true for every positive integer n. You know, another name for positive integer because if you look in your textbook, they may not say positive integer. Another name you could use here would be counting number for every counting number n because when you count, you count one, two, three, four, et cetera. And so if n is any positive integer counting number, so when n is one, that means I'm only have one integer on the left and I have one squared on the right. When n is two, then I have two odd integers on the left and I have two squared on the right, et cetera. Okay, well, now how would I go about proving that this is always true? Well, the procedure that I want to demonstrate here is a procedure known as mathematical induction. So let's write that term down. And basically the principle of mathematical induction involves only two steps. Now, you might think it should involve infinitely many steps because if I were gonna establish each one of these statements individually, there would be infinitely many of those statements. I think we actually verified five of them. But for mathematical induction, there are only two steps and here's what the two steps are. First of all, you have to show that the proposition is true for the very first choice of n and the smallest choice of n would be one, that's the smallest of the counting numbers. So what I want to do is to establish that this is true. I'll put a question mark because that would have to be established. And then the next step is to show that if the proposition is true for an integer k, then the proposition for the next consecutive integer, k plus one is also true. So I have to show that if it's true for one integer, it's true for the next integer after that. You know, this is very much like lining up dominoes. When you set dominoes on in and you line them up to knock them down, imagine here that this is a tabletop and suppose that I were to set up a domino there and then a domino here and then a domino here and then a domino there, et cetera. And I keep lining these up so that they sort of follow a little path or trail. And I have them lined up so that if any domino falls, the one after that will fall. That's sort of what this statement says right here. If the proposition is true for k, then it must be true for the one after that. So if a domino falls over, then the next one must fall over. But that doesn't mean all the dominoes fall down because I have to get this started. I have to push over the first domino. And that's what the first part does is it gets it started by saying proposition number one is true. So if I knock over the first domino and then if I have marane so that if the kth domino falls over then the k plus first domino falls over, then that allows this procedure to continue. This second part is sometimes referred to as the inductive step. I wouldn't ask you that, but that's a name that's sometimes given for part b. So we have to get this initiated by pushing over the first domino and then we have to have marane so that when one falls, the next one falls. Okay, so if I can establish these two things, then shall we say all the dominoes fall over are back to this problem. The proposition is true for all natural numbers. Okay, well let's see how that would go. The first thing I wanna do is to establish that the proposition is true for p equals one. Okay, so over here on the side, let me just ask this as a question, is p of one true? Well let's see now, actually I think we've already seen that p of one is true. What that would say is, if I list the first odd integer on the left, is it equal to one squared? Now you know actually there is no addition taking place on the left-hand side, there's only one, there's only one number to write down, but I'm listing only the first odd integer and yes it does equal one squared, one does equal one and that's the proposition at the very trivial level when I substitute in one. Now we come to part b. Part b says, if p of k is true, then is p of k plus one true? I don't put a question mark on that. Okay, so this will take a little bit more space and a little bit more time to verify, but it's not difficult to verify. I'm gonna start off by supposing that p of k is true and then I wanna prove that p of k plus one is true. So let's say suppose p of k is true. Now I'm assuming k is some positive integer, it could be one, it could be two, it could be 110, it just represents sort of an arbitrary integer along the way. Now when I suppose p of k is true, I'm assuming then when I write down the first k odd numbers that I'll get k squared. So this means that if I write one plus three plus five up to the kth odd number, well let's see if that was the nth odd number, the kth odd number must be two k minus one and I'm assuming this is equal to k squared because I'm assuming that it is true at the k level. So now I ask is p of k plus one true? Well I don't know, we'll have to find out. What I'm gonna do is write down the first k plus one odd numbers and I'm gonna see if it equals k plus one squared. So let's try that. The first k plus one odd numbers would be one plus three plus five plus. Okay now if I wanna get the k plus first odd number, I think I'll use this formula. If I want the nth odd number I put an n right there and if I want the kth odd number I put a k there and if I want the k plus first odd number I'll put k plus one there. Okay so I'm just substituting in k plus one instead of n and so that makes this the k plus first odd number. I could actually multiply that out and simplify it a little bit. What would I like to show that this is equal to? What am I hoping it's equal to? Although I don't know it yet. K plus one squared? K plus one squared. Okay let me just write that over here. I'm thinking I would like for this to become k plus one squared but I couldn't put that in there yet because I don't know it. I'm trying to prove the proposition is true for k plus one. I tell you what can anyone tell me what was the number that came just before two times k plus one minus one? What, let's see I better make a little bit more room for that. What would come just before this odd number? Two times k minus one. Two times k minus one. Jeff tell us how you decided that. Cause I took the series that we'd been working at in the earlier part there. Up here? Yeah and that's the term that comes right. Before we did up to the k term, now we're doing to the k plus one term. Right, see now if I just plugged in k plus one to get the k plus first term, then the one that I get here should be just plugging a k, not a k plus one. That'll be two k minus one. Now some people at home and maybe some of you might be thinking, I don't know, I didn't quite follow that. This is the right answer but here's another way to look at it. What if I multiply this out? That's two k plus two minus one. Which is two k plus one. Okay now these numbers are increasing by two. So if I wanna go backwards, I should decrease that by two. And if I decrease that by two, I'll have two k minus one instead of two k plus one. So either you can replace the k plus one with a k and you'll find the number just before it. Or you can multiply it out and reduce it by two and you'll get the number just before it. Okay so what I have here is one plus three plus five plus. Now I'm listing the last two numbers of this series, two k plus one. And I went ahead and wrote down that simpler form. Now you know if I put parentheses around this portion, maybe I should say square brackets around this portion. We are assuming we know what that sum is. Because you see that's what appears in my assumption that p of k is true. That one plus three plus five up to two k minus one is k squared. So my assumption is that this is equal to k squared. So I'm just gonna put a k squared right there. And then add on that extra term that I didn't have accounted for. Okay so what I've done is I've replaced this long summation with what I'm assuming it's the, oh two k plus one, thanks. Yeah, so I'm replacing this summation with the k squared that I'm assuming it's equal to. Now if I drop the parentheses there, this is k squared plus two k plus one. And if I factor that, what will I get? k plus one quantity squared. k plus one squared, exactly. And that's what I was hoping that I could make this become. So if I assume that the proposition is true for k, then I've just shown that it's true for k plus one. So in conclusion we can say, so p of k plus one is true also. Of course it's only true if I know that the one just before it is true because I had to make this substitution right here in order to reduce that. Well if you establish a and if you establish b, our conclusion is that this proposition is true for every possible n. So that is for every natural number n or counting number n. So that's how the proof goes. Now this is a little mind-boggling to see this the first time so I think we better work another example. Let's go to the next graphic and we'll see another problem. Okay, this problem says we have one over one times two is a half and then the next row says, the next equation says one over one times two plus one over two times three reduces to be two thirds. And then on the third equation, we have one over one times two plus one over two times three plus one over three times four is three over four. Now do you notice any pattern in, first of all the numbers on the left-hand side, they're all fractions but what about the denominators? What do you notice about them? There's a product of two integers. Product of two consecutive integers, okay. And the numerators are all one. And what is the first number in each product? Let's see, it's a one and then it's a two. In other words, it's sort of the same as the position number. The fraction in the first position begins with one, the fraction in the second position begins with a two. So it's one over one times two plus one over two times three. Does that pattern hold in the third on the third line? See we have three fractions, we have ones in the numerator. And in the denominator, we have a pair of consecutive fractions. And the first number, that is the one on the left, in the pair is the same as the position number. One over one times two, one over two times three, one over three times four. And in the fourth line, I haven't given the answer for that but you notice the pattern continues there. One over one times two plus one over two times three, et cetera, till the last one is one over four times five. Okay now, what's the pattern in the answers on the right-hand side? We have one-half, then we have two-thirds, then we have three-fourths. Do you see any pattern in that? The numerator and the denominator are the two numbers in the denominator or the last term on the left. That's very good. Yeah, you notice that the fraction on the right that represents the sum is a ratio of two consecutive numbers and they happen to be the numbers in the right-hand fraction of the summation, the two numbers in that denominator. One over two, two over three, three over four. So if you were gonna guess an answer to the fourth sum, what would you guess it is? Four over five. Four over five, yeah, because that fourth fraction is one over four times five and if I take the ratio of those two numbers, four over five, that should be the answer. Now, of course, if I actually go back and add up all four of those fractions on the fourth line, I could find out if four over five really is the answer or not, but that wouldn't really do us that much good, so we might establish this pattern one more time if it works. But what we're really wondering is, does this always work even if you have, say, a hundred fractions written across there so that if I wrote a hundred of them, the last fraction would be one over 100 times 101 and the answer should be 100 over 101. Will that work all the time for every natural number or for every positive integer? So what number pattern is suggested here, I think we've decided, but will this always hold? How do I go about tackling a problem that has infinitely many cases that I can't verify individually because there's just not enough time in a lifetime to verify every case separately? So instead, I'm gonna use mathematical induction. Let's come back to the grain board and let's decide what proposition p of n would be in this case. Well, let's see, what we start off with is one over one times two plus one over two times three plus one over three times four, dot, dot, dot.  There's no way I could actually list every one of those fractions because we don't know what the value of n is. But the last fraction should be n times n plus one because we notice that in all of the cases that we had in that example, there was a consecutive pair of integers multiplied together here and the first integer was the same as the position number and this is supposed to be the nth fraction because it's the nth proposition. So it's n times its successor n plus one. Now we are guessing then that the sum of these fractions should be what? What expression? In terms of n, how will I write that? N over n plus one. N over n plus one, yeah. And where I come up with that answer is by looking at the pattern of the examples that we just saw on the previous graphic here. Now, is this always true? That's the question that we're asking here. So there are two things that I have to establish. First of all, I have to establish that p of one is true. And then I have to establish that if p of k is true, that implies that p of k plus one is true. This is where k is a positive integer. Yeah, so I have to establish that the very first case is true and that any time it's true, the one after that will be true. So how do we go about doing that? Well, I don't think it's that difficult to establish a, let's just look at that right here. Proposition p of one would say that if I take the very first fraction, which is one over one times two, that I should get the ratio of one over two. Now, let me ask you, is that true? Yes. Yeah, there's only one fraction to write on the left. So I really can't say that I'm adding up any fractions. There's only one to write down. And if I take the ratio of those two integers in the denominator, one over two, that does give me the answer. That's the pattern that we saw here for the case where n was equal to one. Now, let's go to part b. I'm going to suppose that p of k is true. And what I wanna do is prove that p of k plus one is true. Well, what I say I'm assuming p of k is true, it means I'm assuming that this number relationship is valid for n equals k. So that means I'm assuming that one over one times two plus one over two times three plus up to one over k times k plus one, because we're talking about the proposition k should equal k over k plus one. That's the ratio of these two consecutive integers. Okay, now, we don't have to prove that's true because this is what we're supposing is the proposition for k is true. Now, we ask the question, is the proposition for k plus one true? And you might say, well, I don't know, Dennis, what is proposition for k plus one? Well, that's the proposition that says one over one times two plus one over two times three plus one over three times four plus. Now, if I go to the k plus one fraction, I'm gonna have the product of two consecutive integers on the bottom. What will I put in these two blanks for the k plus first proposition? k plus one times k plus two. Yes, exactly, k plus one, k plus two. And because this is the k plus first fraction, it begins with k plus one. And what are we guessing the answer should be if the proposition is true? k plus one over k plus two. k plus one, right, over k plus two, very good. Now, I don't know if this sum is equal to that or not. So we're gonna have to do a little figuring to determine that. I'll tell you what, what would be the fraction that comes just before this one? I bet there'll be a one in the numerator, what else? k in the denominator would be k times k plus one. k times k plus one. Because you see, if this is the k plus first fraction, this must be the kth fraction, so it's the one that starts off with a k. Now, that's interesting because if I put brackets around this portion, then I have a substitution for that because we're assuming that the proposition for k, or at k is true. And that's the summation that goes up to one over k times k plus one. That's what I have in here. And it's equal to k over k plus one. So I'm gonna take this portion out and substitute k over k plus one. But I still have that extra term to add on. One over k plus one, k plus two. And if I get a common denominator for that, let's see, k plus one times k plus two, what would be the new numerator for the first fraction if I'm trying to get that denominator? What's the new numerator gonna be? k times k plus two. k times k plus two, yeah, because we had to multiply by k plus two on the bottom, we need to multiply by that on top, plus one over k plus one, k plus two. Now, I've gotten a common denominator. If I add those two together, let's see, that'll be k plus one, k plus two. Then I'm gonna have, let's see, k squared plus two k plus one. Now, let's see, how could I factor k squared plus two, k plus one? k plus one squared. That is k plus one squared. Let me just write that up above it. That is k plus one squared. And if I cancel off one of the k plus ones, what I'm left with is k plus one over k plus two. And that's exactly what we said we were gonna predict, that we had predicted we were gonna get, right there. So of course now we're all excited about this. Okay, those of you who can't see them at home, they're all excited about this. So what we've done is we've established the proposition is true for the first case, and for any k for which it is true, the one after that will be true. So in other words, if it's true for one, it must be true for two. But then, wait a minute, if it's true for two, then it must be true for three. And if it's true for three, it must be true for four. It's so all the dominoes fall down, you see. So mathematical induction is a procedure that allows us to take a statement, which has infinitely many variations, varieties, and it gives us a way of establishing that the proposition is true for all those, all those positive integers in that case. Okay, let's go to the next graphic and look at another induction proof, because I think we need to do several of these for everyone to get the hang of how the procedure goes. Okay, in the next problem, it says prove that if you add one squared plus two squared plus three squared plus four squared up to n squared, there's a formula for the sum of the squares, and that is n times n plus one times two n plus one, all over six. So in other words, if you wanna add up consecutive squares beginning with one squared, the little formula on the right, actually it doesn't look so little, it has three different factors in the numerator, but the expression on the right will calculate that sum. Now, at first glance you might think, I don't even know if that's true at all, so let's just take a few cases to kind of get the feel for what that's about. So if you come back to the green board, what if I were to take one squared plus two squared plus three, oh, you know, I ought to write down the general statement first. So the proposition is that one squared plus two squared plus three squared up to n squared, that sum is always equal to something over six. It was n times n plus one times two n plus one, all over six. Now, this seems like this is, this would be too much to believe that we could always find the sum of the squares with a single formula. Let's just take a case. What if I take one squared plus two squared plus three squared? Which proposition would you say that one is that I'm beginning to write down? Is that, this is p sub n, so what I'm beginning to write down here is p of what? p of three, yeah, I'm looking at the case where n is equal to three. And for that case, I should put a three in right here. Well, if I put a three for n, that'll be a three. What will this number be, n plus one? If n is three, it'll be what, Susan? Four. It'll be a four, yeah. And what will the last number be? Seven. Yeah, two times three plus one is seven, okay? Now, let's see, if I can't, here's a 12. If I cancel a six and 12, I get a two. That's gonna be 14. So the formula says this answer's 14. But is it really 14? Well, let's see, one plus four plus nine is 14. Yeah, that really does work. You say, well, okay, Dennis, maybe you got lucky. So it works for the case n equals three, but will it work for the case n equals two or n equals four or n equals seven or n equals 100? In other words, every time I prove one case, you might say yes, but does it work for some other case? So how am I gonna show that this works all the time for every positive integer n? And of course, the answer is to use mathematical induction. So rather than trying to establish an individual case, like the one we just saw, let's show that it'll work for every positive integer. Okay, so there are two things that I have to establish. Who can tell me what's the first thing I'll have to establish? That it works for the first term. For the first term, okay, now that would be when n was one, yeah, because see, n is supposed to be the last square. So if I only wrote down the first term, n would be one, so we should establish the proposition that p of one is true. So I'll put a question mark after that. And then what's the other thing I'll have to establish? This is a little bit more complicated. This is the inductive step. Matt, what were you gonna say? I just said it'll work for every term after n. Well, not after n. After the first one. Okay, well, I wanna show that it works for every term after the first one, but that's not how we worded the inductive step. How did we say it? Better to prove that it's true for p of k. Okay, we have to show that if p of k is true, that that would imply... P of k plus one is true. That p of k plus one is true. So you see why this proposition, calling it p, is kind of a nice notation because this abbreviates writing all that out for the k, at the k level, or the k plus one level. Okay, so let's put our proof right below it here. First of all, I wanna establish that it is true for one. Now, if I write down the first square, well, there it is. And if I substitute in one on the other side, will these be equal? Let's see, one times two times three over six. Yeah, I'm just plugging in a one for n, and I get one times two times three over six. Are those two things equal? Yeah. Yes, they are. One equals one, yeah. Or one equals one. So what we've established here is that p, the proposition at one, is true, yeah. And I'll put an exclamation mark because we're all excited at this moment, okay? Now we come to part b, and in this case, this is a little bit more involved. I'm gonna assume that it's true for p equals k. That is, I'm assuming that the k-th domino has fallen over. The question is, will the domino after that fall over? So I'm gonna suppose that p of k is true. Okay, that is, I'm assuming that if you add up the first k-squares, the first k-squares, that would be one squared plus two squared plus three squared up to k squared. You would get the expression on the right when you substitute k for n. That would be k times k plus one times two k plus one all over six. Okay, so this is something I get for free because it's my assumption. So I'm gonna use that in a moment, and I don't have to prove it because I'm assuming that it's true for the k level. Okay, so we ask the question, is p of k plus one true? Well, let's see, is it true? Well, to find out, I'm gonna add up the first k plus one squares, and I'm gonna see if I get the expression on the right with a k plus one in it. So one squared plus two squared plus three squared up to k plus one squared equals and by the way, while we're at it, what number would come just before k plus one squared? What would come just before that square? Like before three squared is two squared. Before five squared, I bet it's four squared. And before k plus one squared is k squared, yeah. Now, you know, this is the third example, and if you think back to the other examples that I've worked, I've done something like that in every one of these problems. I've written out the k plus first term, but then I backed up and I wrote the term just before it. And I think we'll see why in just a moment. Now, let's see if we can figure out what is the answer we would like to get. If I were to put in a k plus one right here, let's see, this'll be over six. If I put in a k plus one right here, k plus one, what would be the next factor after that? If n is k plus one, then what's n plus one? K plus two. K plus two, very good. K plus two. Okay, and now, this next one's a little tricky. If I put a k plus one right there, what is two times k plus one plus one? Well, let's just work that out. Two times k plus one plus one. How much will that be? Two k plus three. Two k plus three, yeah. That's gonna be two k plus two plus one. So this'll be two k plus three. So this is what I'm wondering if I will get for an answer. Okay, well, let's find out. Can anyone tell me, back here at the original problem, I've included the term just before k plus one squared. What am I gonna do now? Take everything from one squared up to k squared and say that that's all equal to the p to the k. Yeah, let's see, over here, we're assuming that one squared through k squared, that's exactly what Jeff has boxed off there, is equal to this fraction, this rational expression. So let's substitute that in.  No, that's right, plus one. Yeah, the plus three is in that one. All over six. But then we're adding on one more term, k plus one squared. So I'm hoping that I can make this sum add up to be the answer that we're expecting right there. What would you do to simplify that? I'm thinking, why don't we get a common denominator? So let's get it all over six. So this would be k times k plus one, times two k plus one, plus six times k plus one squared. Now, you know, I don't think we'd wanna multiply that all out, that looks kinda complicated, but I think we should factor it. Do you see any common factors in the numerator? Are there any common factors in this expression right here? K plus one. There's a k plus one, so let's factor that out. Okay, you know, this is promising because look at my answer, there's a k plus one factor there. So it looks like maybe we're going in the right direction. Now, what would be left over? Well, I would have k plus one times two k plus one, so let's put that here. No, I'd have, excuse me, I'd have a k times two k plus one. K times two k plus one. And over here, I'd have a six times a k plus one because I've already taken one of the k plus ones out. Okay, so now I think at this point, I will have to factor it, I'll have to multiply it out because I don't see any way I could factor that further.  And then it looks like we're gonna get a k right there and here we're gonna get six k, that's seven k all together. And then we're gonna get a constant term. Now, there's no constants that'll be generated here. What's the constant term that I'll get there? Six plus six. And this is all over six. Okay, now you know what? This binomial factors, and I'm sort of running out of room here, but this factors to be the last two binomials that I have right there. Let's see if I can squeeze this in here. K plus one. And now I wanna factor this quadratic and put it all over six. Now there's a two k squared there, so I figure I'm gonna need a two k and a k. And I need to factor six. Oh, by the way, there's a plus there, that tells me the signs are alike. There are plus in the middles, that tells me one of the signs is positive, so they must both be positive. And then to factor six, I think I'll wanna put a three here and a two there, and that will give me seven k. And that's exactly the answer that I was hoping to arrive at. So therefore, if it's true for one integer, it's true for the next integer. Okay, so we've therefore proven that this proposition is true for every positive integer. Now, let's look at an application of this. I guess you could call this an application. Let's look at the next graphic. The question says, how many blocks are in the array shown if the bottom layer is 100 by 100? Now you notice there's one block on the top layer. How many blocks are on the second layer, assuming that there are no missing blocks underneath? Looks like there are four. And on the next layer, how many blocks on the third layer down? Nine. Nine. So, and then the next one that we see is four by four, 16. So we've got one block plus four blocks plus nine blocks plus 16 blocks all the way down to 100 by 100. Now, if I were to write those as squares, I think I could write them this way. Let's just come back to the board here and figure out how many blocks there are in that array. Of course, the array's bigger than we can actually see on the graphic, but you get the idea of what it looks like. So, on the very top, we had one squared, and then just below it, we had four blocks, that's two squared. And then just below that, we had a three by three array, nine blocks, that's three squared. And we keep on going until we get to the very bottom layer and we said that was 100 by 100, that's 100 squared. So how many blocks are there? Well, of course, one way to do it would be to multiply all those out. There'd be 100 numbers there then to add up. That would take quite a while to do it. What would be a shortcut for answering that question? Use our formula that we've derived. Yeah, we work so hard to derive this formula, we ought to at least use it now. What would you substitute for N? 100. Yeah, it looks like N is 100. So if I substitute 100, that's 100 times 101 times, what's the last number? 201. 201. Now, you might think that when you divide by six, you might say, well, Dennis, it seems like there would be some times when this six may not cancel. And if the six doesn't cancel, you're gonna get a fraction for the answer.  Well, you know, this six will always cancel. That's what we've just proven in our inductive proof, our mathematical induction proof, is that this always reduces to whatever the sum is and this sum is an integer, so the six has to cancel. For one thing, you notice these are both, these are consecutive integers, so one of them has to be even, the other one's odd. So that means the two and the six is gonna cancel there. And one of these three numbers has to be a multiple of three. That's not necessarily obvious, but one of them will be. So let's see, if I cancel the two with the 100, I'll make that 50, and which one of those numbers is divisible by three? 201. 201, if I cancel the three with the 201, that'll be 67. So this answer is gonna be 50 times 101 times 67. Now tell you what, can anyone tell me what is 67 times 101? It has a nice pattern to it. 67 times 101. 6,700 and 67. Yeah, it's 6767. You see, 67 times one is 67, and then 67 times 100 is 6,700. So it's 6767. Then if I multiply 50 times that, this number's gonna end in a zero, and now let's just multiply by five. Five times seven is 35, carry a three. Five times six is 30, that makes 33, carry a three. Five times seven's 35, we carry to three, makes it 38. And then five times six is 30, and we carry to three, makes it 33. So we get 338,350. So there are almost a third of a million, or over a third of a million blocks in that display if the bottom layer is 100 by 100. So I've been able to find the number of blocks in the array without actually adding up all those numbers individually but using my shortcut formula. Okay, let's see. I think we should skip the next graphic and the one after that, and let's move along to some of the later graphics so we don't miss, so we don't lose too much time here. On the next graphic, we have a question, which is larger, n squared, or two to the n if n is a whole number? Now you know, n squared grows very rapidly but two to the n grows rapidly as n gets bigger. So which one is larger? And then we're supposed to prove our answer. Well, you know to decide, I think what we should do is just sort of investigate it for a few cases. So what if I make a table and we'll put in, and we'll put n squared and we'll put two to the n power? And let's say the question asked about whole numbers. Now whole numbers include zero as well as positive integers. So let's just list a few cases here. Zero through five, we could put down some more if we need them. Well, n squared would be zero, what would be two to the zero? One. Would be one, okay? It looks like two to the n's bigger than n squared. So do you think that's enough to decide, okay, two to the n's always gonna be bigger than n squared? Sure. Stephen says sure, but I think Stephen's wrong. Yeah, that's only one k, so let's go further. What if I plug in a one? One squared is one and two to the first, two to the first is two. Yeah, so far it looks like two to the n's bigger than two squared. And what if I substitute n equals two? What'll be n squared? Four. Four, and what's two to the second? Four. Four, oh now wait a minute, here they're equal, so two to the n isn't bigger. And what happens for three? What's three squared? Nine. Nine, and two to the third is eight. So now suddenly n squared's bigger than eight. So I guess from now on, the square is bigger than the exponential, but maybe we ought to check a few more cases. What's four squared? 16. And what's two to the fourth power? 16. 16, so wait a minute, now they're equal again. So it looks like this thing is sort of fickle, it's going back and forth. Let's go to five, how about five squared is 25. What's two to the fifth power? 64. No, not 64. 34, 32. 32, yeah if you just double the last number, see we put in one more two, that'll be a 32. Maybe we should go just a few more cases, let's try six and seven. Six squared is 36. And two to the sixth is 64. And seven squared is 49. And two to the seventh is 128. What do you think's gonna happen from here on out? Two to the n's gonna be bigger. Looks like two to the n's gonna be bigger. So it looks like from this point on, two to the n is bigger than n squared. So we now have something we'd like to prove. And the question then is to prove that n squared is less than two to the n if n is, if n is five or larger, if n is greater than or equal to five. And by the way, I'm assuming n here is a positive integer now, not just a fraction or a decimal, but we're talking about positive integers in this case. So in other words, in these first five cases, we had some waffling back and forth. But we're guessing that from five on, the two to the n's gonna be bigger. So to prove this, I have to show two things. I have to show that the proposition here, this being the proposition, is true for the smallest case. Now in this case, what's the smallest value of n? Five. It's five, okay? So I have to prove that p at five is true. Not p at one, because p at one in two and three and four, those are cases that we all eliminated earlier. And then I have to show that if the proposition is true for k, then it's true for k plus one. Now this is gonna take a little bit different argument, I think, than what we saw in the first examples. So let's see if we can establish part A. P at five. Well, if I plug in a five, five squared is less than two to the fifth, because that's 25 is less than 32. So what that tells me is the proposition is true for five. Yeah, so we have that first part established. Okay, let's go to part B. In this case, I'm gonna assume that the proposition is true for k, so let's say suppose p, k is true. And what that means is I'm assuming that k squared is less than two to the k. Now what I wanna do is to prove that proposition k plus one is true, p of k plus one. So we must show p of k plus one true. Now let's see, what that would say then is I wanna prove that k plus one squared is less than two to the k plus one. So let's write down k plus one squared. And somehow I want that to be less than two to the k plus one, so I'll just make a note of that. That's what I'd like to get on the other side. Well, if I expand this, this is k squared plus two k plus one. Now I tell you what, I'm gonna take out pieces of this and replace them with things that are larger. For example, what do I know is larger than k squared? How about two to the k? We know that's larger, that's our assumption. I'll put two to the k there. And while I'm at it, I'm gonna take out the one and I'm gonna replace it with another two k. I think we can all agree that two k is bigger than one because we know that k, that k is at least five or larger, so two k is certainly bigger than one. Now what that means, this expression equals is two k, two to the k plus four k.  Something bigger than four is k. Yeah, because k is at least five, so I can replace four with k. And so that gives me two to the k plus k squared. Okay, now let's take out the k squared and put something even bigger than that. What's bigger than k squared? How about two to the k again? Yeah, we've already done that once. So I'm gonna replace this with two to the k plus two to the k. Now you know what I have then is two times two to the k. And I have the same base, so I should add exponents. And if I add exponents, that's two to the what? K plus one? Two to the k plus one. And why are we all excited? Why is Dennis all excited? Because on the other side was k plus one squared. And now that's exactly what we wanted to get. We wanted to get two to the k plus one. Now this took quite a bit of maneuvering to replace individual terms with things that were larger to get to this final answer. But we've been able to make k plus one squared less than two to the k plus one. So what we've proven is that over here in our chart for all the cases five and larger, two to the n is bigger than n squared for every other case after that. Now we noticed there was a little bit of movement back and forth in the early stages. But when we got to the point where we thought it would always be true, then we went to our inductive argument in that case. Okay, let's go to the last graphic on the Fibonacci sequence and let me just mention a few things about that. And I'm gonna go over here to the green screen again. You remember the Fibonacci sequence? If you come to the green screen, let me just refresh everyone's memory of how this goes. In the Fibonacci sequence, we started off with two ones. And then how did we get all the terms after that? You add on the two previous terms to get the new term. You add the two previous terms, like one plus one is two. One plus two is three. Two plus three is five. What would be the next term after that? Eight. Eight, okay. Now in this graphic, I'm calling the first number f sub one to mean Fibonacci number number one.  So for example, f sub three is really two. It's just this is an abbreviation for that. Now if we go back to the graphic, we'll see some properties of the Fibonacci sequence that can be established by induction. A few of the curious properties of the Fibonacci sequence, f one, f two, f three, et cetera, f sub n, and then keep on going. Well, you may not have been aware of this, but if you add up the first n numbers of the Fibonacci sequence, you get the number two steps later minus one. Yeah, let's come back to the green screen and let me demonstrate that. What if I add up the first two numbers of the Fibonacci sequence, one and one? I get the number two steps later minus one. Yeah, one and one is two and three minus one is two. What if I add up the first three numbers, one and one and two? How much is that? Four. It's four. And look, if I skip over two places, that's five minus one. What if I add up the first four numbers in the Fibonacci sequence? I get seven and that's eight minus one. So as a general rule, if we go back to the graphic again one more time, if you add up the first n numbers of the Fibonacci sequence, you get the number two steps later minus one. Now to prove that you use induction. If I had time, I would prove that now, but I think I'll just state it and I'll leave it to you to think about. Now in the second line, it says if you add up every other Fibonacci number, beginning with the first one, the first, the third, the fifth, up to F sub two n minus one, remember two n minus one is odd, we get F sub two n, which is the very next Fibonacci number. And by the way, if you look at the last line, it says if you add up the squares of the Fibonacci numbers, you get the product of the last number and the one right after that. Hey, I think we're out of time. Thanks for watching and we'll see you next time.


Let's give Rowan a first time speaker a big round of applause. You get to keep one. Have a good time. Thanks. Hi, so my name is Rowan. I'm an undergrad at the University of Washington and last time I was doing research into using Thinsims to break mobile money applications. So first, what are mobile money applications? So, if you've ever used Venmo, then you've probably used a mobile money application. The basic idea is you have a balance that you can load money into, and it's usually some form of app, then you can transfer that money to other people and make payments through that way. Now, the ones you've probably seen all run on smartphones, but it's possible to run these things on the SIM card of a phone or over other means. So they're actually very widely used. So there are almost 700 million accounts worldwide, 276 deployments in 90 countries, and transfers that were a billion dollars a day. Now, a lot of these users don't transfer very much money, though. It's $188 a month, which, on average, and that's because they live in places where they don't make much money. So these applications are very widely used in places like Africa and Southeast Asia for people who don't have access to banks. And the reason why they'd be using this over banks is that banks are a lot rarer, and so here you can see there's roughly 500,000 banks in developing countries, whereas there's 2.2 million mobile money agents. So all you need to be a mobile money agent is just have phone and have access to cash. So the infrastructure required is a lot lower. So it's a lot easier to get access to it. So if you're a farmer and the nearest bank is a couple of villages away, you probably would not have a bank account with a bank because it's going to take too long to get there. And so the only way you could store your money is by trying to keep it safe somewhere, so maybe burying it at the ground, and that has its own issues, like maybe you lose it, gets stolen. So mobile money is actually a really useful tool for these people to try and be more financially secure. And so it doesn't only run over smartphone apps. The most popular interface is USSD. I'll explain what that is later on. Then there's smartphone apps. Then there's SimToolkit apps, which run on SimCard. I'll explain those as well. And then there's IVR. So the interface is offered by these platforms. So most of them offer USSD. So this is the trade-offs between the different forms of applications. So you've got smartphone apps, which everyone knows what a smartphone app is. It's got a very rich UI. It's very easy to develop for this existing development environments. It does not require any cooperation from the phone company. You can just load an app on your phone, start running it. It needs a data connection, which can be a bit difficult to get in some areas, and also requires a smartphone, of course, which comes with its own host of issues. Which means, you know, then you have to be able to charge it every day. They're fragile. If you break the screen, that's a big problem. So they're not so useful in these environments, since most people also don't have smartphones, because they cost money. So then you've got SimToolkit apps. Now, these run on any hardware. So that's good. They also don't require a data connection. They usually use SMS as a backhaul or as a connection back to the service to make things happen. They've got a menu-based UI, so it's visual. It still requires a lot of cooperation from the phone company though, because the application needs to be on the SIM card. So you also need a special SIM card that has the application preloaded. And this can be difficult if, for example, you are not the phone company, and trying to convince them to put the app on the phone. And then there's USSD, which runs on any phone. Again, it's built into the GSM standards. It does not require any special SIM card. It's got a very standardized UI. It doesn't require data. It still requires carrier cooperation, because the phone company has to set up the gateway to allow your application to actually run and give you the number for people to call. However, it only provides a text-only interface. In experience though, people don't seem to care about this. They don't mind using text-only. They've figured out how to use it in a very fast and efficient manner. So we all know what SIM cards are to some degree, but just to go over it, they identify you still in the network. They can authenticate devices on the network. They can do call control, which again I'll explain later, and they can run the SIM toolkit applications, among other things. So SIM toolkit applications run on the SIM card. They consist of menus and input prompts. They can also send SMS, place calls, which cell tower you're talking to, get the phone's IMEI, which is equipment identifier, and a few other things as well. It's defined by a GSM standard as well. So this is an example of what they look like. So on the left you have a SIM toolkit app running on a smartphone. So you can see you've got menus, you tap on a menu, and then it might pop up a prompt asking you for text. And then on the right you've got it running on a feature phone or a basic phone. And so then it's still got very similar UI, except you just navigate it with the keypad. So this is an example of message flow from mobile money application. It's a little modified, but the idea still stands. So what you can see is that ME is mobile equipment, so that's the user's phone, and the SIM card is the SIM card. So what you can see is that all messages always start from the phone and then get sent to the SIM card. So here you can see the phone is telling the SIM card that someone entered into an application with this ID. The SIM card then says, great, select an item from this menu. The phone says, here this is what they selected. The SIM card then asks for the user's pin, the user provides a pin. The SIM card will then go and connect to the network and make the payment go through. In this case, it's just hand-wavy, but usually this is done through some form of encrypted SMS. And then the SIM card will then display the balanced user and the user will terminate the session. So this is what the messages look like. To TLV, you've got the tag, the length of the body and then the values. So the SIM toolkit commands always start with the D0 and then the length. Then you've got the command details tag, so this will tell you what command is being sent. Then you've got the device identity tag, which I feel is a bit redundant because you can already figure that out from the command details tag, but it basically just tells the phone where the message is coming from and where it's going. And then you've got various tags associated with that type of message. So here you've got a text string tag. This is just saying that they're trying, this is just by texting the screen basically. So then you've got USSD or Unstructured Supplementary Services Data. So it's dialed like a voice number. No record is stored on the device, however. So while you would dial it with the same phone application that you would usually use to say call someone, usually there's a call log associated with that. So you can go back and see which numbers you've dialed before. USSD doesn't have that, so there's no way of going back and checking which USSD number someone has dialed. It provides text on the interface, and here you can see it running on a smartphone. This is an application we were using for testing. So this is the format that the numbers are in. So it always starts with a star and the numbers and a pound, then a pound sign. So the first one would just connect you straight to the service. Now if you know the service always pops up the same menu when you get there, and you know you want to enter in one in the first screen, then you can actually just append star one to the number. And then that means it'll enter in one at the first menu prompt and it'll skip straight to the second one, assuming one is valid input for that. And you can chain this many layers deep as you want. You'll get stuck though if you make a mistake and then it will repeatedly try the subsequent numbers on the same screen, which can lead to unexpected behaviour. But you can chain it as many layers deep. So in theory you can do an entire transaction of going through many, many screens just in one command. And this is how most users end up using this service. So now for thin sims, which is what we were actually using in this to do these attacks. So you can see they're very thin devices, they go between the SIM card and the phone. I have some, people want to have a look at them later, but can't really hand them around. So they fit any size SIM card. So you can see we've got the ones on the left are the ones that we were using for testing. They require cutting out a corner of the SIM card and as such they can end up used with mini sims. The ones on the right, you see they've got different, they're much smaller and so they can work on both nano and micro sims as well as mini sims. So they're field installable. This means anyone can install it. You don't need specialised equipment. It's kind of like a screen protector in terms of installation process for some. Then they contain all the functionality of a SIM card. I mean they're just running code so you can write anything you want onto it. They're free from carrier restrictions and therefore they allow third party applications. This is also useful because the phone company isn't the one putting it in. You can put any thin SIM you want into your phone and then they can read and modify all the communication between the SIM card and the phone because they're sitting on the interface. So the original use case for these was cell phone unlocking. So back when you had a GSM phone that locked to a network, you could put a thin SIM into it and be able to use the phone on any network. Which was very useful. Then the other use case we've seen is distribution of apps. We'll talk about an example of that as well later on. For example, if you're a company trying to put an application into a SIM card and the phone company doesn't want you to put it on, then you can use a thin SIM to get around that. Finally, there's the case of distribution. This would be most of these attacks involved being able to steal money from other money applications.  Not recommending this by the way. Let's look at M-Pesa. M-Pesa was founded by Safari Common 2007. The original way it was founded was that they would charge codes that would add balance into their accounts. They would buy these codes and then send them around as a form of payment. In a change of services, you would then send someone say a $10 recharge code that they could either reply to their account for $10 of airtime or sell on to someone else. Eventually, someone might sell it back to a shopkeeper who would sell it to another user. Eventually, Safari Common realised this and which was a mobile money application and cut all this out of the loop and make it a lot more streamlined and safe for the users. Today, it transfers 24% of the Canadian GDP each year. It's very widely used. It's expanded to many other countries and it definitely runs over SIM toolkit application. It's not necessarily currently the primary way it runs but it's definitely run over that in the past. Then EquityBank came along in 2015. They wanted to run their own mobile money application. They came along and because they wanted more people to be able to use it, they couldn't run it on a smartphone app. They needed to use either a USSD or a SIM toolkit and for whatever reason they decided to run it on a SIM toolkit application. Unfortunately, Safari Common had 80 or 90% of the market share and of course they didn't want to put a competing market share on it. So as a result, they forced EquityBank to try and distribute their app as a thin SIM. So there was a court case about this with Safari Common trying to stop them from doing this. The court eventually allowed them to do it but there was very little, no one really looked into the security implications of this. So here you can see a phone with a thin SIM installed and an app running on the thin SIM. So you notice that this is all fine, no data is really at risk here. Then when you've got application running a SIM card however, this diagram makes it look like the data is traveling from the phone to the SIM card. But really what's happening is it's being sent from the phone to the thin SIM. The thin SIM is then deciding to forward it onto the phone and then the SIM card can process the data and send it back. But the thin SIM is processing all the data as it goes through. So there's probably some fun things. What if the thin SIM is not friendly? What if there's some malicious code on it? So there's a lot of things that the thin SIM can do. Let's just look at the first three for the first attack. So this is the ability to intercept, modify and create SIM toolkit commands, then view the response to those commands in plain text and then the ability to send SMS messages without notifying the user. So this attack was primarily targeted at the SIM PASA SIM toolkit application because we needed a target platform. We also did some testing against air teller and some modifications just because it's got a different menu structure. It would work against that as well and probably any other SIM toolkit based mobile money platform. So the attack takes place in two phases. You've got first we steal the credentials and then we actually make the fraudulent payments. So you've got the phone, the thin SIM and the SIM card. So initially there's a transparent and the user is using the SIM toolkit app and it's completely it's not clear at all there's a thin SIM installed, they can't tell. They're just using the SIM toolkit app on the SIM card everything's normal. Eventually the app will ask the user for a pin and at this point the thin SIM will start listening then the user will respond with the pin and the thin SIM stores the response. At this point the thin SIM is stored their credentials for later use or anything about it. So then we have demo. So this is me entering into the Mpacer app. So first I check to see there's no so let me just start this again. So what I'm going to do is first verify there's no pin stored then enter into the Mpacer app try and check my balance and then view the pin afterwards to show that it's captioned. Now unfortunately they don't use them for too long they become they're no longer active and so this one we didn't use for too long and as a result it can't actually send SMS messages but the attack still proves the first half of the attack. So here I go and view the pin that is stored it says no pin is captioned. So then I go into the Mpacer app navigate through some menus check the balance it then asks for the pin says okay and then it fails to send the SMS because it's not active on network exit out view the pin and now we have the pin stored. So back to slides. Okay so now for phase two this is where we actually go and make the fraudulent payment. So again you've got the phone, the thin sim and the SIM card. Now these status updates are sent roughly every 30 seconds from the phone to the SIM card. We're just using this as a way to trigger the attack although it could be triggered through various other means. So once the thin sim decides it wants to start the attack it then begins a transaction it begins a sim toolkit session with the SIM card. In this session it goes and sends all the data required to initiate a transaction. The data sent is exactly the same data that the SIM card would expect to see if the use was interacting with the SIM card. Eventually the SIM card will then try and contact the network. This is via sending an SMS. Now usually this would pop up a notification on the screen. However that would tell the user something weird is happening and they might be able to try and stop what is going on. So let's see if there's a way around that. So here you can see this was one frame taken out of the previous video. So the SIM card was active it would have been more obvious what was going on but here you can see that there is a message at the bottom telling the user that the application is sending an SMS. Now the application can specify the string. So here we've got the message that was actually sent. The SIM card sent to the phone to make this SMS happen. So you've got all the stuff at the start with the command details and the device I don't need. And then you've got this text string and this is what is actually displayed to the user followed by the SMS TPTDU which is the body of the SMS and where it's going and all those boring things. So how can we make this go away? Now you might think oh let's just remove the text string and maybe it will disappear. Well unfortunately that leaves up to the phone to decide whether it wants to send, display something to the user and most phones will display something to the user telling them that an SMS is being sent. But however if you just give it a null string so just tell you've got a string of zero length nothing shows up and so then you can send an SMS without the user seeing anything. So that's what we do. So if we go right back the SIM card is trying to send an SMS the thin SIM takes the message removes the bytes that would make something show up on the screen replace it with a zero length string and then sends a silent SMS that doesn't show up to the user. So what this looks like so let's start again. Alright so what this looks like to the user is just verify we've got the pin stored and then we start the attack then the user won't see anything unfortunately because the SIM card is not active it will still show the failed send SMS but the other messages didn't pop up ahead of time it's there in the it's there in the logs and the ability to send silent messages is shown in another demo as well. So that's that's the oh no. So at this point we've successfully done the transaction and there's no indication to use that the money has gone anywhere or anything's happened really at all. Cool so let's go back to the list of capabilities we have. So we've already used the first three so let's look at the next two. So the ability to log in redirect calls both for voice and usd and the ability to make usd calls and the ability to use it. So this is done by call control so what call control is is whenever you dial a number to call on your phone first the phone will actually ask the SIM card so say you then ask the phone ask the SIM card hey can I call this number and the SIM card will respond yes sure here you go you can call the number however the phone the SIM card can also say no you can't call that number and just deny it outright or it can modify the call and say sure you can call a number for this one instead. Now interestingly for voice calls depending on the phone this mail may not show up and the call log is being redirected on the android phone we had it did show up as being redirected however on the feature phone we were testing on from 2005 was running some windows operating system it didn't show up and it showed the original phone number so this doesn't sound too bad right we can just it's just messing with what people are calling with this because usd is not usually tracked maybe you're using a usd service that you wouldn't want other people to know you're using for whatever reason so if you had a thin SIM installed that was looking at call control it would then be able to see who you're calling which can then be used for advertising surveillance blackmail whatever you want it could also use the phishing attacks if you're ever trying to set up a fake customer support line and trying to get someone to call it this makes it a lot easier you just make them call the original customer support number it redirects to your own number and then you can get away with whatever social engineering attacks you're trying to do you could also route all their calls through some premium number and just make their phone bill go really high and charge them a lot of money that way of course it would be a premium number that you own so you get the money for it or you could redirect to usd calls let's see what happens if we do that so for the usd attack it takes place in two phases however this requires attackers to set up their own usd service which the other one didn't require the attackers to set anything up and depending on the country setting up a usd service can be anywhere from easy to almost impossible for example in the US no one really uses usd I've never seen any usd sessions the closest I've seen is for example the AT&T your dial star, data pound and then it will send you an sms back with the data usage you've got for that month so this is the setup we had so we've got laptop running the osmocom network in a box which is a cell software a cell tower software unfortunately no out of the box cell phone software I could find was open source had functioning usd capabilities so we had to modify it a bit with various patches from various years it worked in the end then we've got usrb b210 which is actually the radio we're using then you can see we've got a phone sitting there with a development module thin sim plugged into the back of it and then a debugger attached so I can view the messages that are actually being sent between the phone and the sim card for debugging purposes so here you've got a phone, the two services you've got the legitimate one that the user is trying to access the attacker service that they've set up and then you've got the thin sim the next thing the user is going to try and do is they're going to try and dial the number for the legitimate service now this initiates call control tries to ask the sim card cannot dial this number however because there's a thin sim installed the thin sim intercepts that and decides to redirect it somewhere else so it then gets redirected to the attacker service now the attacker service will mimic all the menus for the legitimate service perfectly so the user will go through all the menus they're expecting to go through and entering all the payment details however right before the very end of the message, right before the very end of the transaction that would actually send the money the attacker service will return an error because it can't actually make the transaction go through the user will likely interpret this as some kind of network connectivity issue and try again later at which point it would go through with no issues so we have a demo of that as well so in this demo I'm going to dial the number for our usd service and then it will redirect it to the attacker service so now I'm dialing for the legitimate service it gets redirected without telling the user anything so we go through and then enter into check and balance so we type 1 press ok so then ask the pin error could try again later so we exit out of this just mute that to try again I don't know why it takes so long to access the usd service it really shouldn't but it does send me growth room and we try to check the balance again so we enter in 1 check balance again we go and enter in the pin and now we actually get the balance so notice this is 9001 so over 9000 ok so that's the demo of phase 1 so then in phase 2 we actually go and try and steal the money so again this is triggered through some means in this case we just triggered it through a menu item in the simtokit application however again it could be triggered through a status update or something of the like so first the thin symbol call the attacker service because it needs to get the pin back so we call the attacker service and get the retrieved the pin so then it gets the pin back and then it will actually make the transaction so what it does here is it strings together the entire command it would need to do so it would be like star 1 2 3 star 2 to make transaction star and then the destination phone number another star then the amount that trying to send star 1 for confirm star and then the pin and then pound that's the string we need for this service in particular so we have a demo of that we go into the simtokit application so we select send usd it waits for a while because there's no it doesn't display to the user anything is happening usually it would but we've made it silent so now let's go and check let's check the balance to see that we've actually sent some money somewhere so now we go through and actually go and check balance enter in the pin again and now the balance is much lower this is sending a bit over 600 current units of currency somewhere to another account so at that point there's not really a lot the user could do the money has disappeared by the time they notice it's probably been shifted to another account or cashed out of the network so that there's no there's no method to recourse and customer service in these places often not so great so there's very little chance of users getting the money back so there are a couple more capabilities I didn't really talk about ability to track location updates so this is what telltale the user is talking to you could make some like some snooping software to track users doing that there's gsm authentication this is not really so much an attack but you can use it if you know the imzi of the device of another user and the key for the network you can then pretend to be that user and then you can read any data off the sim card including the imzi and the phone book that's stored there also in the gsm standards it allows phones to store sms messages on the sim card and in the case where that message is being stored on the sim card the thin sim would be able to read those as well as they went past so let's look at some possible defenses now so you could disable call control this would get rid of all the call control based attacks as well as the usd based attack because you simply if you can't redirect the call the attack is completely impossible however that requires modifying the phone standards and then updating all the phones which is not really going to happen because a lot of the users who would be affected by this don't have data and if they have data they want to use it for facebook and whatsapp that's what they're going to use it for and so they're not going to install apps they're not going to install updates it's probably not necessarily possible to install for updates over the air for these devices as well not all the companies that made the devices or even still around necessarily so then there's the ability to then disabling silent outgoing sms and usd well this wouldn't actually prevent the attacks all it would do is prevent the notification is make it clear to the user that something bad is happening now again unfortunately this requires modifying the standard and has all the associated difficulties so phone companies to put third party apps onto their sim cards this would then require a lot of cooperation from phone companies who may not want to cooperate and may have financial incentives not to cooperate in the case of safari comp this would at least make thin sims not normalize so if someone saw a thin sim at least then they would be very suspicious of what's going on you could use confirmation codes so if a sim took it in usd after the transaction has gone through then the user would have to enter in that confirmation code in order to verify the transaction and make it go through this works great for phones where the sms message is not stored on the sim card but if it's stored on the sim card then thin sim has access to it and so this is completely useless for those devices I don't know how many devices out there have that functionality so I don't know and for usd you could require the user to enter in confirmation value on the screen so this doesn't work because it needs to talk to the network but the essential idea is that once you start the usd session there's no indication the sim card can't interact with it anymore so if the session completes and gets to the end without having to require any more input the sim card then does get the response the final response that is sent back but if it needs more input it will then ask the user for it and there's a prompt that shows up so what this would mean is that the thin sim would not be able to completely predict the message that it would need to send and something would show up on the user's screen it would allow them to then deny the payment deny the transaction and stop anything from happening so this would be quite effective and finally it's a plain text interface and well there is actually a standard for that however of course no one implements this standard that would be too sensible yeah it's been around for many years but there's no implementation of it so there's a link to the paper that I use that was written for this presented at conference in June and then there's a couple of standards that there are does anyone have any questions if you buy your own sim card I mean you would so as a note for seeing those of the sim card yeah if you look at your sim card it would be very clear if there's a thin sim installed or not it's very obvious yeah however the interesting note it might be possible to do all these attacks if you actually had software running on the sim card itself so if you had supply chain issues for example you might also not be safe yep the I don't believe it's possible to get the key off the sim card if it was possible a thin sim might be able to do it um yeah it's not really something we looked into what else cool thank you


Another important type of equation in mathematics is called an absolute value equation, and this is an equation that involves an absolute value. Now there's a number of ways of solving these equations, but here's one way that's a very nice approach that relies on a connection between algebra and geometry, and it's really helpful to make the following identification. The absolute difference between two numbers A and B, which we're going to write as the absolute value of A minus B, is the distance between A and B on the number line. Now you might have been told that the absolute value represents the distance from zero, and that's true, and it's part of a more general concept that the absolute value in general tells you the distance between two things. So the absolute difference is the absolute value of A minus B is the distance between A and B. So let's take a look at that. So here's the number line, and I've marked a couple of points on that, and let's see if we can find which of these quantities is going to be greater. So let's take a look at that individually. So again, the key here is we want to identify the absolute difference. The absolute value of A minus B is the distance between A and B on the number line. And if we can interpret it this way, if we can locate where A and B are, we can see geometrically what that distance is going to be. So in that first case, this absolute value of Y minus Z, well, that's the distance between Y and Z on the number line. And if only I knew where Y and Z were located, I could plot them and I can represent what that distance is. Oh, wait, here it is. Here we know where Y is because we've been given that information. We know where Z is because we've been given that information. So we can actually identify what that distance is. So I'll go ahead and put my number line down. Here's Y, here's Z. The distance between them, the absolute value of Y minus Z, well, I'm going to represent that using this little blue bar here. And likewise, this absolute value minus 3, minus 5, that's the distance between negative 3 and 5. Well, here's negative 3, here's 5. And I can represent that distance as this bar that runs from negative 3 up to 5. And now I have the very difficult task of figuring out which two of these is bigger. Oh, wait, I can use the geometry. Here's an important lesson. A lot of problems in algebra can be reduced to a problem in geometry. And in general, one of those two representations will be far easier to work with. With absolute value, it's very frequent with the geometric representation that's easier to work with. And I can look at these and say this absolute difference Y minus Z is clearly less than the absolute difference negative 3, minus 5.  Now, that doesn't mean that sometimes we need a little bit of help to see that absolute value of X, absolute value of Y plus 3. Well, the important thing here is to view any absolute value expression as a difference, as a distance between two points. And so I can view X as, well, I can always subtract 0. This is X minus 0. This is the distance between X and 0. And I know where X is. I know where 0 is. And so I can graph what that X minus 0 is going to be here. Absolute value of X minus 0, distance between X and 0. It's this about here. And again, you might remember from your definitions of absolute value way back when that we defined absolute values the distance of a point from 0. And again, it's part of a more general concept. So Y plus 3, we have to do a little bit of algebraic manipulation. But here, I need a subtraction Y plus 3. Well, I can change that to Y minus negative 3. And again, I can change in addition to minus the additive inverse. So this is Y minus negative 3. And again, as an absolute value, as an absolute difference, this is the distance between Y and negative 3. Well, I know where Y is. I know where negative 3 is. So I can represent this distance geometrically by this bar here. And I now have that task of deciding which of these two is bigger. This distance here, representing the absolute value of X, or this distance here, representing the absolute value of Y plus 3. And again, the geometry is much easier to work with. The absolute value of X is definitely greater than the absolute value of Y plus 3. Well, what if I want to solve some equations? For example, let's take a look at absolute value of 2 minus X equal to 3. Well, again, I can view the absolute value of 2 minus X. Well, this is the distance between 2 and X. So let's see. Well, the equation says that the distance between 2 and X is going to be 3. Well, let's go ahead and plot that on the number line. Now, I know where 2 is. I don't know where X is, but I know where 2 is. And I can place that on the number line. So there's 2. And we want to place X the distance between 2 and X is going to be 3. So I want to place X. So it's 3 away from 2. And here's the important thing to remember when dealing with an absolute value equation. In general, my location can be in one of two places. So it's possible that X is 3 more than 2. So here, the distance between X and 2 is 3. The other possibility is that X might be less than 2. So, again, here, the distance between X and 2, this distance is going to be 3 as well. So I know that X is in one of these two places. And now I have the very difficult task of figuring out what X is. Well, if X is over here, X is 3 more than 2, well, it must be that this location here must be 5. And so X and 5 are the same thing. So I could say X equals 5. Or if I'm back here, if I'm 3 less than 2, I have the very difficult task of figuring out where this is. If X is 3 less than 2, well, that's going to put me at negative 1. And so 3 back from 2, that's at negative 1. And there, X is. And X and negative 1 have to be the same thing. Well, how about a more complicated absolute value expression? The key here is that what we have is an interpretation for what the absolute value is.  So let's arrange our equation so we can conclude something about a distance. So let's see. I have absolute value 2X plus 5 minus 4. And so I'll add forward both sides to make this an absolute value on the left and just 4 on the right. And what this tells me is 2X plus 5 equals 4. And again, I'll change that addition into the subtraction of a negative. So 2 plus 2X plus 5, 2X minus negative 5. And again, what this tells me is that the absolute difference between 2X and negative 5, that distance is equal to 4. And so, well, I don't know X, so I don't know where 2X is. But I do know where negative 5 is. So I can put 5 negative 5 on the number line. And I know that wherever 2X is, the distance to negative 5 is going to be equal to 4. So I want to put 2X so that it's 4 away from negative 5. So 2X is either up here or above negative 5, and it's down here below negative 5. And so let's see. If I go from negative 5 up 4, I'll get to 2X. Well, that's going to take me to negative 1. Or if I go down 4, that's going to take me to 2X, but that will also take me down to negative 9. So I have 2X is at the same place that negative 9 is. 2X is at the same place negative 1 is. There's another equation. And so that tells me that X is either equal to negative 1 half, which is what I'll get by solving that first equation. Or X2X is negative 9, so that tells me that X is going to be equal to negative 9 halves, which is what I get from solving that second equation.