Explain strong induction in detail. What is recursively defined function? Use mathematical induction to prove 7ⁿ⁺² + 8²ⁿ⁺¹  is divisible by 5

State pigeonhole principle. Solve the recurrence relation a_n = 5a_n-1 – 6a_n-2 with initial conditions a₀ = 1 and a₁ = 3.

State max flow min cut theorem. Find the value of maximal flow in the graph below:

Explain the principle of inclusion and exclusion. How many integers from 1 to 30 are multiples of 2 or 3?

Give the example of ceiling, floor and boolean function. How do you plot the graph of the function?

Using Chinese remainder theorem solve the following congruences.

x = 1 (MOD 3)

x = 3 (MOD 5)

x = 6 (MOD 7)

Find the multiplicative inverse of 4 in Z₁₁ using extended euclidean algorithm.

Express the following sentences using quantifier.

a. Not all people are loyal.

b. Everybody loves somebody.

c. Someone has passed the exam.

d. Aquatic animals can’t live without water.

e. Some subjects are not interesting.

What is proof by contradiction? Give a proof by contradiction to show that if 3n+2 is odd then n is odd.

State the necessary conditions for two graphs to be isomorphic. How many different words from “MANAGER” can be generated with or without meaning?

Define symmetric closure. What is the symmetric closure of the relation R = {(1,1), (1,2), (2,2), (2,3), (3,1), (3,2)} on the set A = {1,2,3}?

Represent following graph using adjacency matrix.