PadhaikoAll subjects

Past exam question: 2081 Chaitra (Regular), Q1(a)(ii)

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: Induction, Diagonalization & Pigeonhole Principle

Question

Using the principle of mathematical induction. Show that .

Solution

Base Step Verification: Let the proposition be:

For base case :

Since , the base step holds true.

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

Inductive Step: We must prove that is true, that is:

Starting with the LHS of and applying the inductive hypothesis:

The equality holds for . By the principle of mathematical induction, the identity holds for all integers .

Answer:

The base case holds for (). Assuming the identity holds for , adding and factoring yields , completing the inductive step. Thus, the identity holds for all .

All past exam questions for Theory of Computation