Unit 5: Natural Number

Natural Numbers 

Natural numbers are the numbers we use for counting objects in daily life.

Examples:

• 1, 2, 3, 4, 5, …
• Some books include 0 as a natural number, while some start from 1.

Uses in real life:

• Counting students in a class
• Numbering pages
• Counting money, items, days, etc.

Properties of Natural Numbers:

• They are positive whole numbers
• No fractions or decimals
• They go on forever (infinite)

Peano’s Axioms (Basics of Natural Numbers)

Peano’s axioms are basic rules that define natural numbers formally.
Think of them as the foundation rules of counting.

Peano’s Axioms (Explained Simply)

1. 0 is a natural number
   (Some systems start from 0)

2. Every natural number has a successor

   • Successor means next number

   • Example: Successor of 3 is 4, Successor of 10 is 11

3. 0 is not the successor of any number

   • No number comes before 0

4. Different numbers have different successors

   • If two numbers are different, their next numbers will also be different

5. Induction Axiom (Very Important)

   • If something is true for 0

   • And true for the next number whenever it is true for a number

   • Then it is true for all natural numbers

Why Peano’s Axioms are important:

• They give a logical base to mathematics
• Used to prove formulas and rules

Mathematical Induction

Mathematical induction is a method to prove statements that are true for all natural numbers.

Example:

Like climbing a ladder:

• If you can step on the first rung
• And from any rung you can go to the next rung
• Then you can climb the entire ladder

Steps of Mathematical Induction

Step 1: Base Case

Check whether the statement is true for the first number (usually 1 or 0).

Step 2: Induction Hypothesis

Assume the statement is true for some number n.

Step 3: Induction Step

Prove that if the statement is true for n, then it is also true for n + 1.

If all three steps work, the statement is true for all natural numbers.

Example:

Prove:
1 + 2 + 3 + … + n = n(n + 1)/2

• Base case: n = 1 → True
• Assume true for n
• Prove for n + 1
• Result: Statement is true for all n

Strong Mathematical Induction

Strong induction is similar to normal induction, but stronger.

Difference from Normal Induction

• In normal induction, we assume the statement is true for one number (n)
• In strong induction, we assume it is true for all numbers less than n

When to use Strong Induction?

• When a problem depends on multiple previous values

Used in:

• Factorization
• Fibonacci series
• Recursion problems

Steps of Strong Induction

1. Base Case – Check for the smallest value
2. Induction Hypothesis – Assume the statement is true for all values less than n
3. Induction Step – Prove it is true for n

Simple Understanding:

To reach step 10:

• You assume you can reach steps 1, 2, 3, … 9
• Then you prove you can reach step 10

Induction with Non-Zero Base Case

What does Non-Zero Base Case mean?

Sometimes, a statement does not start from 0 or 1.
It may start from 2, 3, or any other number.

Example: Prove something is true for n ≥ 3

Here:

• Base case is n = 3, not 1

Steps:

1. Verify the base case (e.g., n = 3)
2. Assume the statement is true for n
3. Prove it is true for n + 1

Why it is needed:

• Some formulas or conditions do not work for small numbers

Common in:

• Inequalities
• Series
• Algorithm analysis

Difference Summary 

Topic	Key Idea
Natural Numbers	Counting numbers
Peano’s Axioms	Basic rules of natural numbers
Mathematical Induction	Proves statements for all n
Strong Induction	Uses all previous cases
Non-Zero Base Induction	Base case starts from n ≠ 0 or 1

Recurrence Relation

A recurrence relation is an equation that defines a sequence using its previous terms.

In simple words:

“To find the next value, we use the previous values.”

Daily Life Example:

• Salary increases every year based on last year’s salary
• Population growth depends on last year’s population
• Fibonacci series (very common example)

Example:

$$a_n=a_{n-1}+2$$

If:

• $a_1 = 3$

Then:

• $a_2 = 5$

• $a_3 = 7$
  

• $a_4 = 9$
  

Parts of a Recurrence Relation:

1. Formula (relation between terms)
2. Initial condition(s) (starting value)

Types of Recurrence Relations

(A) Simple Recurrence Relation with Constant Coefficients

Meaning:

• Coefficients are fixed numbers
• Relation involves previous terms

General Form:

$$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_k{a}_{n-\mathrm{k}}$$

Where $c_1,c_2,...are\; constants.$

Example:

$$a_n=3a_{n-1}+2a_{n-\mathrm{2}}$$

Here:

• Coefficients: 3 and 2 (constants)

Fibonacci Example:

$$F_n=F_{n-1}+F_{n-\mathrm{2}}$$

(B) Linear Recurrence Relation Without Constant Term

Meaning:

• Linear combination of previous terms
• No standalone constant number

General Form:

$$a_n=c_1{a}_{n-1}+c_2{a}_{n-\mathrm{2}}$$

(No extra +5, +7, etc.)

Example:

$$a_n=2a_{n-1}-a_{n-\mathrm{2}}$$

This is:

• Linear
• Constant coefficients
• Without constant term

Important Note:

If a constant term exists, it is called non-homogeneous.
If no constant term exists, it is called homogeneous.

Methods of Solving Recurrence Relations

Method 1: Iteration Method

Meaning: Keep replacing previous terms until a pattern appears.

Example:

$$a_n=a_{n-1}+3$$$$=a_{n-2}+6$$$$=a_{n-3}+9$$

Finally:

$$a_n=a_1+3(n-1)$$

When to use:

• Simple recurrences
• First-order relations

Method 2: Characteristic Equation Method

Used for:

• Linear recurrence relations
• Constant coefficients
• Homogeneous equations

Steps:

1. Assume solution $a_n = r^n$

2. Substitute into recurrence

3. Get characteristic equation

4. Solve for $r$

5. Write general solution

Example:

$$a_n=5a_{n-1}-6a_{n-\mathrm{2}}$$

Characteristic equation:

$$r^2 - 5r + 6 = 0$$
$$(r-2)(r-3)=0$$

Roots:

$$r=2,3$$

General solution:

$$a_n=A(2^n)+B(3^n)$$

Method 3: Generating Function Method

Used when:

• Recurrence is complex
• Sequence pattern is difficult to see

This method converts sequences into power series.

Generating Functions 

A generating function is a power series where coefficients represent sequence terms.

Definition:

If a sequence is:

$$a_0,a_1,a_2,a_3,\dots$$

Then its generating function is:

$$G(x)=a_0+a_{1}x+a_2{x}^2+a_3{x}^3+\dots$$

Simple Example:

Sequence: 1, 1, 1, 1, …

$$G(x)=1+x+x^2+x^3+\dots$$$$G(x)=\frac{1}{1-\mathrm{x}}$$

Why Generating Functions are Useful:

• Solve recurrence relations
• Find closed-form formulas
• Used in counting problems
• Helpful in computer science and algorithms

Properties of Generating Functions

Property	Explanation
Linearity	Sum of sequences → sum of generating functions
Shifting	Multiplying by x shifts the sequence
Differentiation	Helps generate new sequences
Multiplication	Used for convolution of sequences

Example of Shifting:

If:

$$G(x)=a_0+a_{1}x+a_2{x}^2+\dots$$

Then:

$$xG(x)=a_{0}x+a_1{x}^2+a_2{x}^3+\dots$$

Example of Linearity:

$$G_1(x)+G_2(x)=\text{Generating function of }(a_n+b_n)$$

Solving Recurrence Using Generating Functions (Basic Idea)

Steps:

1. Write generating function $G(x)$

2. Multiply recurrence by $x^n$

3. Sum for all n

4. Simplify equation

5. Find closed-form $G(x)$

6. Expand to get $a_n$

Example:

$$a_n=a_{n-\mathrm{1}}$$

Generating function:

$$G(x)=\frac{a_0}{1-\mathrm{x<span\; class="vlist"><span\; class="mord"><span\; class="mord"><span\; class="msupsub"><span\; class="vlist-t\; vlist-t2"><span\; class="vlist-r"><span\; class="vlist-s"></span></span><span\; class="vlist-r"><span\; class="vlist"></span></span></span></span></span></span></span><span\; class="vlist-s"></span>}}$$

Summary Table (Quick Revision)

Topic	Key Point
Recurrence Relation	Defines sequence using previous terms
Constant Coefficients	Coefficients are fixed
Linear Recurrence	Terms appear linearly
Homogeneous	No constant term
Iteration Method	Step-by-step substitution
Characteristic Equation	Assume $r^n$
Generating Function	Power series representation

Combinatorics 

Combinatorics is the branch of mathematics that deals with counting, arranging, and selecting objects systematically.

In simple words:

“Combinatorics helps us count possibilities without missing or repeating anything.”

Daily Life Examples:

• Number of possible passwords
• Arranging students in a classroom
• Selecting team members
• Counting possible outcomes in games or exams

Why Combinatorics is Important?

• Used in computer science (algorithms, data structures)
• Used in probability
• Used in cryptography
• Used in decision-making problems

Counting Techniques

Counting techniques are rules that help count large numbers of possibilities easily.

Addition Principle (Sum Rule)

If:

• One task can be done in m ways
• Another task can be done in n ways
• And both tasks cannot be done together

Then:

$$\text{Total ways}=m+n$$

Example:

• Choose tea (2 types) or coffee (3 types)
• Total choices = 2 + 3 = 5

Multiplication Principle (Product Rule)

If:

• One task can be done in m ways
• Another task can be done in n ways

Then:

$$\text{Total ways}=m\times n$$

Example:

• 3 shirts and 4 trousers
• Total outfits = 3 × 4 = 12

(C) Permutations (Arrangement)

Permutations deal with arrangement, where order matters.

Formula:

$${}^n{P}_r=\frac{n!}{(n-r)!}$$

Example:

Number of ways to arrange 3 students from 5:

$${}^5{P}_3=5\times 4\times 3=60$$

(D) Combinations (Selection)

Combinations deal with selection, where order does not matter.

Formula:

$${}^n{C}_r=\frac{n!}{r!(n-r)!}$$

Example:

Choose 3 students from 5:

$${}^5{C}_3=10$$

(E) Factorial Notation

$$n! = n \times (n - 1) \times \dots \times 1$$Example:$$5!=120$$

Pigeonhole Principle

If more objects are placed into fewer boxes, then at least one box will contain more than one object.

Simple Statement:

“If n + 1 objects are put into n boxes, at least one box has two or more objects.”

Daily Life Example:

• 13 students and 12 months → at least two students have birthdays in the same month

Mathematical Example:

If 10 socks are placed into 9 drawers, one drawer will contain at least 2 socks.

General Form:

If N objects are distributed among k boxes, then at least one box contains:

$$\lceil \frac{N}{k}\rceil \text{ objects}$$

Applications:

• Computer science (hashing)
• Data storage
• Networking
• Proofs and logic problems

Polya’s Counting Theorem

Sometimes objects look different, but due to symmetry, many arrangements are actually the same.

Polya’s theorem helps count distinct arrangements when:

• Rotations or reflections are allowed

Example Situation:

• Coloring vertices of a square
• Coloring faces of a cube
• Designing patterns

Basic Idea (Layman View):

“Polya’s theorem avoids counting repeated designs that look the same after rotation or reflection.”

Key Concepts Used:

1. Group of symmetries
2. Permutations
3. Cycles
4. Colorings

Very Simple Example:

Coloring the four sides of a square using two colors.

• Without considering rotation → many cases
• With rotation → fewer unique designs

Polya’s theorem gives the exact number of unique colorings.

Polya’s Counting Formula (No Memorization Required)

$$\text{Number of distinct colorings}=\frac{1}{\mathrm{\mid }G\mathrm{\mid }}\sum \text{Number of colorings fixed by each symmetry}$$

Where:

• $G$ = group of symmetries

• $|G|$= number of symmetry operations

Applications:

• Chemistry (molecular structures)
• Computer graphics
• Pattern design
• Network labeling problems

Comparison Table (Quick Revision)

Topic	Key Idea
Combinatorics	Systematic counting
Permutation	Arrangement (order matters)
Combination	Selection (order doesn’t matter)
Pigeonhole Principle	More objects than boxes
Polya’s Theorem	Counting unique patterns