Applications of Mathematical Induction in Inequalities and Recurrence Relations: Worked Proofs

You may remember the base case, hypothesis and inductive step, yet still get stuck when the next step needs an extra inequality or a recurrence reaches back to earlier terms. Each case requires a stated starting index and a stated hypothesis. The method belongs to the wider GATE CS Exam Preparation route, while the essential work remains mathematical.

1. Mathematical induction: define the claim, domain and proof obligation

Let P(n) be a proposition indexed by an integer. To prove it for every n >= n0, prove P(n0), assume P(k) for an arbitrary integer k >= n0, and use that assumption to prove P(k+1). The hypothesis is temporary and belongs only to the chosen k. It does not permit us to assume every later case.

Before doing algebra, ask three questions: What exactly is P(n)? Where does it begin? How many earlier cases does the next case need? A first-order recurrence normally needs one base value, while a second-order recurrence needs two. In the domino picture, the base starts the chain and the step connects each admissible k to k+1. Checking only P(4), P(5) and P(6) cannot prove the infinite tail.

2. Induction for inequalities: prove 2^n >= n^2 for every integer n >= 4

Define P(n) as 2^n >= n^2 for integers n >= 4. At the base, 2^4 = 16 and 4^2 = 16, so equality holds. The threshold matters: at n = 3, 2^3 = 8 < 9 = 3^2. The claim cannot begin at 3.

Now take an arbitrary integer k >= 4 and assume 2^k >= k^2. Multiplication by the positive number 2 preserves the direction:

2^(k+1) = 2 x 2^k >= 2k^2.

That is only an intermediate bound. The required bridge is

2k^2 - (k+1)^2 = k^2 - 2k - 1 = (k-1)^2 - 2.

Because k >= 4, this difference is at least 3^2 - 2 = 7 > 0. Therefore 2k^2 >= (k+1)^2. Combining the two comparisons gives

2^(k+1) >= 2k^2 >= (k+1)^2.

Thus P(k+1) holds. By induction, 2^n >= n^2 for every integer n >= 4, not for every positive integer.

3. Inequality induction needs a bridge estimate and the correct starting point

An inductive hypothesis often produces an intermediate bound, not the final target. Here, 2^(k+1) >= 2k^2 becomes useful only after the separate proof that 2k^2 >= (k+1)^2. Leaving out that bridge leaves the argument unfinished.

Use a three-line diagnostic. First, check the sign of anything used to multiply or divide an inequality. Second, reduce the remaining comparison to an expression whose sign you can establish. Third, use the stated domain. Multiplication by 2 is safe because 2 is positive, and k >= 4 gives (k-1)^2 - 2 >= 7.

Sampling is different from proof. The values at n = 4, 5, 6 give 16 >= 16, 32 >= 25, and 64 >= 36. They support the conjecture but cannot replace an arbitrary-k step. A failed small case may change n0; it cannot be silently ignored.

4. Induction for a first-order recurrence: verify a_n = 2^n - 1

Consider a_1 = 1 and a_n = 2a_{n-1} + 1 for n >= 2. The first terms are

a_2 = 2(1) + 1 = 3, a_3 = 2(3) + 1 = 7,

a_4 = 2(7) + 1 = 15, a_5 = 2(15) + 1 = 31.

These values suggest a_n = 2^n - 1, but they do not prove it. For the base case, a_1 = 1 = 2^1 - 1. For an arbitrary k >= 1, assume a_k = 2^k - 1. Start from the recurrence and substitute the established hypothesis:

a_{k+1} = 2a_k + 1 = 2(2^k - 1) + 1 = 2^(k+1) - 1.

This is the claimed formula at k+1, so induction verifies it for every n >= 1. Generating terms helped us discover a likely formula; induction proved it. For comparison, the Master Theorem for GATE addresses divide-and-conquer recurrences, not the first-order recurrence used here.

5. Strong induction for a second-order recurrence: two earlier values mean two base cases

Let b_0 = 0, b_1 = 1, and b_n = 3b_{n-1} - 2b_{n-2} for n >= 2. Then b_2 = 3(1) - 2(0) = 3 and b_3 = 3(3) - 2(1) = 7, suggesting b_n = 2^n - 1.

Both bases are required: b_0 = 0 = 2^0 - 1 and b_1 = 1 = 2^1 - 1. For an arbitrary k >= 1, assume the formula for the two values needed, b_k = 2^k - 1 and b_{k-1} = 2^(k-1) - 1. Then

b_{k+1} = 3b_k - 2b_{k-1}

= 3(2^k - 1) - 2(2^(k-1) - 1)

= 3 x 2^k - 2^k - 1 = 2^(k+1) - 1.

Strong induction permits assumptions for all established cases through k, although this recurrence uses only k and k-1. Without either base, the proof cannot launch the case b_2.

How many initial values a recurrence gives you decides how many base cases you must verify.

6. Common induction traps: circular steps, missing bases and index errors

Use the arithmetic as a self-check. The first recurrence must give 1, 3, 7, 15, 31; the second must begin 0, 1, 3, 7. Any proposed closed form that misses an initial value is already disproved.

7. Applications of induction in exam-style questions

Typical assessment prompts ask you to choose a valid base index, fill a missing inequality bridge, detect a circular step, infer a closed form from initial recurrence terms, verify a proposed formula, or decide how many bases an order-2 recurrence requires.

Use this solve order: write P(n) and its domain; verify every required base; state exactly what is assumed at k; substitute that hypothesis into the expression for k+1; reduce the remaining target to an identity or sign check; then state the quantified conclusion. Audit your work against n = 4, the lower bound 7, and the sequences 1, 3, 7, 15, 31 and 0, 1, 3, 7. For wider practice, use the Discrete Mathematics MCQs; induction on its own carries only a small set of practice questions there.

8. Mathematical induction short version and the next useful step

The retrieval chain is short: define the indexed claim, start at the first true integer, assume only the allowed earlier case or cases, transform the k+1 expression, and finish at the exact target. Here the outputs are 2^n >= n^2 for n >= 4, and 2^n - 1 for both recurrences under their different initial conditions.

Now reproduce (k-1)^2 - 2 >= 7 and 1, 3, 7, 15, 31 from memory. GATE Guidance by Sanchit Sir offers a structured GATE CS route with a Discrete Mathematics module. For broader mathematical foundations as a separate next step, use Engineering Mathematics for GATE Exam.