Proof questions in GATE CS rarely ask you to invent a long argument from nothing. They usually show a few steps and ask which one is valid, equivalent or fatally flawed. If contrapositive and converse still look interchangeable, or an induction step feels like magic, four clean proof patterns will fix the problem.
1. The four techniques and when each fits
A proof technique is a route from what is known to what must be shown. Choose it from the logical shape of the claim.
Direct proof: Assume the hypothesis P. Use definitions and valid implications until Q follows. This fits claims whose algebra moves naturally forward.
Proof by contrapositive: To prove “if P, then Q”, prove “if not Q, then not P”. These statements are logically equivalent, so either proves the other.
Proof by contradiction: Assume the statement is false and derive an impossibility, such as an integer being both even and odd.
Mathematical induction: Prove an initial case, assume the claim at an arbitrary index k, and show that this forces the claim at k + 1.
For a direct proof, take this claim: if a and b are even, then a + b is even. Write a = 2r and b = 2s. Then a + b = 2(r + s), so the sum is even by definition.
The logic underneath these choices is developed in Propositional and Predicate Logic: Truth Tables, Quantifiers and Inference. In particular, a truth table confirms why a conditional and its contrapositive agree while its converse need not.
2. Mathematical induction worked example: sum of the first n odd numbers
Consider the claim
1 + 3 + 5 + ... + (2n - 1) = n² for every integer n ≥ 1.
An induction proof needs all three parts below.
Base case. For n = 1, the left side is 1. The right side is 1² = 1. They match, so the statement is true at the starting value.
Inductive hypothesis. Assume the statement is true for an arbitrary k ≥ 1:
1 + 3 + 5 + ... + (2k - 1) = k².
Inductive step. The next odd number is
2(k + 1) - 1 = 2k + 1.
Add it to the sum covered by the hypothesis:
k² + (2k + 1) = k² + 2k + 1 = (k + 1)².
That is exactly the required expression at n = k + 1. The base case is true, and truth at k forces truth at k + 1, so the identity holds for every n ≥ 1.
Notice what was not assumed. We did not assume the formula at k + 1. We assumed it only at k and transformed that statement into the next one.
3. Proof by contrapositive: if n squared is even then n is even
Let the statement be: if n² is even, then n is even. A direct start from “n² is even” does not immediately expose the form of n. Its contrapositive is easier:
If n is odd, then n² is odd.
Write an odd integer as n = 2m + 1 for some integer m. Then
n² = (2m + 1)²
= 4m² + 4m + 1
= 2(2m² + 2m) + 1.
The final form is twice an integer plus 1, so n² is odd. The contrapositive is proved. Because a conditional and its contrapositive are logically equivalent, the original claim follows.
Keep the nearby statements separate. The converse is “if n is even, then n² is even”. It happens to be true here, but proving it would still not prove the original implication. The inverse is “if n² is not even, then n is not even”, which is equivalent to the converse, not the original.
4. Proof by contradiction: the square root of 2 is irrational
Assume the opposite of what we want: √2 is rational. Then √2 = p/q for integers p and q with q ≠ 0, written in lowest terms. Thus p and q have no common factor greater than 1.
Square both sides:
2 = p²/q², so 2q² = p².
Therefore p² is even. From the result in the previous section, p is even, so write p = 2r for some integer r. Substitute this into the equation:
2q² = (2r)² = 4r².
Divide by 2:
q² = 2r².
Now q² is even, so q is even too. Both p and q are divisible by 2, which contradicts the starting condition that p/q was in lowest terms. The assumption that √2 is rational must therefore be false. Hence √2 is irrational.
A contradiction must be a genuine logical impossibility. Reaching a large number, an unusual expression or an inconvenient case is not enough.
5. Strong induction and when it gives a more useful hypothesis
Ordinary, or weak, induction assumes the statement for k when proving it for k + 1. Strong induction may assume every case from the base through k. The two forms are logically equivalent in power, but strong induction gives a more convenient hypothesis for statements whose next case depends on an earlier case other than k.
For example, to show that every integer n ≥ 2 can be written as a product of primes, use 2 as the base. For k + 1, either k + 1 is prime, in which case it already is a product of one prime, or it is composite. If composite, write k + 1 = ab with 2 ≤ a, b ≤ k. The strong hypothesis gives prime products for both a and b, so their product gives one for k + 1.
Induction also checks a proposed closed form for a recurrence. Guessing the form is only the start; the base case and recurrence step establish it. Recurrence Relations in Discrete Mathematics for GATE is the natural next application.
6. The traps GATE builds these on
Watch for four recurring defects:
No valid base case. The inductive implication may be true while no starting value is established. The dominoes are aligned, but none is pushed.
Converse presented as contrapositive. For P implies Q, not Q implies not P is equivalent. Q implies P is a different claim.
No real contradiction. A proof must reach incompatible facts or violate a stated condition.
Circular induction. Assuming the k + 1 case while trying to prove the k + 1 case simply assumes the conclusion.
Also check the domain. A proof anchored at n = 2 says nothing about n = 1 unless that case is handled separately. Many identify-the-flaw questions hide the error in the starting index rather than the algebra.
7. How GATE tests proof techniques
Expect logical-equivalence MSQs, proof fragments with one invalid line, and induction fill-ins for sums or recurrences. A good practice method is to label every line with its justification: definition, hypothesis, algebra, known theorem or conclusion. A line with no valid label deserves suspicion.
These ideas sit in Discrete Mathematics. The organising IIT sets the current scope and any mark distribution, so confirm those details on the official GATE 2027 portal rather than carrying forward a remembered figure.
Start untimed until you can name each flaw, then move to short timed sets in the Engineering Mathematics course.
8. The short version and your next step
Use direct proof when the implication flows forward, contrapositive when the negated conclusion is easier, contradiction when the negation creates an impossibility, and induction for statements indexed by n. In induction, always identify the base, hypothesis and step explicitly.
Now reproduce the three worked proofs without looking, then test the distinctions in GATE Guidance by Sanchit Sir and mixed practice from the GATE category. The goal is not to memorise these exact examples. It is to recognise the proof shape before an option distracts you.
