# Theory of Computation: Question Set – 07

#### What is a proof by exhaustion?

A proof by exhaustion is a technique used to prove a statement by showing that it holds true for all possible cases. This method is only practical for small or finite sets of cases, and is often used in combinatorics or number theory problems where the number of cases is manageable. The method involves showing that the statement holds true for each individual case, or by dividing the cases into smaller subcases that can be analyzed separately.

#### What is a direct proof?

A direct proof is a method of proof where one starts with the given assumptions and shows, step by step, how the conclusion logically follows from these assumptions.

#### What is an indirect proof?

An indirect proof is a method of proof where one assumes the negation of the conclusion and then shows that this leads to a contradiction. This shows that the original conclusion must be true.

#### What is a proof by contradiction?

A proof by contradiction is a type of indirect proof where one assumes the negation of the conclusion and then shows that this leads to a contradiction. This shows that the original conclusion must be true.

#### What is a proof by contraposition?

A proof by contraposition is a type of direct proof where one shows that the contrapositive of the original statement is true. The contrapositive of a statement is formed by negating both the hypothesis and conclusion of the original statement and reversing their order.

#### What is mathematical induction?

Mathematical induction is a method of proof used to prove that a statement is true for all natural numbers. The proof involves showing that the statement is true for a base case, usually n = 1, and then showing that if the statement is true for any arbitrary natural number n, then it must also be true for n + 1.

#### What is strong induction?

Strong induction is a variant of mathematical induction that allows us to assume that the statement is true for all natural numbers up to a certain point, not just for the immediate predecessor. The proof involves showing that the statement is true for a base case, and then showing that if the statement is true for all natural numbers up to n, then it must also be true for n + 1.

#### What is structural induction?

Structural induction is a method of proof used to prove that a property holds for all elements of a certain data structure. The proof involves showing that the property holds for the base case (the smallest element of the data structure) and then showing that if the property holds for all sub-elements of a certain element, then it must also hold for that element.