Discrete Mathematics with java applications

[GeeksUtopia]

pretty sure if people can post their essays online and have grammar Nazis have at it, I could post some math problems and a math magician can solve this....

Define a sequence a_n, n in a set of all positive integers, as follows:

a_1 = 1, a_2 = 2, a_3 = 3
a_n = a_(n-3) + a_(n-2) + a_(n-1) for n >= 4

1.Use the well ordering principle to show that a_n < 2^n for all n in a set of all positive integers.

2.Use strong mathematical induction to show that a_n < 2^n for all n in a set of all positive integers.

 

[DoPo]

Just to make sure I understand - you want Java code for this? Because...umm, I think you actually use plain ol' Maths for it, java.lang.Math would just run something to make sure what you have works.

Or...do you want a Java application to actually come up with the solution?

CAPTCHA: sudo make sandwich
Unexpected token "sandwich" expecting a pronoun. Terminating.

 

[GeeksUtopia]

Just to make sure I understand - you want Java code for this? Because...umm, I think you actually use plain ol' Maths for it, java.lang.Math would just run something to make sure what you have works.

Or...do you want a Java application to actually come up with the solution?

CAPTCHA: sudo make sandwich
Unexpected token "sandwich" expecting a pronoun. Terminating.

Sorry should have been more descriptive, it's just plain ol' Maths, and this has been eluding me for the past couple of days.

 

[Redingold]

Just to make sure I understand - you want Java code for this? Because...umm, I think you actually use plain ol' Maths for it, java.lang.Math would just run something to make sure what you have works.

Or...do you want a Java application to actually come up with the solution?

CAPTCHA: sudo make sandwich
Unexpected token "sandwich" expecting a pronoun. Terminating.

Sorry should have been more descriptive, it's just plain ol' Maths, and this has been eluding me for the past couple of days.

Does it have to be with those methods, or will any proof that a[sub]n[/sub] < 2[sup]n[/sup] do?

I have no idea what the weak ordering principle or strong induction are, but it's easy to prove with other methods.

Consider that a[sub]n+1[/sub] = a[sub]n[/sub] + a[sub]n-1[/sub] + a[sub]n-2[/sub] = 2a[sub]n[/sub] - a[sub]n-3[/sub]

Since a[sub]n+1[/sub] is less than 2a[sub]n[/sub], the growth rate for a[sub]n[/sub] is slower than that of 2[sup]n[/sup]. Since 2[sup]n[/sup] > a[sub]n[/sub] for n = 1, 2, 3 and 4, your inequality is true for any positive integer n.

Got no idea how to do it the way you said, though. Also, my proof annoys me, I feel like it's lacking in rigour.

 

[DoPo]

Just to make sure I understand - you want Java code for this? Because...umm, I think you actually use plain ol' Maths for it, java.lang.Math would just run something to make sure what you have works.

Or...do you want a Java application to actually come up with the solution?

CAPTCHA: sudo make sandwich
Unexpected token "sandwich" expecting a pronoun. Terminating.

Sorry should have been more descriptive, it's just plain ol' Maths, and this has been eluding me for the past couple of days.

Ah...the Java in the title threw me off.

OK, I'm no Math magician but I know some Maths, still. Sadly, I've never really got the hang of the mathematical proving (I suck at describing it) but I'll try to help.

In regards to 1. erm, first time I hear of the "the well ordering principle". Wikipedia tells me it states that any set has a smallest member (sans the empy set, of course). That...doesn't actually help me a lot. Dunno how can you use it for proof.

But for 2. - I'm bad at normal induction so I have even less of an idea about the complete one. However, I think you can just use the fact that the growth of 2^n is exponential and higher than the growth of a_n. Also, 2^n starts higher than a_n for positive integers (n=1 - a_n=1; 2^n=2), therefore 2^n will always be higher than a_n. Or something along those lines. Just...umm, write this in Maths, I suppose.

EDIT: read more on Wikipedia on the well ordered principle (so, basically, after the first sentence). This is stupid - it seems 1. is actually saying to use proof by contradiction. Or something like that. Why did anybody feel the need to use so fancy words?

So anyway, I think what you need for it is just to start with the assumption that there exists n for which a_n > 2^n and then prove it's impossible. So I guess the same proof you'd use for 2. but from a different perspective.

 

[GeeksUtopia]

Just to make sure I understand - you want Java code for this? Because...umm, I think you actually use plain ol' Maths for it, java.lang.Math would just run something to make sure what you have works.

Or...do you want a Java application to actually come up with the solution?

CAPTCHA: sudo make sandwich
Unexpected token "sandwich" expecting a pronoun. Terminating.

Sorry should have been more descriptive, it's just plain ol' Maths, and this has been eluding me for the past couple of days.

Does it have to be with those methods, or will any proof that a[sub]n[/sub] < 2[sup]n[/sup] do?

I have no idea what the weak ordering principle or strong induction are, but it's easy to prove with other methods.

Consider that a[sub]n+1[/sub] = a[sub]n[/sub] + a[sub]n-1[/sub] + a[sub]n-2[/sub] = 2a[sub]n[/sub] - a[sub]n-3[/sub]

Since a[sub]n+1[/sub] is less than 2a[sub]n[/sub], the growth rate for a[sub]n[/sub] is slower than that of 2[sup]n[/sup]. Since 2[sup]n[/sup] > a[sub]n[/sub] for n = 1, 2, 3 and 4, your inequality is true for any positive integer n.

Got no idea how to do it the way you said, though. Also, my proof annoys me, I feel like it's lacking in rigour.

the way explained, and like the avatar, shows how this problem is making me feel

 

[smithy_2045]

Proof by induction;

Step 1,
Solve the initialisation step. That is, show that it holds true for the smallest possible value of n.

IE; for n = 1, 2^n = 2 > 1 = a_1

Step 2,
Solve the induction step. I'm a little rusty on this, but I believe you let n = k + 1, and using that you show that it holds true for all values of n.

IE; a_n < 2^n
LHS:
a_k+1 = a_n + a_n-1 + a_n-2
therefore, a_n+1 < 2*a_n
RHS:
2^(k+1) = 2^n * 2

Therefore, a_k+1 < 2*a_n < 2*2^n
Therefore, a_n+1 = 1.

It's been 3 years since I did discrete maths, so it mightn't be perfect, but it seems rigorous enough to me.

 

[DracoSuave]

1<2^1
2<2^2
3<2^3

Okay, got that done.

a_n+3=a_n+2 + a_n+1 + a_n

2^n+3=2^n+2 + 2^n+1 + 2^n + 2^n

If 2^n+2 >= a_n+2, 2^n+1 >= a_n+1, and 2^n >= a_n, then 2^n+3 > a_n+3

There.

 

[DracoSuave]

It's been 3 years since I did discrete maths, so it mightn't be perfect, but it seems rigorous enough to me.

Proof falls apart for n=2 and n=3 because the inductive part becomes undefined.

Not that n=2 or 3 isn't trivial, but...

 

[Tanakh]

pretty sure if people can post their essays online and have grammar Nazis have at it, I could post some math problems and a math magician can solve this....

Define a sequence a_n, n in a set of all positive integers, as follows:

a_1 = 1, a_2 = 2, a_3 = 3
a_n = a_(n-3) + a_(n-2) + a_(n-1) for n >= 4

1.Use the well ordering principle to show that a_n < 2^n for all n in a set of all positive integers.

2.Use strong mathematical induction to show that a_n < 2^n for all n in a set of all positive integers.

Are you sure 1 says that? The well ordering principle is an existence axiom that guarantees you that every set of integers has a smallest element. I can't see how it could be used here as more than an unelegant argument for the sake of putting it in the proof.

As for 2, it's your run off them mill induction. Didn't checked the posts avobe mine, but they should be right.

Why did anybody feel the need to use so fancy words?

Fancy words?

 

[Redingold]

pretty sure if people can post their essays online and have grammar Nazis have at it, I could post some math problems and a math magician can solve this....

Define a sequence a_n, n in a set of all positive integers, as follows:

a_1 = 1, a_2 = 2, a_3 = 3
a_n = a_(n-3) + a_(n-2) + a_(n-1) for n >= 4

1.Use the well ordering principle to show that a_n < 2^n for all n in a set of all positive integers.

2.Use strong mathematical induction to show that a_n < 2^n for all n in a set of all positive integers.

Are you sure 1 says that? The well ordering principle is an existence axiom that guarantees you that every set of integers has a smallest element. I can't see how it could be used here as more than an unelegant argument for the sake of putting it in the proof.

As for 2, it's your run off them mill induction. Didn't checked the posts avobe mine, but they should be right.

Every set of positive integers.

 

[Tanakh]

Every set of positive integers.

Tru that! Though by the well ordered theorem what i said is also true, kinda... every set has a least element, which will work as the "smallest". TBH i never knew there was a weaker version till now.

 

[Tanakh]

Humm, after reading the induction proofs. I would pass both smithy_2045 and DracoSuave's answers if that was their answer in a non pure math class, and fail them both if they were math, physics or something alike.

Draco's inductive step is as informal as it can get, smithy's is better. But both fail because their induction basis is wrong. You must prove the equation is valid for the lowest n value for which the construvitve algorithm works, in this case for n = 4. If the professor was looking for a trick question, this one is quite well done

 

[GeeksUtopia]

Humm, after reading the induction proofs. I would pass both smithy_2045 and DracoSuave's answers if that was their answer in a non pure math class, and fail them both if they were math, physics or something alike.

Draco's inductive step is as informal as it can get, smithy's is better. But both fail because their induction basis is wrong. You must prove the equation is valid for the lowest n value for which the construvitve algorithm works, in this case for n = 4. If the professor was looking for a trick question, this one is quite well done

Thanks and thank you both smithy and Draco, so what I got so far is to basically prove that the opposite of the defined statement is false and the defined statement is true for all integers n >= 4

 

[WoW Killer]

Alright...

Well ordering principle. Like DoPo said, this is just saying that a set of natural numbers must have a least element. This is used to display a contradiction, as pointed out. What you do is, take a set of numbers with a property you believe to be impossible. Among these, there must be a least value. Then, using this least value, create a contradiction. A common method is to find a smaller value in the set. In other words, find a number contained in this set (i.e. having the property you believe to be impossible) that is smaller than the smallest element. Hey presto, you've proved the set to be empty. Do you follow?

In this case we want to prove that a_n = 2^n, and assume for a contradiction that S is non-empty. Therefore, by the well ordering principle, S must have a smallest member, call it s.

We then have that:

1) a_s >= 2^s, and
2) a_s = a_(s-1) + a_(s-2) + a_(s-3) <- missed the trivial step here, easily filled in

Now then, s-1 and s-2 are smaller than s. Since s is the smallest element of S, we see that s-1 and s-2 are not in S (this is how we use that smallest value property). Therefore

i) a_(s-1) < 2^(s-1), and
ii) a_(s-2) < 2^(s-2).

From 1) and 2) we have

2^s <= a_(s-1) + a_(s-2) + a_(s-3),

then substituting i) and ii) we get

2^s < 2^(s-1) + 2^(s-2) + a_(s-3).

Using 2^(s-1) = (2^s)/2 and 2^(s-2) = (2^s)/4 we have

2^s < (3/4) * 2^s + a_(s-3).

Hence

(1/4) * 2^s < a_(s-3), and so

2^(s-2) < a_(s-3).

Finally, we see that

2^(s-2) > 2^(s-3), and therefore

a_(s-3) > 2^(s-3).

But this means s-3 is in S. Since we defined s to be the smallest element of S, this proves that S is empty, which was to be demonstrated.

You may notice at the point I wrote out i) and ii), I could have written a_(s-3) < 2^(s-3) and proceeded from there. It would have resulted in showing that s is not in S, for a similarly effective contradiction. This would have been essentially the same thing as an inductive proof. The two are basically one and the same.

 

[GeeksUtopia]

Alright...

Well ordering principle. Like DoPo said, this is just saying that a set of natural numbers must have a least element. This is used to display a contradiction, as pointed out. What you do is, take a set of numbers with a property you believe to be impossible. Among these, there must be a least value. Then, using this least value, create a contradiction. A common method is to find a smaller value in the set. In other words, find a number contained in this set (i.e. having the property you believe to be impossible) that is smaller than the smallest element. Hey presto, you've proved the set to be empty. Do you follow?

In this case we want to prove that a_n = 2^n, and assume for a contradiction that S is non-empty. Therefore, by the well ordering principle, S must have a smallest member, call it s.

We then have that:

1) a_s >= 2^s, and
2) a_s = a_(s-1) + a_(s-2) + a_(s-3) <- missed the trivial step here, easily filled in

Now then, s-1 and s-2 are smaller than s. Since s is the smallest element of S, we see that s-1 and s-2 are not in S (this is how we use that smallest value property). Therefore

i) a_(s-1) < 2^(s-1), and
ii) a_(s-2) < 2^(s-2).

From 1) and 2) we have

2^s <= a_(s-1) + a_(s-2) + a_(s-3),

then substituting i) and ii) we get

2^s < 2^(s-1) + 2^(s-2) + a_(s-3).

Using 2^(s-1) = (2^s)/2 and 2^(s-2) = (2^s)/4 we have

2^s < (3/4) * 2^s + a_(s-3).

Hence

(1/4) * 2^s < a_(s-3), and so

2^(s-2) < a_(s-3).

Finally, we see that

2^(s-2) > 2^(s-3), and therefore

a_(s-3) > 2^(s-3).

But this means s-3 is in S. Since we defined s to be the smallest element of S, this proves that S is empty, which was to be demonstrated.

You may notice at the point I wrote out i) and ii), I could have written a_(s-3) < 2^(s-3) and proceeded from there. It would have resulted in showing that s is not in S, for a similarly effective contradiction. This would have been essentially the same thing as an inductive proof. The two are basically one and the same.

Thank you so much, again bad-ass people with the most bad-ass avatars that fits the moment and the comments

 

[Tanakh]

Thanks and thank you both smithy and Draco, so what I got so far is to basically prove that the opposite of the defined statement is false and the defined statement is true for all integers n >= 4

For 2? a) The basis (base case): showing that the statement holds when n is equal to the lowest value that n is given in the question. (wikipedia)

In this case n=4 is our basis case because in the inductive step we will use a_m=a_m-3+a_m-2+a_m-1, and the first case for which this is true is n=3, thus we need to show it's true for it.

Depending on your axiomatic frame, there are several ways to do this, i would personally go with:

a_4=a_1+a_2+a_3=1+2+3=6<16=2^4, thus a_4<2^4.

b) The inductive step: showing that if the statement holds for some n, then the statement also holds when n + 1 is substituted for n. (wikipedia)

Since we are using strong induction, we can assume that for EVERY i in naturals lower than a fixed natural k a_i<2^i. Now we have to prove it for k.

a_k = a_k-1 + a_k-2 + a_k-3 < 2^k-1 + 2^k-2 + 2^k-3 < 2^k

QED.

(Note: 2^k-1 + 2^k-2 + 2^k-3 < 2^k needs to be proven, but it's left as an exercise to the reader, and the strong induction hipothesis is used on k-1 + a_k-2 + a_k-3 < 2^k-1 + 2^k-2 + 2^k-3)

-snip-

Lol, of course, using it the same way that the well ordered theorem is in abstract algebra! Thanks, for some reason i would have never tought of using it with, you know, numbers