Unit 1: Logic and Proofs
Argument used to show a statement is true or false.
1.1 Proposition and Propositional Logic
Proposition भनेको यस्तो वाक्य हो जुन कि त 'सत्य' (True) हुन्छ वा 'असत्य' (False), तर दुवै हुन सक्दैन।
उदाहरण: "काठमाडौँ नेपालको राजधानी हो।" (यो एउटा Proposition हो किनकि यो True छ)।
Non-proposition: "अहिले कति बज्यो?" (यो प्रश्न हो, त्यसैले यो Proposition होइन)।
Propositional Logic: यसमा सरल वाक्यहरू हुन्छन्। जस्तै: P: "आज पानी पर्छ", Q: "म छाता ओढ्छु"।
1.2 Logical Connectives
दुई वा दुईभन्दा बढी Propositions लाई जोड्न प्रयोग गरिने शब्दहरूलाई Connectives भनिन्छ।
Logical Connectives: यी वाक्यहरूलाई जोड्ने तरिकाहरू:
Conjunction (AND): दुबै कुरा सही हुनुपर्छ। (P ^ Q)
Disjunction (OR): कुनै एउटा सही भए पुग्छ। (P v Q)
Negation (NOT): भएको कुरालाई उल्टो बनाउने। (~P / ¬P/ Ā)
Implication (→/⇒): "यदि तिमीले मेहेनत गर्यौ भने तिमी सफल हुनेछौ।" (P→Q) If..then
Biconditional (↔/⇔): "तिमीले अनुमति पाउँछौ यदि र केवल यदि तिमीले फर्म भर्छौ।" P↔Q दुवै कुरा सही वा गलत भएमा If and only if
1.3 Tautology, Contradiction, and Contingency
Tautology: सधैँ True हुने Proposition आज पानि पर्छ वा पर्दैन । (Pv~P)
Contradiction: सधैँ False हुने Proposition आज पानि पर्छ र पर्दैन ।(P ^~ P)
Contingency: Both True वा False परिस्थिति अनुसार हुन सक्छ। (P→Q/ P^Q)
1.4 Representing English Sentences into Propositional Logic
अङ्ग्रेजी वाक्यलाई गणितीय चिन्हमा बदल्ने प्रक्रिया।
वाक्य: "यदि बाहिर घाम लागेको छ भने म घुम्न जान्छु।"
Logic: मानाौँ P: "बाहिर घाम लागेको छ", Q: "म घुम्न जान्छु"। यसलाई P→Q लेखिन्छ।
1.5 Propositional Equivalences
यदि दुईवटा Logical expressions को Truth Table को नतिजा समान छ भने तिनीहरू Equivalent हुन्छन्।
उदाहरण (De Morgan's Law): ~(P^Q)⇒~Pv~Q
1.6 Rules of Inferences (वैध तर्कका नियमहरू)
तर्क गर्दा निष्कर्ष निकाल्न प्रयोग गरिने नियमहरू।
Modus Ponens: यदि P→Q सत्य छ र P पनि सत्य छ भने, Q अनिवार्य रूपमा सत्य हुन्छ।
उदाहरण: "यदि पानी पर्यो भने बाटो भिज्छ।" पानी पर्यो। निष्कर्ष: बाटो भिज्यो।
1.7 Valid Argument (वैध तर्क)
एउटा Argument भनेको केही आधारभूत भनाइहरू (Premises) र एउटा अन्तिम निष्कर्ष (Conclusion) को समूह हो।
Validity: यदि सबै Premises 'True' हुँदा निष्कर्ष (Conclusion) पनि अनिवार्य रूपमा 'True' हुन्छ भने, त्यसलाई Valid Argument भनिन्छ।
यदि Premises 'True' भएर पनि Conclusion 'False' हुन सक्छ भने, त्यो Invalid (Fallacy) हुन्छ।
1.8 Rules of Inferences (अनुमानका नियमहरू) Formal Proof
लामो Truth Table नबनाई तर्कको वैधता जाँच्न केही स्थापित नियमहरू प्रयोग गरिन्छ:
नियमको नाम: तार्किक रूप (Rule) उदाहरण
Modus Ponens: P →Q, P ∴Q यदि घाम लाग्यो भने गर्मी हुन्छ। घाम लाग्यो। त्यसैले, गर्मी भयो ।
Modus Tollens: P→ Q, ~Q ∴~P यदि सफ्टवेयर राम्रो छ भने चल्छ। सफ्टवेयर चलेन। त्यसैले, सफ्टवेयर राम्रो छैन।
Hypothetical Syllogism: P→Q, Q→R ∴P→R यदि पढ्यौ भने पास हुन्छौ। पास भयौ भने जागिर पाउँछौ। त्यसैले, पढ्यौ भने जागिर पाउँछौ।
Disjunctive Syllogism: PvQ, ~P ∴ Q म चिया खान्छु वा कफी। मैले चिया खाइन। त्यसैले, मैले कफी खाए।
Addition: P ∴ PvQ राम चलाख छ। त्यसैले, राम चलाख छ वा अल्छी छ।
1.9 Testing Validity of Argument (तर्कको वैधता जाँच्ने विधि)
कुनै तर्क Valid छ कि छैन भनेर जाँच्न मुख्य दुई तरिकाहरू छन्:
क) Truth Table विधि:
सबै भनाइहरूको एउटै Truth Table बनाउने। जुन-जुन लहर (Row) मा सबै Premises True छन्, ती लहरमा Conclusion पनि True हुनुपर्छ। यदि एउटा मात्र यस्तो Row भेटियो जहाँ Premises 'T' छन् तर Conclusion 'F' छ भने, त्यो तर्क Invalid हुन्छ।
ख) Formal Proof (Rules of Inference प्रयोग गरेर):
दिइएका Premises बाट सुरु गरेर माथिका नियमहरू लगाउँदै Conclusion सम्म पुग्ने।
उदाहरण:
१. P→Q (Premise)
२. Q→R (Premise)
३. P (Premise)
निष्कर्ष R निकाल्नु पर्नेछ:
४. P→R (१ र २ मा Hypothetical Syllogism लगाएर)
५. R (३ र ४ मा Modus Ponens लगाएर) — Valid!
1.10 Predicate Logic and Quantifiers
जब वाक्यमा 'variable' (जस्तै x) प्रयोग हुन्छ, त्यसलाई Predicate भनिन्छ।
Universal Quantifier (∀ for all): "सबैका लागि" (सबै मानिस मरणशील छन्)।
Existential Quantifier (∃ There exists): "कोही एकका लागि" (कोही विद्यार्थी चलाख छन्)।
1.11 Rules of Inference for Quantified Statements
जब वाक्यमा "सबै" (All) वा "कोही" (Some) जस्ता शब्द आउँछन् (for all, there exists), तब निम्न ४ नियमहरू प्रयोग हुन्छन्:
Universal Instantiation (UI): यदि कुनै कुरा सबैका लागि सत्य छ (∀x P(x)) भने, त्यो कुनै एउटा खास व्यक्ति (c) को लागि पनि सत्य हुन्छ।
उदाहरण: सबै मानिस मरणशील छन्। त्यसैले, राम मरणशील छ।
Universal Generalization (UG): यदि कुनै कुरा एउटा 'Arbitrary' (जुनसुकै हुन सक्ने) व्यक्तिको लागि सत्य छ भने, त्यो सबैका लागि सत्य हुन्छ (∀x P(x))।
Existential Instantiation (EI): यदि कोही एकको लागि कुरा सत्य छ (∃x P(x)) भने, हामी मान्न सक्छौँ कि त्यो कोही खास व्यक्ति 'c' हो।
Existential Generalization (EG): यदि कुनै खास व्यक्ति 'c' को लागि कुरा सत्य छ भने, हामी भन्न सक्छौँ कि "कोही त छ" (∃x P(x)) जसको लागि यो सत्य छ।
एउटा व्यवहारिक उदाहरण (Testing Validity):
तर्क: "सबै विद्यार्थीहरू मेहनती छन्। हरि एउटा विद्यार्थी हो। त्यसैले, हरि मेहनती छ।"
मानाौँ S(x): x विद्यार्थी हो, H(x): x मेहनती छ।
Premises: ∀x (S(x)→H(x)) र S(h)
Conclusion: H(h)
प्रमाण (Proof):
१. ∀x (S(x)→H(x)) (Premise)
२. S(h)→H(h) (Universal Instantiation बाट)
३. S(h) (Premise)
४. H(h) (२ र ३ मा Modus Ponens लगाएर)
निष्कर्ष: यो तर्क Valid छ ।
1.12 Proof Techniques (प्रमाणित गर्ने विधिहरू)
कुनै पनि गणितीय भनाइलाई प्रमाणित गर्न निम्न विधिहरू प्रयोग गरिन्छ:
Direct Method: सिधै तर्क प्रयोग गरेर प्रमाणित गर्ने।
उदाहरण: यदि n एउटा जोर (even) संख्या हो भने n^2 पनि जोर हुन्छ भनी देखाउनु।
Question: Using the Direct Method of proof, show that for any integer n, if n is an even integer, then n^2 is also an even integer.
Solution:
1. Logical Framework:
In a Direct Method of proof, we assume the hypothesis P is true and use mathematical rules, axioms, and previously proven theorems to directly conclude that Q is true (P \rightarrow Q).
Here:
P: n is an even integer.
Q: n^2 is an even integer.
2. Proof:
Let us assume that n is an even integer.
By the formal definition of even integers, any even number n can be expressed as:
n = 2k
(where k is some integer, k \in \mathbb{Z})
To find the nature of n^2, we square the expression for n:
n^2 = (2k)^2
n^2 = 4k^2
We can rewrite the right side of the equation to check for the definition of an even number (multiples of 2):
n^2 = 2(2k^2)
Let m = 2k^2. Since k is an integer, 2k^2 (which is m) must also be an integer. Thus:
n^2 = 2m
Since n^2 is expressed in the form 2m (a multiple of 2), by definition, n^2 is an even integer.
3. Conclusion:
Starting with the assumption that n is even, we have directly derived that n^2 is even. This confirms the validity of the statement.
Proved.
Indirect Method (Contrapositive): P→Q प्रमाणित गर्न ~Q→~P प्रमाणित गर्ने।
Question: Prove that for any integer n, if n^2 is odd, then n is odd, using the Method of Contraposition.
Solution:
1. Logical Framework:
Let the given statement be P \rightarrow Q, where:
P: n^2 is an odd integer.
Q: n is an odd integer.
To prove this using the Method of Contraposition, we must prove that \neg Q \rightarrow \neg P is true. That is: "If n is an even integer, then n^2 is an even integer."
2. Proof:
Assume that the negation of the conclusion is true. Let n be an even integer.
By the definition of even numbers, any even integer n can be expressed as:
n = 2k
(where k is some integer, k \in \mathbb{Z})
Now, to determine the parity of n^2, we square both sides:
n^2 = (2k)^2
n^2 = 4k^2
This expression can be rewritten as:
n^2 = 2(2k^2)
Let m = 2k^2. Since k is an integer, m is also an integer. Therefore:
n^2 = 2m
By definition, any integer in the form 2m is an even integer. Thus, we have shown that if n is even, then n^2 must also be even (\neg Q \rightarrow \neg P).
3. Conclusion:
Since the contrapositive \neg Q \rightarrow \neg P is logically equivalent to the original conditional statement P \rightarrow Q, we conclude that:
"If n^2 is odd, then n is odd."
Proved.
Proof by Contradiction: पहिले भनाइ गलत छ भनेर मान्ने र अन्त्यमा आफैँलाई गलत साबित गर्ने।
Question: Prove that sqrt{2} is an irrational number using the Method of Contradiction.
Solution:
1. Initial Assumption:
In a Proof by Contradiction, we start by assuming that the given statement is false.
Assume, to the contrary, that \sqrt{2} is a rational number.
By the definition of rational numbers, \sqrt{2} can be written in the form:
\sqrt{2} = \frac{p}{q} (यस्तोलाई गणितिय चिन्ह द्वारा लेखने)
Where:
p and q are integers.
q \neq 0.
p and q are in their simplest form (they are co-prime, meaning they have no common factors other than 1).
2. Mathematical Derivation:
Squaring both sides of the equation:
2 = \frac{p^2}{q^2}
Multiplying both sides by q^2:
p^2 = 2q^2 --- (Equation 1)
This implies that p^2 is an even number (since it is a multiple of 2).
According to the theorem (which we proved earlier), if p^2 is even, then p must also be even.
Since p is even, we can write:
p = 2k (for some integer k)
Now, substitute p = 2k into Equation 1:
(2k)^2 = 2q^2
4k^2 = 2q^2
q^2 = 2k^2
This implies that q^2 is an even number. Following the same logic, q must also be even.
3. Finding the Contradiction:
We have found that both p and q are even numbers. This means they both have 2 as a common factor.
However, this contradicts our initial assumption that p and q are co-prime (have no common factors other than 1).
4. Conclusion:
Since our assumption led to a contradiction, the assumption must be false. Therefore, \sqrt{2} cannot be rational.
Thus, \sqrt{2} is an irrational number.
Proved.
Trivial and Vacuous Proof: यदि परिणाम सधैँ True छ भने त्यो Trivial हुन्छ। यदि सर्त नै False छ भने त्यो Vacuous हुन्छ।
1. Trivial Proof
The conclusion (q) is always true, regardless of the premise.
Example: "If n is an integer, then 5 = 5."
(The result is a self-evident fact.)
2. Vacuous Proof
The condition (p) is always false, making the entire statement "true" by default.
Example: "If a square has three sides, then I am the King of England."
(Since the starting condition is impossible, the claim cannot be proven false.)
Proof by Counter Examples: कुनै भनाइ गलत छ भनेर देखाउन एउटा मात्र गलत उदाहरण दिनु।
उदाहरण: "सबै Prime संख्याहरू बिजोर हुन्छन्।" (Counter example: 2 एउटा जोर Prime संख्या हो, त्यसैले भनाइ गलत भयो)।
Proof by Counterexample
In formal logic, a statement of the form \forall x, P(x) (For all x, P(x) is true) is proven false by identifying a single element in the domain for which the predicate is false. This single instance is called a counterexample.
Statement: "For every n \in \mathbb{Z}^{+}, if n is prime, then n is odd."
Counterexample: Let n = 2.
2 is a positive integer.
2 is a prime number.
However, 2 is even, not odd.
Conclusion: Since a counterexample (n=2) exists, the universal generalization is disproved.
Proof by Cases: सबै सम्भावित परिस्थिति (Cases) हरूलाई छुट्टाछुट्टै प्रमाणित गर्ने।
Proof by Cases (Exhaustive Proof)
Definition: A method of proof where the statement is divided into several exhaustive cases, and each case is proven separately to show that the statement holds for all possible scenarios.
Question: Prove that for every integer n, n^2 + n is always an even number.
Solution:
We will use Proof by Cases by considering two scenarios for the integer n: either n is even or n is odd. These two cases cover all possible integers.
Case 1: n is an even integer
If n is even, then n = 2k for some integer k.
Substituting this into the expression:
n^2 + n = (2k)^2 + (2k)
= 4k^2 + 2k
= 2(2k^2 + k)
Since 2(2k^2 + k) is a multiple of 2, the result is even.
Case 2: n is an odd integer
If n is odd, then n = 2k + 1 for some integer k.
Substituting this into the expression:
n^2 + n = (2k + 1)^2 + (2k + 1)
= (4k^2 + 4k + 1) + (2k + 1)
= 4k^2 + 6k + 2
= 2(2k^2 + 3k + 1)
Since 2(2k^2 + 3k + 1) is a multiple of 2, the result is even.
Conclusion:
Since n^2 + n is even in both cases, it is proven that n^2 + n is even for every integer n.
Unit 2: Induction and Recursion
2.1 Mathematical Induction and its Principal
Mathematical induction is one of the techniques which can be used to prove variety of mathematical statements which are formulated in terms of n, where n is a positive integer.
The Principle of Mathematical Induction is used to prove that a statement, P(n), is true for every natural number n.
To complete a proof by induction, must satisfy two specific conditions:
1. The Base Case
To prove that the statement holds true for the first natural number in the set (usually n = 1). This confirms the "first domino" is ready to fall.
P(1) is true.
2. The Inductive Step
This is the "if-then" part. To assume that the statement is true for some arbitrary integer k. This assumption is called the Inductive Hypothesis. You then use this assumption to prove that the statement must also be true for the next integer, k + 1.
If P(k) is true, then P(k+1) is true.
2.2 Strong Induction
The Principle of Strong Induction
कुनै पनि Statement P(n) लाई सबै n∈N को लागि प्रमाणित गर्न:
1. Base Case: P(1) (वा सुरुवाती केही मानहरू) सत्य छ भनी देखाउने।
2. Inductive Hypothesis: मानौँ कि P(1), P(2), ..., P(k) सम्मका सबै मानहरू सत्य छन्।
3. Inductive Step: यो अनुमानको आधारमा P(k+1) सत्य छ भनी प्रमाणित गर्ने।
2.3 Recursive Definition
कुनै पनि Recursive definition मा दुईवटा मुख्य भागहरू हुन्छन्:
Base Case (Basis Step): यसले सुरुवाती मान वा सबैभन्दा सरल अवस्था तोक्छ। यस बिना प्रोग्राम वा परिभाषा अनन्त (infinite loop) सम्म जान सक्छ।
Recursive Step (Inductive Step): यसले नयाँ मानहरू कसरी अघिल्लो मानहरूबाट निकाल्ने भन्ने नियम बताउँछ।
2.4 Structural Induction
Structural induction proves a property for a whole system by showing it holds for the basic pieces and remains true as they are composed into larger structures.
Base: True for the simplest part.
Step: If true for the components, it’s true for the composite object.
2.5 Recursive Algorithms and its Correctness
To prove a recursive algorithm is correct, you use structural induction to show it handles its simplest inputs and correctly combines the results of its sub-tasks.
How to Prove Correctness
Termination: Prove the algorithm always reaches a base case (no infinite loops).
Base Case: Show the algorithm returns the correct result for the simplest possible input.
Inductive Step: Assume the algorithm works for smaller components. Prove that when these results are composed, the final output is correct.
Unit 3: Number Theory
Number theory is the study of properties of integers.
3.1 Divisibility and Modular Arithmetic
Divisibility
It is the study of whether one number can be divided by another without leaving a remainder.
Definition: a is divisible by b if a÷b results in a whole number.
Example: 15 is divisible by 3 (15 = 3×5), but 15 is not divisible by 4.
Modular Arithmetic
It is a system of arithmetic for integers where numbers "wrap around" after reaching a certain value (the modulus). It focuses only on the remainder.
Notation: a (mod n) = r
The Clock Analogy: Think of a 12-hour clock. If it is 10:00 and you add 5 hours, it is 3:00 i.e. (15 (mod 12) = 3).
3.2 Primes
Prime Number is a whole number greater than 1 that cannot be formed by multiplying two smaller whole numbers.
Definition: A number that has exactly two factors: 1 and itself.
Examples: 2, 3, 5, 7, 11, 13, 17, 19...
Note: 2 is the only even prime number.
3.3 Greatest Common Divisor (GCD)
Greatest Common Divisor (GCD)—also known as the Highest Common Factor (HCF)—is the largest positive integer that divides two or more integers without leaving a remainder.
Definition: The biggest "shared" factor between numbers.
Example: For 12 and 18:
Factors of 12: 1, 2, 3, 4, 6, 12
Factors of 18: 1, 2, 3, 6, 9, 18
GCD(12, 18) = 6
3.4 Least Common Multiples (LCM)
Least Common Multiple (LCM) is the smallest positive integer that is perfectly divisible by two or more numbers.
While the GCD looks for the biggest common factor, the LCM looks for the smallest common multiple.
Definition: The first number where the "timetables" of two different numbers meet.
Example: For 4 and 6:
Multiples of 4: 4, 8, 12, 16, 20, 24...
Multiples of 6: 6, 12, 18, 24, 30...
LCM(4, 6) = 12
3.5 Euclidean and Extended Euclidean Algorithm
Euclidean Algorithm
Based on the principle that gcd(a, b) = gcd(b, a(mod b)).
Example: gcd(101, 13)
101 = 7(13) + 10
13 = 1(10) + 3
10 = 3(3) + 1
3 = 3(1) + 0
Result: GCD is 1.
Extended Euclidean Algorithm
The algorithm finds integers x and y such that:
ax + by = gcd(a, b)
These integers (x, y) are useful for finding modular inverses. If gcd(a, n) = 1, then ax + ny = 1, which implies ax☰1 (mod n). In this case, x is the modular inverse of a modulo n.
Example Walkthrough: 101x + 13y = 1
Using the steps from the Euclidean algorithm above, we work backward:
1 = 10 - 3(3)
Substitute 3 from step 2 above: 1 = 10 - 3(13 - 1(10))
Simplify: 1 = 4(10) - 3(13)
Substitute 10 from step 1 above: 1 = 4(101 - 7(13)) - 3(13)
Simplify: 1 = 4(101) - 28(13) - 3(13)
Final Equation: 1 = 4(101) + (-31)(13)
Result: x = 4, y = -31
3.6 Linear Congruence and solving Linear Congruence
linear congruence is an equation of the form
ax ≡ b (mod n),
where a, b, n are integers and x is the unknown.
CONDITION FOR SOLUTION
The congruence ax ≡ b (mod n) has a solution if and only if
gcd(a, n) divides b.
If gcd(a, n) does not divide b, then there is no solution.
STEPS TO SOLVE LINEAR CONGRUENCE
Find d = gcd(a, n).
If d does not divide b → no solution.
If d divides b, divide a, b, n by d:
a' = a/d, b' = b/d, n' = n/d.
Find the modular inverse of a' modulo n' using Extended Euclidean Algorithm.
Compute x ≡ (a'^(-1) × b') (mod n').
NUMBER OF SOLUTIONS
If d = gcd(a, n), then there are d solutions:
x = x0 + k(n/d), where k = 0, 1, 2, ..., d−1.
EXAMPLE
Solve: 6x ≡ 8 (mod 14)
gcd(6, 14) = 2, and 2 divides 8, so solution exists.
Divide by 2: 3x ≡ 4 (mod 7).
Inverse of 3 mod 7 is 5.
x ≡ 5 × 4 ≡ 20 ≡ 6 (mod 7).
Final solutions: x = 6, 13 (mod 14).
Chinese Remainder Theorem states that a system of simultaneous congruences has a unique solution modulo the product of the moduli, provided the moduli are pairwise coprime.
STATEMENT OF CRT
If
x ≡ a1 (mod n1)
x ≡ a2 (mod n2)
...
x ≡ ak (mod nk)
and n1, n2, ..., nk are pairwise coprime, then there exists a unique solution modulo N, where
N = n1 × n2 × ... × nk.
STEPS TO SOLVE USING CRT
Compute N = n1 × n2 × ... × nk.
For each i, compute Ni = N / ni.
Find Mi such that
Ni × Mi ≡ 1 (mod ni)
(Mi is the modular inverse of Ni modulo ni).
Compute
x = (a1·N1·M1 + a2·N2·M2 + ... + ak·Nk·Mk) mod N.
EXAMPLE
Solve:
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
Step 1:
N = 3 × 5 × 7 = 105
Step 2:
N1 = 105/3 = 35
N2 = 105/5 = 21
N3 = 105/7 = 15
Step 3:
35M1 ≡ 1 (mod 3) → M1 = 2
21M2 ≡ 1 (mod 5) → M2 = 1
15M3 ≡ 1 (mod 7) → M3 = 1
Step 4:
x = (2×35×2 + 3×21×1 + 2×15×1) mod 105
x = (140 + 63 + 30) mod 105
x = 233 mod 105 = 23
Final Answer: x ≡ 23 (mod 105)
3.8 Computer Arithmetic with Large Integers
Computer arithmetic with large integers deals with performing arithmetic operations (addition, subtraction, multiplication, division, and modular operations) on integers that are too large to be stored in standard computer word sizes.
WHY LARGE INTEGERS ARE NEEDED
Normal computers store integers in fixed sizes (32-bit or 64-bit).
In cryptography and number theory, numbers can have hundreds or thousands of digits, so special algorithms and representations are required.
REPRESENTATION OF LARGE INTEGERS
Large integers are stored as:
Arrays or lists of digits or bits
Base 2, base 10, or base 2^k representation
Multiple machine words instead of a single word
BASIC OPERATIONS ON LARGE INTEGERS
Large Integer Addition
Add digit by digit with carry (like manual addition).
Large Integer Subtraction
Subtract digit by digit with borrow.
Large Integer Multiplication
School method (O(n^2))
Fast methods: Karatsuba, FFT-based multiplication
Large Integer Division
Long division method for big numbers.
MODULAR ARITHMETIC WITH LARGE INTEGERS
Operations are done modulo n:
(a + b) mod n
(a − b) mod n
(a × b) mod n
Unit 4: Recurrence Relations
4.1 Recursive Definitions of Sequences
Recursive definition means defining a sequence using previous terms.
Form:
Base case (starting value)
Recursive rule (formula using previous terms)
Example:
Fibonacci sequence
F₀ = 0, F₁ = 1
Fₙ = Fₙ₋₁ + Fₙ₋₂
Arithmetic sequence
a₁ = 2
aₙ = aₙ₋₁ + 3
Meaning: Each term depends on earlier terms.
4.2 Applications of Recurrence Relations
Recurrence relations are used to:
Algorithm analysis
Time complexity of divide-and-conquer algorithms
Example: T(n) = 2T(n/2) + n (Merge Sort)
Computer science problems
Fibonacci numbers
Tower of Hanoi
Binary search
Dynamic programming
Mathematics
Population growth
Compound interest
Counting problems
4.3 Solving Linear Recurrence Relations
A linear recurrence relation is:
aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + f(n)
(a) Homogeneous Recurrence Relations
Definition: No extra function term (f(n) = 0)
General Form:
aₙ = c₁aₙ₋₁ + c₂aₙ₋₂
Example:
aₙ = 3aₙ₋₁ − 2aₙ₋₂
Steps to Solve:
Write characteristic equation
r² − 3r + 2 = 0
Solve for r
r = 1, 2
General solution
aₙ = A(1)ⁿ + B(2)ⁿ
(b) Non-Homogeneous Recurrence Relations
Definition: Has extra function term f(n) ≠ 0
General Form:
aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + f(n)
Example:
aₙ = aₙ₋₁ + 3ⁿ
Solution Steps:
Solve homogeneous part
Find particular solution for f(n)
Add both solutions
Final solution:
aₙ = (homogeneous solution) + (particular solution)
Unit 5: Relation and Graph Theory
Unit 6: Finite Automata
6.1 Deterministic Finite Automata (DFA)
Definition: DFA is a 5-tuple (Q, Σ, δ, q₀, F)
Q = finite set of states
Σ = finite input alphabet
δ = transition function (Q × Σ → Q)
q₀ = initial state
F = set of final/accepting states
Properties:
For each state and input symbol, δ gives exactly one next state
Accepts strings ending in a final state
Example: DFA accepting all strings ending with ‘01’
6.2 Non-Deterministic Finite Automata (NFA)
Definition: NFA is a 5-tuple (Q, Σ, δ, q₀, F)
δ = transition function (Q × Σ → 2^Q)
Can have multiple or zero next states for a given input
Can include ε-transitions (move without input)
Properties:
NFA and DFA recognize the same class of languages (regular languages)
Conversion: NFA → DFA using subset construction
6.3 Regular Expressions
Definition: Algebraic way to represent regular languages
Operators:
Concatenation: AB = strings formed by a string from A followed by B
Union: A + B = strings from A or B
Kleene star: A* = zero or more repetitions of strings from A
Examples:
(a+b)* = all strings of a’s and b’s
ab* = strings starting with a followed by zero or more b’s
6.4 Kleene's Theorem
Statement: A language is regular iff it can be accepted by a finite automaton (DFA/NFA)
Implication:
Every language recognized by a DFA/NFA can be represented by a regular expression
Every language described by a regular expression can be recognized by a DFA/NFA