## I hate discrete structures

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

minty ice
Posts: 11
Joined: Tue Aug 05, 2008 5:30 am UTC

### I hate discrete structures

Someone teach me how to do mathematical induction

examples:

1 + 3 + 5 + ... + (2n-1) = n2

12 + 22 + 32 + ... + n2 = (n(n+1)(2n+1))/6

curse my cs major and my lack of math skills.

antonfire
Posts: 1771
Joined: Thu Apr 05, 2007 7:31 pm UTC

### Re: I hate discrete structures

There's a number of ways to think about induction proofs.

The usual way is like this: Suppose you want to show that, say, 1+2+3+...+n=n(n+1)/2.

Well, clearly, this is true for n=1: 1=1*(1+1)/2. (This is the "base case".)

Also, whenever it's true for n, it's true for n+1: if 1+2+3+...+n=n(n+1)/2, then 1+2+3+...+(n+1) = 1+2+3+...+n+(n+1)=n(n+1)/2+(n+1)=(n+1)(n+2)/2. So, if we know that 1+2+3+...+n=n(n+1)/2, we know that 1+2+3+...+m=m(m+1)/2, where m=n+1. (This is the "inductive step".)

That's the proof. Since it's true for 1, it's true for 2 (by the inductive step), so it's true for 3, and so on. So it's true for every natural number.

Here's another way to think about it. Suppose it's not the case that 1+2+3+...+n=n(n+1)/2 for every positive integer n. Then there is a smallest positive integer n for which it's not true. By the base case, we know it's not 1. So, there's a point where it's true for one positive integer, but not for the next positive integer. But we've shown that this isn't possible by the inductive step.

To summarize: You can use induction to prove some property is true for every positive integer. There are two steps to an induction proof: the base case, where you prove that the property holds for 1; and the inductive step, where you prove that if the property holds for n, it must hold for n+1 as well.

You can also start at 0, thus proving a proposition for every nonnegative integer.

Here's another example:

Theorem: Every nonnegative integer n can be written as 2m or 2m+1, for some nonnegative integer m.

Proof: Induction on n.
Base case, n=0: n=2*0, and 0 is a nonnegative integer.
Inductive step: Assume n can be written as 2m or 2m+1, for some nonnegative integer m. If n=2m, then n+1=2m+1, and m is a nonnegative integer, as desired. If n=2m+1, then n+1=2(m+1), and m+1 is a nonnegative integer, as desired.

Edit: If you're a CS major, it might help to think of an inductive proof as sort of like a recursive function.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

stormgren
Posts: 80
Joined: Wed May 16, 2007 11:09 pm UTC
Location: over the hills and far away

### Re: I hate discrete structures

Visualize Mojo the Induction Monkey climbing a ladder. If there is a mechanism that says that IF Mojo is able to climb to step k, THEN he will climb to step k+1, and additionally we can prove that Mojo climbed the first step, then Mojo will climb every step.

Well that's how I think about it anyway...
Another one my professor mentioned:
"Well, when you do heroin the first time, that's the base case. And if you do heroin this time, you'll do it again. So by induction you're a heroin addict."

Basically anything which has a starting point and a mechanism by which, given an arbitrary value, it certainly will be true for the next value, is provable by induction.

The formal statement of the induction hypothesis is:
Consider a series of mathematical statements P(n). Let k0 be the base case, a natural number.
If 1.) P(k0) is true
and 2.) P(k) => P(k+1) for all k>=k0,
Then P(n) holds for all n>=k0.

Oh, Mojo's full name is "Mojo the Magical Mathematical Induction Monkey." That's clearly important.

Xanthir
My HERO!!!
Posts: 4860
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: I hate discrete structures

To actually *prove* that your result is the correct answer, you do some simple math.

Assume that you have a possible answer to the sum. I'll use 1+2+3... because it's easy. You believe the answer on the nth step is n(n+1)/2.

Now, if this is true, then on the (n+1)th step, the answer will be (n+1)((n+1)+1)/2. You just substitute the n+1 in. To help the next step, I'm going to go ahead and simply both of these. The answer for the nth step simplifies to (n2+n)/2, while the (n+1)th step simplifies to (n2+3n+2)/2.

Now you just have to prove that this *assumed* answer for the (n+1)th step is actually true. You do this by taking the answer for the nth step, (n2+n)/2, and directly adding the next step, (n+1). A quick bit of algrebra shows that (n2+n)/2 + (n+1) does indeed equal (n2+3n+2)/2.

Thus, you have proven your inductive step. You've given a base inductive step, showed what the next step would be *if* you were right, and then showed that it matches the actual result of adding in the next step.

This, paired with the base case, completes the proof.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Yakk
Poster with most posts but no title.
Posts: 10879
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: I hate discrete structures

First, define a proposition. This is sort of like a function, but it 'returns' a logical statement.

Induction is:
If P(n) is a proposition about the natural number n, and
(1) P(0) is true, and
(2) ( P(k) -> P(k+1) ) is true for all natural numbers k, then
P(n) is true for all n from the natural numbers.

(1) is known as the base case. (2) is known as the inductive step.

Using mojo the monkey, (1) is the base of the ladder, and (2) is the step where mojo climbs a rung.

So we start off with 1 + 3 + 5 + ... + (2n-1) = n2. That looks like a statement we want to prove, right?

Well we have a hammer. Let's make the statement look like a nail!

Define P(n) := "1 + 3 + 5 + ... + (2n-1) = n2".

At this point, we don't know if P(n) is true. But we have a proposition on the natural numbers -- so we can apply induction!

Can you prove P(0) is true? I hope you can. Do it. Do it now. Don't just sit there, dooooo it. </dora explorer="true">

Ok, now we have the tricky part. We want to assume P(k) and use it to prove P(k+1), and we have to do this for an arbitrary natural number k.

So we write out what we know and what we want to prove:
We are allowed to assume: P(k) := "1 + 3 + 5 + ... + (2k-1) = k2"
for some specific (but unknown and arbitrary) natural number k.
We want to prove: P(k+1) := "1 + 3 + 5 + ... + (2k-1) + (2(k+1)-1) = (k+1)2"
Now remember -- we cannot derive anything from what we want to prove. We just noted it for future reference.

What we have to do is use it for inspiration. Expand the left or right hand side on scrap paper, and see if we can get anything interesting. Keep in mind that we can use the P(k) as a fact.

Can you see any way to manipulate one side or another of the thing we want to prove, so we can use our P(k) fact or identity?

The standard way to prove that two things are equal is to derive one from the other. So start with one side of the P(k+1) thing we want to prove, and then using P(k) as a fact, derive the other side. Make sure all of your derivations are "both ways" -- or, if you prefer, derive the left from the right, and then the right from the left.

Insert dora here.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Tac-Tics
Posts: 536
Joined: Thu Sep 13, 2007 7:58 pm UTC

### Re: I hate discrete structures

Induction is very closely related to a recursively-defined function (which are very useful in computer science). You may want to practice languages which rely on recursion (Scheme, Ocaml, Haskell, Erlang), as they may help you understand the process a little better.

Let's work with the example: P(n) is the statement 1 + 2 + 3 + ... + n = n(n+1) / 2. P is a predicate of one variable. Predicates are functions which can be true or false.

P(0) is 0 = 0(0+1) / 2, which is true.
P(1) is 1 = 1 * (1 + 1) / 2, which is also true.
P(2) is 1 + 2 = 2 * (2 + 1) / 2, which is also true.
P(3) is 1 + 2 + 3 = 3 * (3 + 1) / 2, which is still true.

We can check by hand if any given P(n) is true. It's really easy. You just plug in the value for n and plug it into your calculator. So for any individual n, finding out if P(n) is true is a simple matter of computation.

The problem is how do we show that no matter what n we choose, P(n) is a true statement? To calculate it by hand, we'd need to do an infinite number of computations. An important property of proofs is they must be finite! So how can we show, in a finite number of steps, P(n) is true?

The answer is we must assume an axiom of induction. This axiom goes like this:

If you can prove that P(0) is true and if for any n, we can show that P(n) being true implies that P(n+1) is true, then we can conclude for all n, P(n) is true.

Why do we accept this axiom as a legitimate part of logic? Well, if the two conditions are met (P(0) is true and P(n) implies P(n+1)), then we can recurse.

P(0) is true (base case)
P(0+1) = P(1) is true (by the implication)
P(1+1) = P(2) is true (by the implication)
P(2+1) = P(3) is true (by the implication)
... (and so on as high as we want)

So what I've outlined above is intuitively why induction is a legitimate form of proof. It's easy for most students to accept that, because they get graded on their proofs, not one whether or not they understand their proofs!

But the basic idea is simple. You need to prove your base case and the implication. The base case is always really easy, since it's a matter of computation. P(0). Plug in 0 for n in the formula and see if it's true or not.

The hard part is the implication step, because implication is really unintuitive! What does it mean that "P(n) implies P(n+1)"? It means assuming P(n) is true, proving that P(n+1) is true.

The confusion comes from that assumption. "If you *assume* P(n) is true, then aren't you assuming your entire proof is correct?" The answer is 'no'.

Douglas Hofstadter in his marvelous book Godel Escher Bach (GEB) describes the idea of logical implication very cleanly. He uses the term "fantasy" to give emphasis that your assumptions are just that! "Imagine a fantastic world where we found a magical number called n that made the statement P(n) true! What would the far reaching consequences of such a world be?"

Well, in the scenario above, let's assume some fantastic number n exists such that:

1 + 2 + ... + n = n (n+1) / 2.

What of it?

Well, by using regular logic inside of this fantasy world, we can deduce another fact:

1 + 2 + ... + n + (n+1) = n (n+1) / 2 + (n+1).... add (n+1) to both sides
1 + 2 + ... + n + (n+1) = (n (n+1) + 2(n+1) )/ 2.... do a little algebra to get a common 2 in the demoninator
1 + 2 + ... + n + (n+1) = (n^2 + 3n + 2 )/ 2.... more algebra.... multiply out the top
1 + 2 + ... + n + (n+1) = (n+1) (n+2) / 2... factor the top
1 + 2 + ... + n + (n+1) = (n+1) ((n+1) +1) / 2... do a final twerk to emphasize the form of the equation

If you are very astute (or have done induction before), you might notice that that last line is actually the statement P(n+1). The fantasy is over. By making your crazy assumptions, you have shown you can produce crazy results. After this step, you are *not* assuming P(n) is true. You have done your damage.

But what does this amount to? In order for this assumption to be any good, we'd need to actually find a suitable fantastic value for n. That's what the base case is for! The base case proves the existence of that n. Since P(0) is true, we can "invoke" our implication step. Let n=0, and our implication is P(0) => P(1). Since P(0) is true, then we conclude that P(1) is true. And since P(1) is true, we can invoke the implication step again, and prove P(2) is true. And when we are ready to turn in our test, we simply invoke the induction axiom above and conclude that "For all n, P(n) is true".

As you can hopefully see from this example, the hardest part of induction is understanding what "P(n) => P(n+1)" means and understanding how you prove it. There is also a lot of algebra during that step, which can be challenging as well (factoring polynomials is a bitch). Also, when real mathematicians do real proofs, they rarely figure the steps out in the order they appear in the proof. Human reasoning is very sketchy and the important steps will become obvious in a horrible messy way. Working backwards is often easier than working forwards, but your professor will expect the answer to be written forwards!

Yakk
Poster with most posts but no title.
Posts: 10879
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: I hate discrete structures

And, if you are a computer programmer, you can look at that step of the proof like a scope.

Ie

Code: Select all

`Assuming (statement X){ // NEW SCOPE  ... the assumed statement X may be taken as true within this scope} // END OF SCOPE`

The assumed statement is not assumed to be true in general -- we just assume it within a restricted scope. We cannot take the assumption out -- but anything we prove within the scope (say a statement we call Y) does generate _outside_ of the scope the statement:
X -> Y
or, "if X is true, then it follows that Y is true".

In the inductive proof, you are doing:

Code: Select all

`Prove P(x).Assume P(n){ // NEW SCOPE  ... here, we prove that P(n+1) is true!} // END OF SCOPE... because we proved that P(n+1) is true inside the Assume P(n) scope, we get:P(n) -> P(n+1)... we then take that statement, and use induction to prove P(n) is true _without_ making an assumption!`

if that makes any sense. :0
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

minty ice
Posts: 11
Joined: Tue Aug 05, 2008 5:30 am UTC

### Re: I hate discrete structures

yeah still dont get it.

Yakk
Poster with most posts but no title.
Posts: 10879
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: I hate discrete structures

Can you do _any_ inductive proof? If so, do it in a post.

Do you have an _example_ of an inductive proof from your course notes? If so, copy it into a post here.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

boxcounter
Posts: 35
Joined: Thu Jul 03, 2008 9:32 pm UTC

### Re: I hate discrete structures

minty ice wrote:yeah still dont get it.

Guys, I think at this point we should probably try to talk about it, rather than everyone barfing inductive proofs at Minty Ice...

Minty Ice, I want *you* to convince *us* that 1 + 2 + 3 + ... + n = n(n+1)/2. I ... well... I've just never believed it to be true, call me a skeptic.

First of all, here's three questions that I usually try to ask myself. I ask them to you:

1) What does that equation even mean?
2) Do you believe it? Why?
3) What is n? How big is n allowed to get? How small?

Please forgive me if (1) and (2) are too obvious, but seriously, it's really hard to prove stuff you don't believe/understand. And it's impossible to prove things that are wrong, I guess... So let's just make sure we're on the same page about that.