MATH1081 Discrete Maths (5 Viewers)

[InteGrand]

Re: Discrete Maths Sem 2 2016

They give me this basic idea to construct my proof and I don't know how to use it.

That basic idea is hinting at using induction on n.

 

[InteGrand]

Re: Discrete Maths Sem 2 2016

I managed to get through the converse, because the question was an iff question, but I'm not too sure how to approach it from this direction.

Here's some hints/sketch.

Note (why?) that we really just need to prove the claim for proper fractions, i.e. numbers of the form p/q, where p, q are positive integers and p < q (so fractions less than 1). The general case will follow easily from this.

So, let p, q be positive integers with p < q. To find the decimal representation of p/q, recall that we can do this by long division by dividing q into p. What we do is divide q into the number "p.00000...". (E.g. If we were doing 3/7, we'd divide 7 into 3.0000... when doing the long division algorithm.)

Each time we divide q into a number from this process, we write the quotient above the p.0000..., and the remainder goes next to the next 0, etc. (Usual long division process from primary school.)

Now, note that as we go through this process, if we ever get to a stage where the remainder is the same as a previous remainder, the decimal representation will then start repeating the cycle from what happened at the last time we got that remainder (why?).

But such a second occurrence of a previous remainder is guaranteed to occur (why?)! And so p/q will have a repeating decimal representation.

(Where the "repeat" here really includes finite decimal representations, which means we got a remainder of 0 at one stage, and the decimal representation is finite, e.g. 0.25 (which would "repeat" as 0.25000...). Of course if writing up a formal proof we'd write things more carefully, but these were just rough hints/sketch, so we don't need to worry about that here.)

 

[Paradoxica]

Re: Discrete Maths Sem 2 2016

Bernoulli's inequality

Trivial.

 

[InteGrand]

Re: Discrete Maths Sem 2 2016

Bernoulli's inequality

Trivial.

How so?

 

[Paradoxica]

Re: Discrete Maths Sem 2 2016

How so?

 

[InteGrand]

Re: Discrete Maths Sem 2 2016

That doesn't really help, does it? The exponent here is bigger than 1.

 

[RealiseNothing]

Re: Discrete Maths Sem 2 2016

That doesn't really help, does it? The exponent here is bigger than 1.

^^^

 

[Paradoxica]

Re: Discrete Maths Sem 2 2016

That doesn't really help, does it? The exponent here is bigger than 1.

I should have been more wary, considering this exact question appeared in my trials...

Oh well.

-flies away-

 

[leehuan]

Re: Discrete Maths Sem 2 2016

That basic idea is hinting at using induction on n.

Lol I wanted to use induction but I couldn't see the link

Here's some hints/sketch.

Note (why?) that we really just need to prove the claim for proper fractions, i.e. numbers of the form p/q, where p, q are positive integers and p < q (so fractions less than 1). The general case will follow easily from this.

So, let p, q be positive integers with p < q. To find the decimal representation of p/q, recall that we can do this by long division by dividing q into p. What we do is divide q into the number "p.00000...". (E.g. If we were doing 3/7, we'd divide 7 into 3.0000... when doing the long division algorithm.)

Each time we divide q into a number from this process, we write the quotient above the p.0000..., and the remainder goes next to the next 0, etc. (Usual long division process from primary school.)

Now, note that as we go through this process, if we ever get to a stage where the remainder is the same as a previous remainder, the decimal representation will then start repeating the cycle from what happened at the last time we got that remainder (why?).

But such a second occurrence of a previous remainder is guaranteed to occur (why?)! And so p/q will have a repeating decimal representation.

(Where the "repeat" here really includes finite decimal representations, which means we got a remainder of 0 at one stage, and the decimal representation is finite, e.g. 0.25 (which would "repeat" as 0.25000...). Of course if writing up a formal proof we'd write things more carefully, but these were just rough hints/sketch, so we don't need to worry about that here.)

First why - because set of rationals is closed under addition and integers are a subset of Q, yeah that's obvious and makes sense

Second why - Ah ok I can see it. From the long division process, say the number was 3. Then it'd be just doing a division by 30 to get the next value, just like was done earlier on. And then whatever the next number is will go the same way. My wording was horrible though... not sure how to fix it

Third why - Is this just because there are only nine digits in base 10 but our decimal can have an infinite number of digits and ultimately we will run out and be forced to repeat?

 

[InteGrand]

Re: Discrete Maths Sem 2 2016

Lol I wanted to use induction but I couldn't see the link


First why - because set of rationals is closed under addition and integers are a subset of Q, yeah that's obvious and makes sense

Second why - Ah ok I can see it. From the long division process, say the number was 3. Then it'd be just doing a division by 30 to get the next value, just like was done earlier on. And then whatever the next number is will go the same way. My wording was horrible though... not sure how to fix it

Third why - Is this just because there are only nine digits in base 10 but our decimal can have an infinite number of digits and ultimately we will run out and be forced to repeat?

Last 'why' is basically pigeonhole principle. When we are doing each step in the long division, the remainders by definition can only come from {0, 1, ..., q-1}, which is a finite set. So as we keep going through the procedure, since we get a remainder from this finite set each time, we will eventually get two the same (in fact, after doing q+1 steps we'd be guaranteed two same remainders, by the pigeonhole principle).

 

[leehuan]

Re: Discrete Maths Sem 2 2016

Last 'why' is basically pigeonhole principle. When we are doing each step in the long division, the remainders by definition can only come from {0, 1, ..., q-1}, which is a finite set. So as we keep going through the procedure, since we get a remainder from this finite set each time, we will eventually get two the same (in fact, after doing q+1 steps we'd be guaranteed two same remainders, by the pigeonhole principle).

Ah, still getting to the pigeonhole principle (think it's in topic 4) but I'll make a note of it.

 

[InteGrand]

Re: Discrete Maths Sem 2 2016

Ah, still getting to the pigeonhole principle (think it's in topic 4) but I'll make a note of it.

It's basically intuitive as follows. I'll illustrate it as though q = 5, but same idea works for general q of course.

Write down the remainder from each stage of the division algorithm (these have to be whole numbers from 0 to 4, since we're dividing by 5).

It's pretty clear that if we keep writing down numbers 0 to 4 forever, we can't avoid having two numbers the same (because we'll run out of numbers if we try to do that).

And that's it!

 

[leehuan]

Re: Discrete Maths Sem 2 2016

It's basically intuitive as follows. I'll illustrate it as though q = 5, but same idea works for general q of course.

Write down the remainder from each stage of the division algorithm (these have to be whole numbers from 0 to 4, since we're dividing by 5).

It's pretty clear that if we keep writing down numbers 0 to 4 forever, we can't avoid having two numbers the same (because we'll run out of numbers if we try to do that).

And that's it!

Woooaaahh that looks so simple when you put it like that

(And it actually sorta matches up with my idea...)

 

[leehuan]

Re: Discrete Maths Sem 2 2016



The reverse implication is trivial. Help on forward implication please

 

[Paradoxica]

Re: Discrete Maths Sem 2 2016

The reverse implication is trivial. Help on forward implication please

The non-trivial quadratic residues mod 7 are 1,2,4. It is impossible for the sum of any two of these residues to be divisible by 7. The conclusion follows.

 

[leehuan]

Re: Discrete Maths Sem 2 2016

The non-trivial quadratic residues mod 7 are 1,2,4. It is impossible for the sum of any two of these residues to be divisible by 7. The conclusion follows.

Ok yep makes sense. Now how would I set it out so that the fussy discrete maths tutors don't penalise my marks lol

Edit: Don't worry, can do by contradiction.

 

[Paradoxica]

Discrete Maths Sem 2 2016

Ok yep makes sense. Now how would I set it out so that the fussy discrete maths tutors don't penalise my marks lol

First, exhaustively obtain the residues mod 7, including the trivial one.

n = 7k, 7k±1, 7k±2, 7k±3

Secondly, write out every pair of residues that can be obtained, and compute their sum.

(0,0)(0,1)(0,2)(0,4)(1,1)(1,2)(1,4)(2,2)(2,4)(4,4)

Then show that the only pair that leaves trivial residue mod 7 is (0,0), which is the case IFF x ≡ y ≡ 0 mod 7

 

[RenegadeMx]

Re: Discrete Maths Sem 2 2016

First, exhaustively obtain the residues mod 7, including the trivial one.

n = 7k, 7k±1, 7k±2, 7k±3

Secondly, write out every pair of residues that can be obtained, and compute their sum.

(0,0)(0,1)(0,2)(0,4)(1,1)(1,2)(1,4)(2,2)(2,4)(4,4)

Then show that the only pair that leaves trivial residue mod 7 is (0,0), which is the case IFF x ≡ y ≡ 0 mod 7

ye this is pre much how u do the mod questions

 

[Drsoccerball]

Re: Discrete Maths Sem 2 2016

The reverse implication is trivial. Help on forward implication please

[]

 

[leehuan]

Re: Discrete Maths Sem 2 2016

I'm worried I messed up my inductive step. I feel like I need to attempt strong induction but is there a way to do so without?