Author Topic: Discrete Maths (Read 18559 times) Tweet Share

FallonXay · « **on:** April 21, 2017, 12:53:27 pm »

Hello!
I'm having a ton of trouble with proofs in discrete maths ( I can barely do any questions

)
I've posted a few questions below (Q13, 15a, 16 b/c) any help would be greatly appreciated!

Thanks.

RuiAce · « **Reply #1 on:** April 21, 2017, 01:40:02 pm »

Quote from: FallonXay on April 21, 2017, 12:53:27 pm

Hello!
I'm having a ton of trouble with proofs in discrete maths ( I can barely do any questions )
I've posted a few questions below (Q13, 15a, 16 b/c) any help would be greatly appreciated!
Thanks.

Remember, in discrete mathematics they are EXTREMELY fussy about how your proofs are set out. For these proofs, I'll reduce my explanation but at the reward of structuring my answer the exact same way I would've structured it in the exam. If you post any more from here onwards, I will focus more on explanation, but my proof will be all over the place and it'll be up to you to reconstruct it logically (keeping any necessary and omitting any extraneous details)

Proofs are long so I'm also split posting.

For Q13, the trick was to identify that the LHS took the form (2n)!/n!
$\text{Let }n \in \mathbb{N}\text{. Then}$
$\begin{align*}(n+1)(n+2)\dots(2n-1)(2n)&=\frac{1.2.3.4\dots (2n-1)(2n)}{1.2.3.4\dots (n-1)(n)}\\ &= \frac{(2n)!}{1.2.3\dots(n-1)(n)}\\ &= \frac{2^n (2n)!}{2^n(1.2.3 \dots (n-1)(n)}\\ &= \frac{2^n [1.2.3.4.5.6\dots(2n-2)(2n-1)(2n)]}{2.4.6\dots (2n-2)(2n)}\\ &=2^n.1.3.5 \dots (2n-1) \end{align*}$

RuiAce · « **Reply #2 on:** April 21, 2017, 02:17:42 pm »

$\text{Let }a,n\in \mathbb{Z}^+ \backslash \{1\}$
This proof involves prime numbers. So somewhere in here we will use proof by contrapositive.
$\text{Suppose }a^n-1\text{ is prime}\\ \text{Consider }a^n-1 = (a-1)(a^{n-1}+a^{n-2}+\dots+a+1)$
Note: It is assumed that you know the formula for the sum of a G.P. Note also that the above factorisation is irreducible over Z.
$\text{Since }a^n-1\text{ is prime, one of these factors must be 1}\\ \text{If }a-1 = 1\text{, then }a=2$
$\text{If } a^{n-1}+a^{n-2}+\dots+a+1=1\text{ we have no solution}\\\text{as }n>1\text{ and }a>1 \implies 1+a+a^2+\dots+a^n > 1$
$\text{Hence }a=2.\text{ It falls to prove that }n\text{ is prime.}$
$\text{Suppose the contrapositive: }n\text{ is composite.}\\ \text{Then, }n = km\text{ where }1 < k,m < n$
$a^n-1 = (a^k-1)\left(\left(a^k\right)^{m-1}+\left(a^k\right)^{m-2}+\dots+a^k + 1\right)$
$\text{Since }a=2\text{ we have}\\ 1 = a^1-1 < a^k-1 < a^m -1\\ \text{Hence }a^k-1\text{ is a factor of }a^n-1\text{ that's not }1\text{ or }a^n-1\\ \text{Hence }a^n-1\text{ is composite}$
$\text{As the contrapositive is true}\\ \text{If }a^n-1\text{ is prime, }n\text{ is prime}$
If you just rearrange the formula by multiplying that denominator to the left, you get the factorisation trick I used.
$\text{The converse is that if }a=2\text{ and }n\text{ is prime, then }a^n-1\text{ is prime.}\\ \text{False: Let }a=2\text{ and }n=11\text{ which is prime}\\<br />\text{Then }a^n-1 = 2^{11}-1 = 2047 = 23\times 89\\ \text{So }a^n-1\text{ is composite.}$

FallonXay · « **Reply #3 on:** April 21, 2017, 02:38:58 pm »

Quote from: RuiAce on April 21, 2017, 01:40:02 pm

Remember, in discrete mathematics they are EXTREMELY fussy about how your proofs are set out. For these proofs, I'll reduce my explanation but at the reward of structuring my answer the exact same way I would've structured it in the exam. If you post any more from here onwards, I will focus more on explanation, but my proof will be all over the place and it'll be up to you to reconstruct it logically (keeping any necessary and omitting any extraneous details)

Thanks Rui you life saver!

Also, would you have any tips on knowing when to use contrapositive, direct proofs or contradictions? (Besides a lot of practice :p )

RuiAce · « **Reply #4 on:** April 21, 2017, 02:41:36 pm »

$\text{If }n=30\text{, then take }a=5\text{ and }b=6\\ \text{Clearly, }30 \mid 30\\ \text{But }30 \nmid 5\text{ and }30\nmid 6\\ \text{Hence the statement is false}$
________________________________
$\text{In general, we are trying to prove that}\\ \text{There exists }a,b\in \mathbb{Z}\text{ such that }n\mid ab\text{ and }n\nmid a, n\nmid b$
$\text{Suppose }n\text{ is composite. Then we may write}\\ n=km\\ \text{ where }1 < k,m < n$
It may help to stare really hard at the proof in part b) where we had a numeric example.
$\text{Take }a=k\text{ and }b=m\\ \text{Then }n=km = ab = 1\times ab \text{ so }n \mid ab\\ \text{but }n \nmid k \text{ as }k < n\\ \text{and }n \nmid m\text{ as }m < n\\ \text{Hence the result is false.}$

RuiAce · « **Reply #5 on:** April 21, 2017, 02:42:40 pm »

Quote from: FallonXay on April 21, 2017, 02:38:58 pm

Thanks Rui you life saver!

Also, would you have any tips on knowing when to use contrapositive, direct proofs or contradictions? (Besides a lot of practice :p )

Hmm.

"Contra-" proofs appear mostly in irrationality and prime/composite numbers. It is advised that you attempt proof by contradiction if you can't figure out why it must be right, but you do know why the negation is just blatantly wrong.

FallonXay · « **Reply #6 on:** April 21, 2017, 02:57:11 pm »

Quote from: RuiAce on April 21, 2017, 01:40:02 pm

$\begin{align*}(n+1)(n+2)\dots(2n-1)(2n)&=\frac{1.2.3.4\dots (2n-1)(2n)}{1.2.3.4\dots (n-1)(n)}\\ &= \frac{(2n)!}{1.2.3\dots(n-1)(n)}\\ &= \frac{2^n (2n)!}{2^n(1.2.3 \dots (n-1)(n)}\\ &= \frac{2^n [1.2.3.4.5.6\dots(2n-2)(2n-1)(2n)]}{2.4.6\dots (2n-2)(2n)}\\ &=2^n.1.3.5 \dots (2n-1) \end{align*}$

In the 4th line, what happened to the 2^n in the denominator?

RuiAce · « **Reply #7 on:** April 21, 2017, 02:58:08 pm »

Quote from: FallonXay on April 21, 2017, 02:57:11 pm

In the 4th line, what happened to the 2^n in the denominator?

Note that there are n terms.

I multiplied 2 to EACH of the n terms. This requires n lots of 2s to multiply, i.e. 2^n.

Essentially I expanded it in. Note how the denominator goes from $1.2.3\dots (n-1)(n)$ to $2.4.6\dots (2n-2)(2n)$

FallonXay · « **Reply #8 on:** April 21, 2017, 03:03:49 pm »

Quote from: RuiAce on April 21, 2017, 02:58:08 pm

Note that there are n terms.

I multiplied 2 to EACH of the n terms. This requires n lots of 2s to multiply, i.e. 2^n.

Essentially I expanded it in. Note how the denominator goes from $1.2.3\dots (n-1)(n)$ to $2.4.6\dots (2n-2)(2n)$

Sorry, I don't quite understand how you expanded it? wouldn't you have to multiply it out by 2^n to get (2^n) x (2 x 2^n) x ... x (n x 2^n)?

RuiAce · « **Reply #9 on:** April 21, 2017, 03:11:53 pm »

Quote from: FallonXay on April 21, 2017, 03:03:49 pm

Sorry, I don't quite understand how you expanded it? wouldn't you have to multiply it out by 2^n to get (2^n) x (2 x 2^n) x ... x (n x 2^n)?

$\begin{align*}2^n.1.3.5\dots (n-1)(n) &= \underbrace{2.2.2. \dots .2.2}_{n\text{ terms}}.1.3.5\dots (n-1)(n)\\ &= (2\times 1)(2\times 3)(2\times 5)\dots (2\times (n-1))(2\times n)\tag{rearranging}\\ &= 2.4.6\dots (2n-2)(2n)\end{align*}$
I only multiplied 2 to every term. Not the bulky 2^n to every term.

FallonXay · « **Reply #10 on:** April 21, 2017, 03:13:47 pm »

Quote from: RuiAce on April 21, 2017, 03:11:53 pm

$\begin{align*}2^n.1.3.5\dots (n-1)(n) &= \underbrace{2.2.2. \dots .2.2}_{n\text{ terms}}.1.3.5\dots (n-1)(n)\\ &= (2\times 1)(2\times 3)(2\times 5)\dots (2\times (n-1))(2\times n)\tag{rearranging}\\ &= 2.4.6\dots (2n-2)(2n)\end{align*}$

Ohhhhhh, very nice. Thanks

FallonXay · « **Reply #11 on:** April 21, 2017, 04:01:46 pm »

Hello,

how would you prove the following question attached?

(Thanks in advance!)

RuiAce · « **Reply #12 on:** April 21, 2017, 04:15:04 pm »

Quote from: FallonXay on April 21, 2017, 04:01:46 pm

Hello,

how would you prove the following question attached?

(Thanks in advance!)

This one requires a bit of skillful thinking and preferably an abuse of notation to go with it.

(The chapter and question reference is given in your screenshot. If there's any line in the proof they gave that troubles you feel free to bring it up.)

FallonXay · « **Reply #13 on:** April 22, 2017, 10:17:06 am »

Quote from: RuiAce on April 21, 2017, 04:15:04 pm

This one requires a bit of skillful thinking and preferably an abuse of notation to go with it.

(The chapter and question reference is given in your screenshot. If there's any line in the proof they gave that troubles you feel free to bring it up.)

I'm assuming the '10' in the answers are factorising out the decimal places? But how do they know what powers to put it to? (i.e 10^m, 10^(r-1), etc)?

RuiAce · « **Reply #14 on:** April 22, 2017, 10:40:54 am »

Quote from: FallonXay on April 22, 2017, 10:17:06 am

I'm assuming the '10' in the answers are factorising out the decimal places? But how do they know what powers to put it to? (i.e 10^m, 10^(r-1), etc)?

The idea is that in general (i.e. not always), a decimal number that is rational has one part that is terminating, and a part after it that's recurring.

E.g. $\frac1{12}=0.083333333\dots=0.08\overline{3}$
The $0.08$ part is the terminating part
The $0.00\overline{3}$ is the recurring part

m and r are integers made to distinguish the purpose. Note that this is a proof where you would say let m and n be blah, not 'suppose' m and n be blah.

I believe that the question wants you to take the first r decimal places (or r-1, you can figure that little thing out) to be the terminating part, and the NEXT m-r decimal places to be the recurring part.

Search the forums now!

We have moved!

Author Topic: Discrete Maths (Read 18559 times) Tweet Share

FallonXay

Discrete Maths

RuiAce

Re: Discrete Maths - Proofs Questions

RuiAce

Re: Discrete Maths - Proofs Questions

FallonXay

Re: Discrete Maths - Proofs Questions

RuiAce

Re: Discrete Maths - Proofs Questions

RuiAce

Re: Discrete Maths - Proofs Questions

FallonXay

Re: Discrete Maths - Proofs Questions

RuiAce

Re: Discrete Maths - Proofs Questions

FallonXay

Re: Discrete Maths - Proofs Questions

RuiAce

Re: Discrete Maths - Proofs Questions

FallonXay

Re: Discrete Maths - Proofs Questions

FallonXay

Re: Discrete Maths - Proofs Questions

RuiAce

Re: Discrete Maths - Proofs Questions

FallonXay

Re: Discrete Maths - Proofs Questions

RuiAce

Re: Discrete Maths - Proofs Questions

Recent Posts

User:
Password: