Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

**mathsyperson****Moderator**- Registered: 2005-06-22
- Posts: 4,900

Aaw, **JaneFairfax** isn't bolding people any more. I liked that. Anyway, here's my proof.

Consider the integral I = ∫dx/x. Using integration by parts, and taking u = 1/x, dv/dx = 1, we get:

I = x/x - ∫-x/x²dx

= 1 + ∫1/x dx

= 1 + I

We now have that I = 1+I and thus we can conclude that **1=0**.

*Last edited by mathsyperson (2007-03-22 22:44:11)*

Why did the vector cross the road?

It wanted to be normal.

Offline

**Dross****Member**- Registered: 2006-08-24
- Posts: 325

mathsyperson wrote:

Consider the integral I = ∫dx/x. Using integration by parts, and taking u = 1, dv/dx = 1/x, we get:

I = x/x - ∫-x/x²dx

That step is where the mistake lies - the rule is supposed to be:

But you're using some random rule that you get from integrating where you're supposed to differentiate, and vice versa - along the lines of:

*Last edited by Dross (2007-03-22 21:45:00)*

Bad speling makes me [sic]

Offline

**mathsyperson****Moderator**- Registered: 2005-06-22
- Posts: 4,900

Oh, that's really annoying. Sorry, I just got my labels mixed up. But still, I've edited them now and the flaw's still there. There's another more significant error in there that isn't just me being silly.

Why did the vector cross the road?

It wanted to be normal.

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

mathsyperson wrote:

Aaw,

JaneFairfaxisn't bolding people any more. I liked that.

Very well then, **mathsyperson**.

And I believe I know the answer to your proof, but Ill let others have a go at the problem first. So I wont say anything about it here yet.

Offline

**Dross****Member**- Registered: 2006-08-24
- Posts: 325

Heh - should really have given you the benefit of the doubt on that one I guess!

Anyway - now that's been cleared up and all, the error is that because your conclusion takes I to have some numerical value, you can only use your conclusion when you evaluate this integral between limits (i.e. you cannot use an indefinite integral). So you have to say:

Of course, as soon as you evaluate this, the

term becomes zero and doesn't bother us any more.*Last edited by Dross (2007-03-23 03:52:23)*

Bad speling makes me [sic]

Offline

**mathsyperson****Moderator**- Registered: 2005-06-22
- Posts: 4,900

Very good. You got that far more easily than I did when I saw it.

Anyway, that must mean that it's your turn for a proof again.

Why did the vector cross the road?

It wanted to be normal.

Offline

**Dross****Member**- Registered: 2006-08-24
- Posts: 325

Theorem: All positive integers are equal.

Proof:

It is sufficient to show that *a* = *b* for any two positive integers *a* and *b*.

Furthermore, it is sufficient to show that for every positive integer *n*, if *a* and *b* are such that *max(a, b)* = *n*, then *a* = *b*.

Proceed by induction.

For *n* = 1, the only choice for positive integers such that *max(a, b)* = *n* is *a* = *b* = 1, so the proposition holds for *n* = 1.

Now assume the proposition is true for some positive integer *k*.

Then consider the positive integers *a* and *b* such that *max(a, b)* = *k+1*.

Then *max(a - 1, b - 1)* = *k*.

By our assumption, *a* - 1 = *b* - 1, so obviously *a* = *b*.

QED

*Last edited by Dross (2007-03-23 04:41:12)*

Bad speling makes me [sic]

Offline

**luca-deltodesco****Member**- Registered: 2006-05-05
- Posts: 1,470

isnt the problem here, that the first part of the induction process isn't valid, since the two positive integers are already the same?

The Beginning Of All Things To End.

The End Of All Things To Come.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

Great proof, Dross. You are requiring the natural numbers to be closed under subtraction by 1. They aren't.

Then consider the positive integers a and b such that max(a, b) = k+1.

Then max(a - 1, b - 1) = k.

Your base case requires a - 1 and b - 1 to be natural numbers. But if I pick b = 1, then this simply isn't true.

I still am a bit shaky with this part:

Furthermore, it is sufficient to show that for every positive integer n, if a and b are such that max(a, b) = n, then a = b.

Is there something wrong with that statement? If there is, I can't seem to find it.

"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

Ricky wrote:

Furthermore, it is sufficient to show that for every positive integer n, if a and b are such that max(a, b) = n, then a = b.

Is there something wrong with that statement? If there is, I can't seem to find it.

I think what the statement is saying is this. Choose any two positive integers *a* and *b*. Then (supposedly) *a* would be equal to *b* if max(*a*,*b*) = some positive integer *n* so prove this by induction on *n*.

I dont think theres anything wrong with making such a statement. I mean, the statement is well and truly false; however, there is no harm at all in stating a statement of this kind provided it can be shown that the supposed proof of it is invalid. And I think youve already exposed the fallacy i.e. that while *a* and *b* may be positive integers, *a*−1 and/or *b*−1 may not be positive integers.

*Last edited by JaneFairfax (2007-03-23 12:09:49)*

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

Well, I'll assume I got the answer right. So it's my turn:

Prove that there are an infinity amount of primes equivalent to 1 modulo 4.

Proof: Assume that there are only finitely many primes congruent to 1 modulo 4: p1 = 5, p2 = 13, .. pr. Consider 4(p1)(p2)...(pr) + 1. This is not divisible by any of our primes, but it must be divisible by a prime congruent to 1 modulo 4, so the assumption that there are are only finitely many such primes must be wrong.

"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

Perhaps the proof of primes being equivalent to 3 modulo 4 should be done first, as such a condition can be proven true. But give me a counter example first before you say it's not true.

"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

Actually, I'll just give such a proof. Let p1, p2... pn be a finite list of primes such that each prime is congruent to 3 modulo 4. Then consider 4*p1*p2...*pn + 1. This is equivalent to 3 modulo 4. Now consider the prime factors of such a number as q1, q2, ..., qr. Obviously, qi != 2 (mod 4) for all 1 <= i <= r as this would imply 2 | 4*p1*p2...*pn + 1. Similarly for 4. So it must be that qi = 1 (mod 4) or qi = 3 (mod 4). Note that if all qi = 1 (mod 4), then 4*p1*p2...*pn + 1 = 1 (mod 4). Thus, it must be that at least 1 qi = 3 (mod 4). As qi | 4*p1*p2...*pn + 1, it must be that qi is not in our finite list of primes. Contradiction, there are an infinite amount.

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

Ricky wrote:

Then consider 4*p1*p2...*pn + 1. This is equivalent to 3 modulo 4.

Sorry, I dont get it.

PS: As for the previous part, well, 5 and 17 are primes congruent to 1 mod 4 but 4(5×17)+1 = 341 = 11×31 isnt divisible by any prime congruent to 1 mod 4. Then again I suppose its because Im not considering all the primes congruent to 1 mod 4. I suppose things might be different if you had to multiply together all such primes (assuming theyre finite).

*Last edited by JaneFairfax (2007-04-01 01:26:56)*

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

It was my fault. The error is fairly obvious when you don't see the proof of infinite primes congruent to 3 modulo 4 first. What's weird is that the statement which is true for 3 modulo 4 does not hold for 1 modulo 4. And all I was asking was for a counter example, which you provided.

Your turn if you want it. Otherwise, I think I got another one to post.

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

Ah well. I thought it was obvious enough to not need a counterexample. Anyway, if you have more false-proofs puzzles, keep posting. They are giving my brain cells an excellent working out.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

Lets try a group theory proof. This is one I actually did, but I modified the statement a bit so that the theorem is actually false. Anyone who understands highschool algebra can find the error in this... though they won't understand a word of the rest of it.

K ≤ G means K is a subgroup of G.

HK is the group generated by {hk : h is in H and k is in K}

n is the symbol I will be using for intesection, as I am that lazy.

Prove that if H is a normal subgroup of G of prime index p, then for all K ≤ G, either |K| = 1 or G = HK and |K : K n H| = p.

Proof: First note that if G = HK, then |G| = |HK| = |H|*|K| / |K n H|. but |G| = p*|H| for some prime p, so it must be that |K|/|K n H| = p.

Now assume that G != HK. So |G| != |HK|. As H is normal in G and K ≤ G, HK ≤ G. So |G| / |HK| = a, for some integer a, as |HK| divides |G|. Also, |G|/|H| = p. But |HK| = |H||K|/|H n K|, so |G|/(|H||K|/|H n K|) = a, and thus, |G|/|H| = |K||K n H|a. If a = 1, then |HK| = |G|, so it must be a != 1. thus, since |K||K n H|a = p, it must be that |K| = 1.

Therefore, either |K| = 1 or G = HK and |K : K n H| = p.

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

Ricky wrote:

|G|/(|H||K|/|H n K|) = a, and thus, |G|/|H| = |K||K n H|a.

Err, are you sure its not |*G*|/|*H*| = |*K*|*a*** ∕ **|*K* ∩ *H*|?

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

Exactly! The normal proof is to prove that K ≤ H, not |K| = 1. It should have gone:

so |G|/(|H||K|/|H n K|) = a, and thus, p = |G|/|H| = |K|a / |K n H|. But |K n H| divides |K| as K n H is a subgroup of K. So it must be that either a = 1 or a = p. If a = 1, then |HK| = |G|, so it must be that a = p. But then |K|/|K n H| = 1, and thus, K ≤ H.

But I got it (partially) wrong, all because I couldn't divide. Ah well.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

Here is another I came across today.

Prove the number of k-ary strings of length n which has all k "bits" is given by the formula:

So for example, the tertiary (0's, 1's, and 2's) string 010010 does not contain a 2. But 01002 does, so we would count this.

Proof:

First, we choose where to place our k distinct bits. We may choose from n slots (string is of length n). So we have n choices for the first, n-1 choices for the second, and we continue all the way till n-k choices, making this:

n(n-1)...(n-k) = P(n, k), permutations of n objects selecting k.

So we are left with n - k slots in our string. Each of these slots may take on k values, making this k^(n-k). Since these are independent, we end up with the equation:

.Offline

**mathsyperson****Moderator**- Registered: 2005-06-22
- Posts: 4,900

You're counting things more than once there.

Say we want to count the number of binary strings of length 3.

Then, by your method, we would first place the 2 distinct bits.

This would give us the following 6 possibilities:

01?

0?1

?01

10?

1?0

?10

And then by replacing each ? by 0 and 1, we would get the twelve strings that the formula tells us that we should get. However, in the first two of those, replacing the ? with a 1 will give the same string, even though it got counted twice. In total, there are only actually 6 strings for this example. The same flaw will happen in any case where n≠k (and where k>1).

Why did the vector cross the road?

It wanted to be normal.

Offline

**JaneFairfax****Member**- Registered: 2007-02-23
- Posts: 6,868

I have one.

Prove that every Cauchy sequence is convergent.

Proof:

(This is the definition of a Cauchy sequence.)

*Last edited by JaneFairfax (2007-04-11 08:05:50)*

Offline

**javacodeman****Member**- Registered: 2007-04-04
- Posts: 9

Great thread. I'm to post 51. I'm just replying so I can be sure to find it again later.

java

Offline

**Zhylliolom****Real Member**- Registered: 2005-09-05
- Posts: 412

That's a strange smiley there. But here's my thought on the situation. You've given us the illusion that {a[sub]n[/sub]} converges to a[sub]N + 1[/sub]. But we cannot conclude this. Why? Because for different ε, we may have different N. N is dependent on ε. Then a[sub]N + 1[/sub] may not always be the same number since N changes with a different choice for ε. But we know that if a limit of a sequence exists, it must be unique. Therefore we cannot conclude that {a[sub]n[/sub]} converges to a[sub]N + 1[/sub], since a[sub]N + 1[/sub] is not necessarily unique for all N.

Offline