Hi! Can someone please help me with this DISCRETE MATH exercises? Any help will

Question

Hi! Can someone please help me with this DISCRETE MATH exercises? Any help will be really appreciated and will rate ++! Thanks

1. Prove each problem using the indicated technique:

a) Direct Proof: Prove that the square of an even number is an even number.

b) Vacuous Proof: Show that all positive integers such that n=log2n are roots of a polynomial of the form ax3+bx2+cx+d (where a, b, c, and d are fixed integers).

c) Trivial Proof: Show that all prime numbers are of the form 3k or 3k+1 or 3k-1 where k is an integer.

d) Indirect Proof: n is even if and only if 5n2+2 is even (n is an integer).

e) Proof by Cases: Show that min(a, min(b, c))=min(min(a, b), c)) when a, b, and c are real numbers.

f) Constructive Proof: For every three natural numbers x, y, z larger than 1 (x, y, z > 1), there is some natural number larger than all x, y, z such that it is not divisible by x or y or z.

g) Non-constructive Existence Proof: Consider two numbers: 2x10500+15 and 2x10500+16. Prove that at least one of them is not a perfect square.

Explanation / Answer

This question has multiple sub-parts. I have solved four. Please post one more question for the same.

a)

I direct proof we assume and then proof.

assume n is even

so n=2k

now square of this = 2k^ 2 = 4k2

This can be written as 2*2*k2 . Since it is 2 times a number it will surely be even. Hence proofed.

c)

the above statement is true of any number.

Let us take an integer n now when n is divided by 3 reminder can be 0,1,2

In other words,
n= 3k
or
n = 3k + 1
or
n = 3k + 2
for some k

i.e.

n = 3k
or
n= 3k+1
or
n = 3(k+1) - 1
for some integer k

Hence it is true for any integer.

d)

In direct proof will be let us take 5n^2 + 2. If this is even that means that 5n^2 is even.

Now 5 is odd so n^2 should be even in order to make 5n^2 odd.

Since n^2 is even that means that n has to even because even*even = even.

Hence proofed.

e)

let us take this case when a>b>c

so min(a,mn(b,c)

=min(a,c)

=c

second side

min(min(a,b),c))

=min(b,c)

=c equal.

Now let us take another case when a<b<c

min(a,min(b,c)=min(a,b)=a

min(min(a,b),c))=min(a,c)=a Hence equal.

So they both are equal.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.