Theory of Computaion

Give the answer of the following questions:

1. What is principle of mathematical induction? Explain types of it. Also what is need of those PM’s'?
2. What do you understand by strong principle of mathematical induction? How it is different from mathematical induction? Give an example of a statement where you require strong principle of mathematical induction.

Prove the following using weak pmi:

1. Prove that integer bigger than 2 have prime factorization.
2. Define: The principle of mathematical induction. Also prove for any string x and n>=0 REV (xy) =REV(y) REV(x).

Strong PMI: Suppose p(n) is a statement involving an integer n, then to prove that p(n) is true for every n>= n₀ it is sufficient to show two thing.

1. P(n₀) is true
2. For any k>=n₀, if p (n) is true, for every n satisfying n₀<=n<=k then p (k+1) is true.

Prove the following using strong pmi:

1. For any n>=2, n is either prime or product of two (or more) prime.
2. Every positive integer is the product of power of 2 and an odd integer.
3. a₀=-2, a₁=-2 for any n>=2 an=5a_n-1-6a_n-2, prove that for every n>=0 a_n=2*3ⁿ-4*2ⁿ

Recursive Definitions:

1. Factorial of a number
2. Fibonacci Series Function
3. Set N of all natural numbers
4. Finite Subset of the natural Numbers
5. Palindrome language
6. Set S of all integer(positive and negative) divisible by 7
7. Set S of all integer divisible by 2 or 7
8. The set U of all strings in {0,1}* containing the substring 00
9. The set V of all strings of the form 0ⁱ1^j, where j<=i<=2j
10. The set W of all strings of the form 0ⁱ1^j, where i>=2j
11. Fully Parenthesized Algebraic Expression