Grandmas and Trolls Brainteaser

Taken from Braingle.com:

You are on your way to visit your Grandma, who lives at the end of the valley. It's her birthday, and you want to give her the cakes you've made.

Between your house and her house, you have to cross 7 bridges, and as it goes in the land of make believe, there is a troll under every bridge! Each troll, quite rightly, insists that you pay a troll toll. Before you can cross their bridge, you have to give them half of the cakes you are carrying, but as they are kind trolls, they each give you back a single cake.

How many cakes do you have to leave home with to make sure that you arrive at Grandma's with exactly 2 cakes?

2 cakes.

You can solve this by working backwards. Each troll does two things: first he takes away half, then he gives you one back. If we look at the last troll with the last step first (giving one cake back), we see that to have two cakes at the end of it, we must have had only one cake (because 1 + 1 = 2). The previous step, in which he took away half of your cakes, we just have to double the number of cakes we had (1) to find that number, so we had two cakes before our last troll.

If we had two cakes leaving the 6th troll, that means he gave one back in the last step, so we had one cake after he halved our cakes. If after halving our cakes there was only one, that implies we had two cakes before he took half of them. So we had two cakes before our 6th troll as well.

If we continue working through with every troll, we see it doesn't matter how many trolls we encountered. With this pattern of troll tolls, to have exactly 2 by the time we reach Grandma's house, we would have to start with 2 cakes.