Discrete Math Study Plan: Induction, Number Theory, Counting

Unit-2: Discrete Mathematics – Study Plan (Complete Breakdown)

This unit has three big parts:

1. Mathematical Induction

2. Number Theory (Arithmetic)

3. Counting Techniques

I will explain what to cover inside each part, step by step.

1. Principles of Mathematical Induction

This part is very important for exams and proofs.

Topics to cover:

• Meaning of Mathematical Induction

• Principle of Mathematical Induction (PMI)

• Structure of an induction proof

  • Base step

  • Induction hypothesis

  • Induction step

• Simple examples of induction

• Strong Mathematical Induction

• Comparison between simple induction and strong induction

2. The Well-Ordering Principle

This topic is closely related to induction.

Topics to cover:

• Definition of Well-Ordering Principle

• Explanation using natural numbers

• Relation between Well-Ordering Principle and Mathematical Induction

• Simple examples

• Use of Well-Ordering Principle in proofs

3. Recursive Definition

This topic explains how objects are defined step by step.

Topics to cover:

• Meaning of recursive definition

• Base case in recursive definition

• Recursive rule

• Examples of recursive sequences

• Difference between recursive and explicit definition

4. The Division Algorithm

This starts the number theory (arithmetic) part.

Topics to cover:

• Statement of Division Algorithm

• Explanation of terms: dividend, divisor, quotient, remainder

• Mathematical form of division algorithm

• Examples

• Important properties

5. Prime Numbers

Topics to cover:

• Definition of prime number

• Composite numbers

• Examples of prime numbers

• Properties of prime numbers

• Role of primes in number theory

6. Greatest Common Divisor (GCD)

Topics to cover:

• Definition of GCD

• GCD of two integers

• Properties of GCD

• GCD using factor method

7. Euclidean Algorithm

Very important and frequently asked.

Topics to cover:

• Meaning of Euclidean Algorithm

• Steps of the Euclidean Algorithm

• Finding GCD using Euclidean Algorithm

• Worked examples

• Why Euclidean Algorithm is efficient

8. Fundamental Theorem of Arithmetic

Topics to cover:

• Statement of the theorem

• Explanation in simple words

• Prime factorization

• Uniqueness of prime factorization

• Examples

9. Basic Counting Techniques

This starts the combinatorics part.

Topics to cover:

• What is counting in discrete mathematics

• Addition principle

• Multiplication principle

• Simple examples

10. Inclusion–Exclusion Principle

Topics to cover:

• Need for inclusion–exclusion

• Formula for two sets

• Formula for three sets

• Examples

• Applications in counting problems

11. Pigeon-Hole Principle

Short but very important.

Topics to cover:

• Definition of pigeon-hole principle

• Simple pigeon-hole principle

• Generalized pigeon-hole principle

• Examples

• Real-life type problems

12. Permutation

Topics to cover:

• Meaning of permutation

• Permutation of n objects

• Permutation with repetition

• Permutation without repetition

• Examples

13. Combination

Topics to cover:

• Meaning of combination

• Difference between permutation and combination

• Combination formula

• Examples

• Applications

Suggested Study Order

1. Mathematical Induction

2. Well-Ordering Principle

3. Recursive Definition

4. Division Algorithm

5. Prime Numbers

6. GCD

7. Euclidean Algorithm

8. Fundamental Theorem of Arithmetic

9. Basic Counting Techniques

10. Inclusion–Exclusion Principle

11. Pigeon-Hole Principle

12. Permutation

13. Combination

Meaning of Mathematical Induction

Mathematical induction is a method of proof used in mathematics to show that a statement is true for all natural numbers. Instead of checking the statement again and again for every number, induction gives a logical process to prove it for infinitely many cases in a finite number of steps. The idea is similar to climbing stairs: if you can step on the first stair, and if stepping on one stair always allows you to step on the next, then you can reach every stair. In the same way, induction proves that if a statement is true for the first natural number and true for one number implies it is true for the next, then the statement is true for all natural numbers.

• Mathematical induction is used to prove statements involving natural numbers like 1, 2, 3, …

• It is a method of proof, not a formula or theorem.

• It is mainly applied to prove results involving sums, inequalities, divisibility, and sequences.

• The logic of induction is based on implication: truth of one case leads to truth of the next.

• It helps in proving infinitely many cases in a finite number of steps.

Standard structure used in induction

• Base case: Show that the statement is true for the first natural number (usually n = 1).

• Induction assumption: Assume the statement is true for some natural number n = k.

• Induction step: Prove that the statement is true for n = k + 1.

Example (theory-level induction question)

Question: Prove that the sum of first n natural numbers is
n(n + 1) / 2.

Base case:
For n = 1,
Left side = 1
Right side = 1(1 + 1)/2 = 1
So, the statement is true for n = 1.

Induction assumption:
Assume the statement is true for n = k,
that is,
1 + 2 + 3 + … + k = k(k + 1)/2.

Induction step:
For n = k + 1,
1 + 2 + 3 + … + k + (k + 1)
= k(k + 1)/2 + (k + 1)
= (k + 1)(k + 2)/2

This matches the required formula for n = k + 1.

Hence, the statement is true for all natural numbers by mathematical induction.

Principle of Mathematical Induction (PMI)

The Principle of Mathematical Induction is a formal rule used to prove that a statement is true for all natural numbers. It is based on a logical chain idea. If a statement is true for the first natural number and if the truth of the statement for one natural number implies its truth for the next natural number, then the statement must be true for every natural number. This principle gives a solid foundation to the method of mathematical induction used in proofs.

Statement of Principle of Mathematical Induction

Let P(n) be a statement depending on a natural number n. If the following two conditions are satisfied, then P(n) is true for all natural numbers n ≥ 1.

• Base step: P(1) is true.

• Induction step: If P(k) is true for some natural number k, then P(k + 1) is also true.

Important points and concepts

• PMI is a logical principle, not a formula.

• It is used to prove statements for infinitely many natural numbers.

• The induction step connects two consecutive cases.

• The assumption that P(k) is true is called the induction hypothesis.

• If both base step and induction step are correct, the proof is complete.

Example (standard B.Tech exam question)

Question: Prove that
1 + 3 + 5 + … + (2n − 1) = n² for all natural numbers n.

Base step:
For n = 1,
Left side = 1
Right side = 1² = 1
So, P(1) is true.

Induction hypothesis:
Assume P(k) is true for some natural number k,
1 + 3 + 5 + … + (2k − 1) = k².

Induction step:
For n = k + 1,
1 + 3 + 5 + … + (2k − 1) + (2k + 1)
= k² + (2k + 1)
= (k + 1)²

Thus, P(k + 1) is true.

Hence, by the Principle of Mathematical Induction, the statement is true for all natural numbers.

Strong Mathematical Induction

Strong mathematical induction is an extension of the Principle of Mathematical Induction. In this method, instead of assuming that the statement is true for only one natural number, we assume it is true for all natural numbers up to a certain value. This stronger assumption helps in proving statements where the next step depends on more than just the immediately previous case. Even though the assumption looks stronger, the logic remains fully valid and is widely used in discrete mathematics and number theory.

Statement of Strong Mathematical Induction

Let P(n) be a statement defined for natural numbers n ≥ 1. If the following conditions are satisfied, then P(n) is true for all natural numbers.

• Base step: P(1) is true.

• Strong induction step: Assume P(1), P(2), P(3), …, P(k) are all true for some natural number k, and using this assumption, prove that P(k + 1) is true.

Important points and concepts

• Strong induction allows assuming multiple previous cases at the same time.

• It is useful when P(k + 1) depends on earlier values, not only on P(k).

• The base case may include more than one starting value if needed.

• Strong induction and simple induction are logically equivalent.

• This method is commonly used in proofs involving divisibility and recursive definitions.

Example (standard B.Tech exam question)

Question: Prove that every natural number greater than 1 can be written as a product of prime numbers.

Base step:
For n = 2,
2 is a prime number and hence can be written as a product of primes.

Induction hypothesis:
Assume that all natural numbers 2, 3, 4, …, k can be written as a product of primes.

Induction step:
Consider k + 1.

• If k + 1 is a prime number, then it is already a product of primes.

• If k + 1 is composite, then it can be written as a product of two smaller natural numbers, each less than k + 1.

By the induction hypothesis, both of these smaller numbers can be written as products of primes. Hence, k + 1 can also be written as a product of primes.

Therefore, the statement is true for all natural numbers greater than 1 by strong mathematical induction.

Well-Ordering Principle

The well-ordering principle states that every non-empty set of natural numbers has a smallest element. This principle is very important in discrete mathematics because it provides a foundation for many proofs, especially in number theory. Instead of moving step by step like induction, this principle starts from the idea that there must be a minimum element in any non-empty set of natural numbers. Many induction-based proofs can also be explained using the well-ordering principle.

Important concepts to remember

• The well-ordering principle applies only to natural numbers.

• It guarantees the existence of a least element, not just any element.

• It is a logical principle, not a formula.

• It is closely related to mathematical induction.

• Many proofs by contradiction use the well-ordering principle.

Standard exam-type questions and concepts

Question 1: State the Well-Ordering Principle

Answer:
Every non-empty set of natural numbers contains a smallest element.

Question 2: Explain the relation between Well-Ordering Principle and Mathematical Induction

• If a statement is false for some natural numbers, the set of all such numbers must have a smallest element.

• This smallest element leads to a contradiction when the base case and induction step are true.

• Hence, mathematical induction can be derived from the well-ordering principle.

Question 3: Prove that there is no smallest positive rational number

Proof using Well-Ordering Principle idea:
Assume there exists a smallest positive rational number r.
Then r/2 is also a positive rational number and r/2 < r.
This contradicts the assumption that r is the smallest.
Hence, no smallest positive rational number exists.

Question 4: Use Well-Ordering Principle to prove that every natural number greater than 1 has a prime divisor

Concept-based proof:

• Consider the set of natural numbers greater than 1 that do not have a prime divisor.

• Assume this set is non-empty.

• By the well-ordering principle, it has a smallest element n.

• n cannot be prime, so it must be composite.

• Hence, n = ab where 1 < a, b < n.

• By minimality of n, both a and b have prime divisors.

• This implies n also has a prime divisor, which is a contradiction.

Therefore, every natural number greater than 1 has a prime divisor.

Key exam tips

• Always state the principle clearly before using it in a proof.

• Most questions use contradiction + smallest element logic.

• This topic is often linked with prime numbers and factorization.

Question
Use the well-ordering property to show that if x and y are real numbers with x < y, then there exists a rational number r such that
x < r < y.

Solution (Using Well-Ordering Property)

Step 1: Start from the given condition
We are given that
x < y

So the difference
y − x > 0

Step 2: Consider a suitable set of natural numbers
Define the set

S = { n ∈ N | n(y − x) > 1 }

This set is non-empty because natural numbers increase without bound.

Step 3: Apply the Well-Ordering Property
Since S is a non-empty set of natural numbers, by the well-ordering property, S has a smallest element.

Let this smallest element be n.

So,
n(y − x) > 1

Step 4: Use the smallest n to form inequalities
From
n(y − x) > 1

We get
nx + 1 < ny

Step 5: Choose an integer m
There exists an integer m such that

nx < m < ny

This is possible because the distance between nx and ny is greater than 1.

Step 6: Define the rational number r
Let

r = m / n

Since m and n are integers and n is not zero, r is a rational number.

Step 7: Show that r lies between x and y
Divide the inequality

nx < m < ny

by n to get

x < m / n < y

That is,

x < r < y

Final Conclusion
Thus, using the well-ordering property, we have shown that there exists a rational number r such that

x < r < y.

Hence proved.

Recursive Definition

A recursive definition is a way of defining a function, sequence, or structure by giving its first value and then defining every next value using the previous ones. Instead of writing a direct formula, recursion builds the definition step by step. This method is very common in discrete mathematics because many objects are naturally defined in terms of smaller or earlier cases.

Important concepts to remember

• A recursive definition always has two main parts.

• The base case gives the starting value.

• The recursive rule explains how to get the next value from earlier values.

• Without a base case, a recursive definition is incomplete.

• Recursive definitions are used for sequences, functions, sets, and algorithms.

General form of a recursive definition

• Base case: Defines the value for the smallest input.

• Recursive step: Defines the value for n using values of smaller n.

Example 1

Question
Define the sequence recursively:
2, 4, 8, 16, …

Answer

Base case:
a₁ = 2

Recursive rule:
aₙ = 2aₙ₋₁ for n ≥ 2

Explanation
Each term is obtained by multiplying the previous term by 2, starting from 2.

Example 2

Question
Give a recursive definition of the sum of first n natural numbers.

Answer

Base case:
S(1) = 1

Recursive rule:
S(n) = S(n − 1) + n for n ≥ 2

Explanation
The sum up to n is obtained by adding n to the sum of the first n − 1 natural numbers.

Example 3

Question
Define factorial using recursion.

Answer

Base case:
0! = 1

Recursive rule:
n! = n × (n − 1)! for n ≥ 1

Explanation
Factorial of n is obtained by multiplying n with factorial of n − 1.

Difference between recursive and explicit definition

• Recursive definition depends on previous values.

• Explicit definition gives a direct formula for the nth term.

• Recursive definitions are easier to understand logically.

• Explicit formulas are faster for direct computation.

Key exam tips

• Always write base case first.

• Clearly mention the recursive rule.

• Do not miss conditions like n ≥ 1 or n ≥ 2.

• Many questions ask to convert a pattern into a recursive form.