I've got a great job offer for you. You can even choose the salary plan. You can get a £100 on the first day and each day you work, you get £50 more than the day before. Or a different plan, I double your salary every day but you start on one pound on day one. The question is, how long do you want to work for us and what payment plan do you want? Is that too good to be true? It's just a story I know. But we can still look at the figures. Have you made a decision? How do we actually decide? You could get your spreadsheet out and try it, I'll get mine. Let's put in all the data from these payment plans. So, I've got a column here for the days of work, and the first payment plan and the second payment plan. So, first payment plan, we start with a £100 on day one, and on the second day is the payments we had on the previous day with extra £50 on top. So, that means we get 150 on day two, 200 on day three, 250 on day four, and so on. So, we got all of that. Let's see how many days we need but will put 28 for now. Now, on the second option, you start on one pound. So, we start on one pound and on the second day, we go with doubling what we earned on the previous day. We carry on in that fashion so we're going to double. Now, it's that good table to help us make a decision? Let's see. We're earning really low amount on the second payment plan. We got one pound, two pounds, four pounds. Day eight, we are in £128, not bad and it keeps doubling so we're just making really serious money on day 10 and it looks like we're catching up with the £550 we get on a first payment plan. So, how many days should I work? On day 11, I'm already earning more on the second plan than on the first. Is that how I should make my decision? Yes, I can hear you screaming there. It's not enough just to compare that. We need to say how much money do you make in total. We will need to tally up all of this. So, let's do that. We have that value and then the new one, let's add up and we just adding up the money you've earned up to that day all the payments you received up to that day. So, that we are and understood same on this one. Let's copy that formula. Pick numbers. There we are. We're having the accumulation of salaries. So, highlight this column here. So, we're actually comparing the sums of these and looking at that to detail, the first day, the income of plan B overtakes plan A is when you earn 8,191 against 5,212. So, the day before, we're still making more money on the first payment plan. But we are ahead from the 13th day onwards. Why am I talking about that? We are going to pay attention to sequences of earnings and sums of earnings. But let's look at another example. I've got another story for you. The inventor of the game of chess, this was before the seventh century in India, presented a game to the emperor. Now, having enjoyed the new game the emperor praised the inventor and offered a generous reward. "Whatever you want!" She asked for one grain of rice for the first square of the board. Two for the second square, four grains of rice for the third square, eight for the next, and so on. The Emperor approved the payment, probably dismissing it as a humble request from this inventor and not giving it much more thought. Well, in the end it's just a few grains of rice for an emperor. The Treasurer in charge of the transaction later returned to the emperor informing them the reward would add up to more rice than they could ever, ever have ground. What is going on? You know the chessboard is eight by eight. So, we have 64 squares, surely adding one plus two, plus four, plus eight, all the way to two to the power of 63 grains of rice. That can't be that much can it? Now, if you want you can go and find out how much do we produce in the world in rice in terms of grains but I leave you to that. I have another problem for you. The traveling maths presenter problem. I'm taking bookings for touring with my new show. Here's my schedule for the next summer together with a travel costs. So, initially I'm going to London, Manchester and Edinburgh and I need to travel between all these cities and London to Manchester I'm seeing that there's a £100 fare, London to Edinburgh a £150 fare, Manchester to London yes trains in Britain is a little bit more expensive, it's a £120, and Manchester the Edinburgh a bargain 50 quid, Edinburgh to London a £130, Edinburgh to Manchester £50. So, this is what I'm expected to spend so far now. I have to visit all the cities and come back to the starting point. Of course, in the cheapest way possible. But no cities are to be repeated apart from the start and end. I do want to end up at home. We can attack the problem by trying out all the possible trips in my tour. Could do London to Manchester to Edinburgh of course back to London. London, Edinburgh, Manchester, back to London. Manchester, London, Edinburgh, and so on. These six trips to check and surely, we can add up the totals and calculate the cheapest trip doesn't sound difficult. But it turns out, I just got another booking coming in. I'm going to Cardiff here's my updated table with my costs. Now, with this extra city, the trips I'm to make I'm to travel, I could do Cardiff, London, Manchester, Edinburgh back to Cardiff. Cardiff, London, Edinburgh, Manchester back to Cardiff and so on. So, I could just put a Cardiff at the beginning of all the trips I've studied before, that gives me six of them. But I could go to Cardiff seconds could I? Here's the list. Or I could go to Cardiff in the third place, on the fourth place and so on. How many trips do I have now with this extra city? It turns out, it's 24. So, within cities, six trips that I can consider. With four cities, we now have 24 trips. How many trips for n cities? I'm expecting a big tour. The trips to consider with one more city is the same as the trips I had with my old number of cities times the new number. So, trips of n plus one cities is the same as n times the trips with n cities. So, trips on three cities is six, trips on four cities is four times trips of three, which is four times six to 24, trips with five cities is five times of trips of for which we've just done, it's five times 24 which is a 120. So, I can expand this as the trips for n cities as n times n minus one times n minus two times a smaller, smaller number times three times two. We could analyze the costs of all these trips could we? But how long does it take to do that job? To cost and analyze all these possibilities as the number of cities increases. As I get more and more bookings, this approach to finding the cheapest tour becomes unmanageable. I hear you cry. Surely, we can use computers. The number of options to look at grows very fast as we increased number of cities to visit. So, fast that this brute force approach of checking every option is not okay. Not even with computers. In the case of the traveling maths presenter problem also known in the literature as the traveling salesperson problem. There is no known algorithm to give the optimal solution. This is why in a competing degree, you study problem-solving maths, algorithms, complexity, and get to learn why some algorithms just do not accomplish the task within our lifetime. Not even with all computers in the world linked up working on the same task. We touched on this before when we talked about factorizing large numbers and deciding of a number being prime. In this topic, we will be looking at some tools for understanding sequences of numbers like the ones we saw earlier, their growth and summation. We will not cover all possibilities but we will introduce key tools that will allow you to make sense of the behavior of sequences.