# MTH202 Discrete Mathematics Assignment 3 solution Fall 2012

Q#01: Use mathematical induction to prove that for every integer with . (Note that this inequality is false for and .) Marks = 6

Q#02: Find the GCD of and using Division Algorithm. Marks = 4

Q#03: Define a sequence by the formula , for all integers . Show that this sequence satisfies the recurrence relation , with and for all integers .

Solution:

question 1 solution:

BASIC STEP:

p(4) = 2^n

2^4 =16 < 24 = 4!

INDUCTIVE STEP:

For this step we assume that p(k) is true for posiive integer k with k>=4

Assume:

2^k < k!

2^k+1 < (k+1)!

2^k+1 = 2.2^k

<  2.k!

< (k+1)k!

= (k+1)!

So p(k+1) is true when p(k) is true.

Solution of question 2:

Let a= 4566891  and b=182  . Also, let’s introduce the variable “r” for the remainder

Let’s evaluate a/b  . It turns out that a/b  = 25092 remainder 147. What we’re are interested in is the remainder.

So let  . Now assign the value of “b” to “a” and the value of “r” to “b”.

So now a=182 ,b=147  and r=147

Now we must ask ourselves: “Does b=0?”. Since b=147 (which is NOT zero), we must start all over and keep going until “b” equals zero.
Let’s evaluate a/b  . It turns out that a/b= 182/147  = 1 remainder 35. What we’re are interested in is the remainder.

So let  . Now assign the value of “b” to “a” and the value of “r” to “b”.

So now a=147 ,b=35  , and r=35

Now we must ask ourselves: “Does b=0?”. Since b=35 (which is NOT zero), we must start all over and keep going until “b” equals to zero
Let’s evaluate a/b  . It turns out that a/b= 147/35  = 4 remainder 7. What we’re are interested in is the remainder.

So let  . Now assign the value of “b” to “a” and the value of “r” to “b”.

So now a=35 ,b=7 , and  r=7

Now we must ask ourselves: “Does b=0?”. Since b=7 (which is NOT zero), we must start all over and keep going until “b” equals zero.

Let’s evaluate a/b  . It turns out that a/b = 35/7  = 5 remainder 0. What we’re are interested in is the remainder.

So let  . Now assign the value of “b” to “a” and the value of “r” to “b”.

So now a=7 ,b=0  , and  r=0

Since the value of b is now zero, we can stop the process.
Now the value of “a” in the last row is the GCD of the numbers “a” and “b”
So this means that GCD(4566891,182)=7.