So this is one of the easiest proofs by induction to understand. And it's cool.
Suppose we wanted to add all the natural numbers from 1 to 100, what would we get? (1+2+3+...+99+100 = ??)
Don't reach for a calculator (or Excel spreadsheet) yet, that'd just be obnoxious, instead lets look at a simpler problem. What is the sum of the natural numbers from 1 to 5? 1+2+3+4+5 = 15. What about from 1 to 6? 21. Let's create a table of these sums:
1
1
2
3
3
6
4
10
5
15
6
21
7
28
On the left we have number, and on the right we have the sum of all the numbers from one to that number. Before going any further, see if you can detect a pattern in the right column.
One pattern is very obvious, to get the next number on the right column, all you have to do is add the number to its left to the number above it (7+21=28). So the next number down will be 28+8=36. In general we can write the formula:
F(n+1) = (n+1) + F(n)
This is a recursive formula, written in terms of the previous value. This is helpful, because if we know value, we can easily figure out what comes next, but it doesn't really help trying figure out what the 100th value is (unless we want to first figure out 99 others).
So while our recursive formula is nice, it's not nice enough. Some more observations might lead to:
F(n) = n(n+1)/2
(Side note: I gave this assignment to a group of nine sixth graders and they found this result on their own in under 45 minutes). Now to find all the numbers from 1 to n, all you have to do is multiply n by n+1 and divide that by 2. But is does that formula really work? Well now we finally get around to induction (I know it's taken a while).
To prove something by induction, we have to show it's true for the initial case, then show that if it's true for the nth case, it'll always be true for the (n+1)th case. The first step is easy:
F(1) = 1(1+1)/2 = 2/2 = 1
So our formula certainly holds true for the first case. Now assume that it's true for the nth case:
F(n) = n(n+1)/2
and if we add n to both sides of this equation we get:
Nick sent this in an email to us, but I wanted to upload it to keep our documentation up. The response from Joseph is posted as well.
Hey Team,
As usual, an excellent meeting. A lot of notes this week:
Our schedual as of right now:
7/28 -- Mu Discussion (231-272)
8/4 -- Micah's Presentation
8/11-- General Discussion of Part 1 (1-272)
8/18 -- There was some discussion of doing a Chess day this day.
There was a lot of Chess discussion in general today, anyone who wants to play email chess with me, let me know (by responding to this email).
We played a game I found in This Book in which the rules were to "pick the smallest number that is not chosen by anyone else." The results are included below as well as in the Excel attachment.
In reference to the TNT, we discussed mathematical induction. on Centophila, I'll be posting a short paper on the subject.
Game Results:
Joe
5
4
4
3
2
2
Eric
7
2
5
6
4
5
John
5
2
1
2
2
2
Veronica
7
3
1
6
1
1
Derek
3
3
3
3
3
3
Nick
27
4
8
4
4
4
Kera
9
1
2
3
1
4
See you next week, -Nick
FYI, for those not present today, the results of 6 iterations of the game below can be interpreted as follows:
1. "game" results are the columns 2. the "winner" is the smallest positive integer not chosen by anyone else (so, for example, the winner of game 1 is Derek, game 3 winner is Kera, etc.) 3. "learning" (of some sort) occurs because the results of each game's choices are publicly known and the cumulative choices are part of the group's "memory" as well.
Obviously, the game is NOT interesting if there are just 2 players, since the right choice is 1 in each case (if you choose 1, you can't lose) and there should never be a winner. With as little as 3 players, it gets interesting. With too many (say, 25 or more) players, it also is probably not very interesting. In between 2 and "too many" is where the interest lies.
Hey there. I thought I'd try to contribute something of substance while away, so I've picked out a few books that I think might jive well with the themes we've been discussing.
The First Law trilogy by Joe Abercrombie is a good answer to the fantasy tradition of grand narratives. It concerns itself largely with random chance and pointlessness. (It's also fantastic).
The Prince of Nothing by R. Scott Bakker is a great example of philosophical, theological and very gritty fantasy. It's a bit like Dune, and a bit like the Second Crusade.
Here's a new and improved (proposed) game plan for the next few weeks:
7/21 -- TNT Discussion (199-230) 7/28 -- Mu Discussion (231-272) 8/4 -- Micah's Presentation 8/11-- General Discussion of Part 1 (1-272)
We did not discuss GEB again this week, instead we had a great discussion about Santa, and his relationship to both the platonic realm and Eric's mom, and a little bit of logic. Next week we should pick up from where we left off a while ago.
Note that before reading Chapter 9: Mumon and Godel (246-272), you should first read Chapter 1: The MU puzzle (33-42).
Last week (7/7) we discussed the intuitionist philosophy, and it came up that the rejected Reductio Ad Absurdum. The example John used was the proof that there are infinitely many prime numbers (personally I think the irrationality of the square root of two is a little cooler).
Anyways, we didin't actually go over the proof, so here it is.
A quick refresher: A prime number is a number that can only be divided by one and itself. So 3 is prime (only 1 and 3 divide 3) and so is 7, but 9 us not (can be divided by 3) nor is 24 (2, 3, 4, 6, 8 and 12 all divide 24). The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19...
As you get higher and higher up on the number line, there are less and less prime numbers, so the natural question to ask is, do the prime numbers ever run out?
Well let's assume they do. Let's assume we eventually run out prime numbers. That must mean that there's a biggest prime number, right? Let's call our biggest prime number P. Now let's make another number, we'll call it Q. Where going to make Q but multiplying all of the prime numbers together, then adding one. Symbolically:
Q = (2*3*5*7*11*13*...*P) +1
So we do we know about Q? For starters, we know that Q can not be divided by any number between 1 and P. How do we know that? Well, Q is divided by any number between 1 and P, then the remainder will always be 1.
For the sake of comprehension, lets assume 7 is the biggest prime number (P). then:
Q = (2*3*5*7) +1 = 211
Q can't be divided evenly by 2, 3, 5 or 7 (try it, remainder 1 every time, right?). That means that there's either a number bigger than 7 (our "biggest prime") or 211 is prime (it's prime, trust me).
In general, every time we pick a P, we can always find a Q that's either prime, or has a prime factor larger than P. Therefore there's no largest prime number, and our original assumption (that P is the largest prime) is shown to be absurd. This is called Reductio Ad Absurdum (Reduction to the absurd, we say it in Latin because it reminds us that we are better than other people).
I'm not sure this is really a great outline, but I imagine most of you reading this have already seen this a few times before. If I'm wrong, and if it needs to be cleared up a little (or if you notice a mistake I've made) please leave a comment.
For next week (7/7) read Crab Canon (pg 199) and Chap. 8 (pg 204).
Big thanks to Kera for an enlightening presentation.
At the end of this month (7/28) Micah will be doing a presentation.
-Nick
7.01.2009
Hi everyone,
Thanks for being so receptive to my presentation. Here's a copy of it for those who missed parts of it.
It was great to get all your feedback, thanks again!
Please do send me any notes you all have on what you see as the future of art and what you believe would be the most important aspects of our manifesto.
