1d. Problems: Proof Techniques

Question 1

for ints a&b, if a&b are odd then ab = odd
   there exists x -> a = 2x+1
   there exists y -> b = 2y+1
must prove ab=odd, z -> ab = 2z + 1
This is an example of...

Answer 1

Proof by Construction
use multiplication to prove that z exists
ab = (2x+1)(2y+1)
=4𝑥𝑦+2𝑥+2𝑦+1 
=2(2𝑥𝑦+𝑥+𝑦)+1
z = 2xy + x + y

Question 2

Prove by Contradiction

A ⋂ B=Ø, C ⊆ B, then [PROVE] A ⋂ C = Ø

Answer 2

prove A&C have nothing in common
1.Assume y = false
Assume: A⋂C != Ø: there is an element (x) that’s in both A and C
2. since C ⊆ B, element (x) in C must be an element of B
3. from 1) x ∈ A
x ∈ A and x ∈ B implies A ⋂ B != Ø which contradicts fact
therefore assumption in 1 is invalid bc A ⋂ C = Ø

Question 3

Proof by Induction Example

summation from i=0 to n

Answer 3

= n(n+1) / 2
prove left = right
1.show expression is true for n = 0
2.assume true for n = k >=0
3.consider n = k=1
...confused

Question 4

|A| = k, how many binary relations are there on A?

Answer 4

What is the size of the power set?

|P(AxA) = 2^k^2

Question 5

G = undirected graph, k nodes, max number of edges(no self loops) can can have = ?

Answer 5

k
2

k choose 2

Question 6

B1: Gold not here
B2: Gold not here
B3: Gold in box 2
only one is true, 2 are false

Answer 6

option 1 (b1 ⋂!b2 ⋂!b3)
option 2 (!b1 ⋂ b2 ⋂ !b3)
option 3 (!b1 ⋂ !b2 ⋂ !b3)
...
assume !b1 is correct ⋂ !!b2 ⋂ !b3
therefore b2 ⋂ !b2 is always false
therefore gold in B2