PadhaikoAll subjects

Past exam question: 2082 Kartik (Back), Q1(b)(ii)

Theory of Computation · 2 marks

Open in the Padhaiko app

Topic: Induction, Diagonalization & Pigeonhole Principle

Question

Prove that is divisible by 3 using the principle of mathematical induction.

Solution

Base Step Verification: Let be the statement that is divisible by for all integers (or ).

For base case :

Since is divisible by , is true. (For : , which also holds).

Inductive Hypothesis and Inductive Step: Inductive Hypothesis: Assume that is true for some positive integer , i.e.:

Inductive Step: We need to show that is true, i.e., is divisible by .

Since is an integer, is also an integer. Hence, is a multiple of .

By the principle of mathematical induction, is divisible by for all integers .

Answer:

Base case gives , divisible by . Assuming , we have , completing the inductive step. Thus, is divisible by for all .

All past exam questions for Theory of Computation