PadhaikoAll subjects

Past exam question: 2082 Chaitra (Regular), Q1(b)

Theory of Computation · 2 marks

Open in the Padhaiko app

Topic: Induction, Diagonalization & Pigeonhole Principle

Question

Using mathematical induction show that for every integer the number is a multiple of 13.

Solution

Base Step Verification: Let be the proposition that is divisible by for integer .

For :

Since , is divisible by . Thus, the base step holds true.

Inductive Hypothesis and Inductive Step: Inductive Hypothesis: Assume that is true for an arbitrary integer , which means:

This implies .

Inductive Step: We must show that is true, i.e., is a multiple of .

Evaluate the expression for :

Since and , the quantity is an integer. Hence, is a multiple of .

By the principle of mathematical induction, is a multiple of for all integers .

Answer:

The proposition holds for the base case (). Assuming it holds for , algebraic rewriting yields , completing the inductive step. Thus, is a multiple of for all .

All past exam questions for Theory of Computation