virtual university of pakistan

Q#01: Use mathematical induction to prove that for every integer with . (Note that this inequality is false for and .) Marks = 6
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.

Q#02: Find the GCD of and using Division Algorithm. Marks = 4
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.


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