Answer to Question #94495 in Discrete Mathematics for Sim Grewal

Question

1. For integers a and b,if ab is odd, then a and b are odd.

2. If xy=(x +y)^2 / 4 ,then x=y. prove the following 2 statements, state the method used and explain all necessary steps.

3.Suppose that factorial is the Python function defined below. Use this function to give a
proof by induction of the statement: For all n ∈ N, factorial(n)= n!. def factorial(n):
if n==0:
return 1
elif n==1:
return 1
else:
return factorial(n-1)∗n

Answer 1

1) ab is odd, ab = 2k+1. Let's suppose that a(or b) is even, then a(or b) is equal to 2m. But a(or b) is a divisor of ab, so 2m is a divisor of 2k+1, it's impossible, so a(or b) cannot be even.

2) First of all, we have Cauchy's inequality:

$$x+y \ge 2\sqrt{xy}$$

(Equality, if $x=y$ )

$(x+y)^2 \ge 4xy$

$=> xy=\frac{(x+y)^2}{4},$ if $x=y.$

3) It's easy to check that function is correct for n=1 and n=0, let's suppose that it works for n=N (factorial(N) = N!), now we have to prove that it works for n=N+1 (factorial(N+1) = (N+1)!).

Function factorial (N+1) will perform this line:

return (factorial (N))* (N+1)

So it'll return N! * (N+1) = (because factorial (N) is equal to N! - as we supposed) = (N+1)!

Function's correctness is proven using the induction.