What are functions?

Wikipedia.com defines a function in mathematics as an abstract entity that associates an input to a corresponding output according to some rule.

A good mental model for this idea is a function machine. My colleague at CIESE (where I worked until last October) Jason Sayres created this nice example which he calls The Mystery Box Game* which is really version of "Guess my Rule". For example, let's say

2 goes through the box and becomes 5
5 goes through the box and becomes 11
9 goes through the box and becomes 19
Can you predict what rule is being used here? (Spoiler alert: click here)

A rule is a mathematical way of explaining a pattern if one exists. Since mathematics can be thought of as the study of patterns, rules or functions are foundational for understanding mathematics.
Hopefully, the rest of lesson 1 (Chap 3) will be easier to understand. (Note: Bob has posted the answers for the first lesson of the first edition on our Jacobs group site.)

So what's the tower puzzle got to do with functions?
Julie wrote this:
Thanks Bob. You said:
Instead of comparing the number of moves to the number of discs, try comparing the number of moves for "n" discs to the number of moves for "n-1" discs.

I now say:
We now have an exponentially increasing difference 2, 4, 8... so I would guess it continues 16,32, 64, 128 ...

Let's try ( 2^n) -1 as a function. This means that when I replace: n with 1 the function rule produces: (2^1) = 2 -1 = 1. Continuing in the same with n = 2, 3, 4, my outputs are:
(2^2) = 4 -1 = 3
(2^3) = 8 -1 = 7
(2^4) = 16 -1 = 15
etc
am also seeing that the 1 disc is moved every alternate move in the pattern CBA although I have no idea how to express the moves mathematically. There is also something like 2,3,2,4,2,3 which looks patternish happening but I get very muddled trying to rermember what to do next physically when listing it this way.

Ihor replies:
You certainly got most of it. I assume that you increased the number of disks by 1, the number of moves jumped to the next power of 2 (minus 1). You also wrote the formula to get you the number of moves if the number of disks is N (or any number.) As you might recall, the monks in the tower of Benares started working on a tower with 64 disks. And when they are done the earth will become a pile of rubble. Is that something we should be worried about? In terms of our function machine, the 64 tower suggests the following:

Input: 64
Rule: Take 2 to power of 64 and subtract 1
Output: Whatever you get after you multiply 2 by itself 64 times and subtract 1! Quite a formidable task. (If you would like to see how a spreadsheet does it click here.)

As you probably can guess we don't have to worry that the monks will finish anytime soon and the worry about the earth's (unlike the stock market) demise is premature.

More about the way the disks move

For a 1 disk tower, it takes one move.
For a 2 disk tower, it takes three moves.
For a 3 disk tower, it takes seven moves.
Check out this animation of 4 disks:
Since 2^4 - 1 is 15, that's how many moves it takes. Now if you look at the 4-tower, you notice there is a 3-tower on top of the 4th disk. We first need to move the 3-tower to another place before we can free up the 4th disk to move. So this will take 7 moves. Now we can move the bottom disk which is the 8th move. Next we have to rebuild the 3-tower on top of the relocated 4th disk. So that will take another 7 moves and we are done. So in sum we need to move the 3-tower twice and the bottom disk just once so that's 2 x 7 + 1 = 15 moves.

We know there are 31 moves for 5 disks. And we know that we can't move the bottom disk until we move the 4-tower out the way... Hmmm. (Can you finish what I'm thinking based on what we did with the 4-tower?)

Coming this weekend: Descartes and his marvelous discovery (Lesson 2). Stay tuned...

-Ihor

*Black box mystery game is explained in detail here: http://ciese.org/math/activities/blackbox/