Okay, so for this probably and given, uh, are in represents the number of moves is by the frames to her algorithm. Okay, we want to choose into decay to be these smallest integer such that n being the number of desks is less than equal to k times que plus one divided by two cans we want to prove and that are then again, being the number of moves is equal to two times Ah, are and minus K plus two to the K minus one. And additionally, we want to look at our initial conditions so that no disks requires no moves. And that we're having one disc requires one move. Yes, We start this proof off with the bass case. Our base step, we'll take what we have. Zero disk. So if we have our four pegs and no disks on it, we cannot do any moves to solve the puzzle. Right? The puzzles solved just in existence so are not is equal to zero. Okay, And then when we have one disc to get that one does to the fourth peg requires one move right from page one to peg for. So in the case, we have just one desk. It requires one move to solve. So those are the base steps, actually, like just solving initial conditions. Okay, then for recurrence, our recurrence step here we consider what we have n discs. You can't kind of break it down into three broader states. Right? So first, we're going to move the n minus case. Smallest discs. So the smallest discs to the second peg. So if we had our four pegs, it's gonna be some number of larger disks on one. And then some of these smaller ones on peg to left over okay? And that's gonna require are and minus k moves right by the recurrence relation. So next we want to move the K largest disk. So this is everything that's left on paid one to peg for. Okay, we have just three pegs toe work with where you have to leave that second peg alone in order to get the K largest pegs over to the fourth head here. Okay, but Thea Teller of Hanley uses only three pegs who can use that hand. Lie under them to know that it's going to take to the power of K minus one moves Okay. That was the Hanoi algorithm then. Lastly, it's the last thing we want to do here is to move everything that's on that second pegs. We need to move those and minus K. Smallest discs over to peg for. I need to get on top of the rest of them. So to the fourth peg. And again, we're going to do that in the same amount of moves that we move them to the second pig, namely our and minus K moves. Okay, so then we just have to sum up these 12 number of moves, right? Until we do that, we're gonna get that r n. It's equal to all right. In my case, that was moving que smallest pegs to that second smallest this to a second peg, plus the moves it took to move all the discs from the first peg to the fourth pay. That was to the K minus one and plus moving. All the disks from the second peg kay and my case smallest discs to the fourth egg. And we have ah, some common terms here race. We can combine these two terms to get two times are and minus K plus two to the K minus one, and that will complete the proof