Induction On Divisibility and Inequalities

Induction On Divisibility and Inequalities

What is it?

Divisibility: show 3 divides 4^n - 1, or 7 divides 3^{2n}-1, school-style. Write 4^{k+1}-1 = 4(4^k-1) + 3, so the extra is clearly a multiple of 3. Inequalities: (1+x)^{n} >= 1+n x for x>=-1, n>=1 (Bernoulli named if the book has it). Meaning: factor or add a clearly positive/divisible leftover.

In simple words

• Divisibility: show 3 divides 4ⁿ - 1, or 7 divides 3²ⁿ-1, school-style.
• Write 4^k+1-1 = 4(4^k-1) + 3, so the extra is clearly a multiple of 3.
• Inequalities: (1+x)ⁿ >= 1+n x for x>=-1, n>=1 (Bernoulli named if the book has it).
• Write 4^k+1-1 as 4(4^k-1)+3 so both pieces are visibly multiples of 3.

Important terms

INDUCTION ON DIVISIBILITY AND INEQUALITIES: Divisibility: show 3 divides 4^n - 1, or 7 divides 3^{2n}-1, school-style. Write 4^{k+1}-1 = 4(4^k-1) + 3, so the extra is clearly a multiple of 3. Inequalities: (1+x)^{n} >= 1+n x for x>=-1, n>=1 (Bernoulli named if the book has it). Meaning: factor or add a clearly positive/divisible leftover.

1. DIVIDES: P(n): m divides f(n). IH: f(k)=m t. Aim: f(k+1)=m s. Algebra: f(k+1) = (something)*f(k) + (multiple of m).

2. INEQUALITIES: Assume P(k), multiply both sides by a positive number, or add a positive term. Track the direction of >= . Base often n=1 or n=2 as stated.

What you should learn

• State the main ideas and notation used in induction on divisibility and inequalities.
• Apply the rules of induction on divisibility and inequalities in a clear, step-by-step solution.
• Check signs, conditions, and the final answer for mathematical accuracy.

Examples

• 4^k+1-1 = 4(4^k-1)+3
• 3 | 3 and 3 | IH piece
• State m divides both

DIVIDES

P(n): m divides f(n). IH: f(k)=m t. Aim: f(k+1)=m s. Algebra: f(k+1) = (something)*f(k) + (multiple of m).

INEQUALITIES

Assume P(k), multiply both sides by a positive number, or add a positive term. Track the direction of >= . Base often n=1 or n=2 as stated.

Full school-level explanation

Divisibility: show 3 divides 4^n - 1, or 7 divides 3^{2n}-1, school-style. Write 4^{k+1}-1 = 4(4^k-1) + 3, so the extra is clearly a multiple of 3. Inequalities: (1+x)^{n} >= 1+n x for x>=-1, n>=1 (Bernoulli named if the book has it). Meaning: factor or add a clearly positive/divisible leftover.

Divisible leftover, then inequalities:

WHAT — INDUCTION ON DIVISIBILITY AND INEQUALITIES

Divisibility: show 3 divides 4^n - 1, or 7 divides 3^{2n}-1, school-style. Write 4^{k+1}-1 = 4(4^k-1) + 3, so the extra is clearly a multiple of 3. Inequalities: (1+x)^{n} >= 1+n x for x>=-1, n>=1 (Bernoulli named if the book has it). Meaning: factor or add a clearly positive/divisible leftover.

RULE — 1. DIVIDES

P(n): m divides f(n). IH: f(k)=m t. Aim: f(k+1)=m s. Algebra: f(k+1) = (something)*f(k) + (multiple of m).

METHOD — 2. INEQUALITIES

Assume P(k), multiply both sides by a positive number, or add a positive term. Track the direction of >= . Base often n=1 or n=2 as stated.

WORKED EXAMPLE

Worked: 3 divides 4ⁿ-1, the step. 4^k+1-1 = 4*4^k - 1 = 4(4^k-1) + 3 3 divides (4^k-1) by IH 3 divides 3 so 3 divides the sum

DIVIDES

P(n): m divides f(n). IH: f(k)=m t. Aim: f(k+1)=m s. Algebra: f(k+1) = (something)*f(k) + (multiple of m).

Remember

• extract f(k)

Examples

• 4^k+1-1 = 4(4^k-1)+3
• 3 | 3 and 3 | IH piece
• State m divides both

INEQUALITIES

Assume P(k), multiply both sides by a positive number, or add a positive term. Track the direction of >= . Base often n=1 or n=2 as stated.

Remember

• keep the inequality direction

Examples

• Multiply by (1+x) if x>-1
• Show extra >= 0
• End at P(k+1)

How to answer a induction on divisibility and inequalities question

How it works

• Identify the given quantities, notation, and required result.
• Choose the matching rule and write it before substitution.
• Work one algebraic step at a time, keeping brackets and signs clear.
• Check restrictions, simplify the result, and verify it where possible.

Remember

• write the k+1 expression in terms of the k piece
• leftover must be divisible / positive
• 4(4^k-1)+3
• split into IH piece + 3
• extract f(k)
• keep the inequality direction
• write the k+1 expression in terms of the k piece
• leftover must be divisible / positive

How the ideas connect

Worked: 3 divides 4ⁿ-1, the step. 4^k+1-1 = 4*4^k - 1 = 4(4^k-1) + 3 3 divides (4^k-1) by IH 3 divides 3 so 3 divides the sum

Deeper understanding

Go beyond memorising Induction On Divisibility and Inequalities. Connect the definition to reasons, relationships, exceptions, and exam wording.

How the ideas connect

Worked: 3 divides 4ⁿ-1, the step. 4^k+1-1 = 4*4^k - 1 = 4(4^k-1) + 3 3 divides (4^k-1) by IH 3 divides 3 so 3 divides the sum

Common mistakes

Exam focus

Core Idea

1. DIVIDES

2. INEQUALITIES

Worked Example

Exam focus

Quick revision

• write the k+1 expression in terms of the k piece
• leftover must be divisible / positive
• 4(4^k-1)+3
• split into IH piece + 3
• INDUCTION ON DIVISIBILITY AND INEQUALITIES: Divisibility: show 3 divides 4ⁿ - 1, or 7 divides 3²ⁿ-1, school-style. Write 4^k+1-1 = 4(4^k-1
• 1. DIVIDES: P(n): m divides f(n). IH: f(k)=m t. Aim: f(k+1)=m s. Algebra: f(k+1) = (something)*f(k) + (multiple

Write 4^k+1-1 as 4(4^k-1)+3 so both pieces are visibly multiples of 3.

For long answers on Induction On Divisibility and Inequalities: define clearly → explain the main parts → give one example → state one exam caution.