Sem IV Mathematics Summary

Cheatsheet Content

### Number Systems #### Definitions - **Number System:** A mathematical notation for representing numbers using digits or symbols, defining the base (radix) of counting. - **Decimal (Base 10):** Digits 0–9 - **Binary (Base 2):** Digits 0 and 1 (Fundamental language of computers, 1 bit, 8 bits = 1 byte) - **Octal (Base 8):** Digits 0–7 (Common in Unix file permissions, 1 octal digit = 3 binary bits) - **Hexadecimal (Base 16):** Digits 0–9 and A–F (A=10, B=11, C=12, D=13, E=14, F=15). Used in memory addressing, color codes. 1 hex digit = 4 binary bits (nibble). #### Conversion: Binary to Decimal - Multiply each binary digit by $2$ raised to its positional power (starting from $0$ at the rightmost bit) and sum all results. - **Example:** $(1011)_2 = 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 8 + 0 + 2 + 1 = (11)_{10}$ #### Conversion: Decimal to Octal - Repeatedly divide the decimal number by $8$ and record the remainders. Read remainders from bottom to top. - **Example:** $(324)_{10}$ - $324 \div 8 = 40$ R $4$ - $40 \div 8 = 5$ R $0$ - $5 \div 8 = 0$ R $5$ - Answer: $(504)_8$ #### Conversion: Binary to Hexadecimal - Group binary digits into sets of $4$ from the right. Convert each group to its hexadecimal equivalent. - **Example:** $(101000)_2$ - Group: $0010 | 1000$ - $0010_2 = 2_{16}$ - $1000_2 = 8_{16}$ - Answer: $(28)_{16}$ #### Conversion: Binary to Octal - Group binary digits into sets of $3$ from the right. Convert each group to its octal equivalent. - **Example:** $(10011001)_2$ - Group: $010 | 011 | 001$ (padded with leading zero) - $010_2 = 2_8$ - $011_2 = 3_8$ - $001_2 = 1_8$ - Answer: $(231)_8$ - For fractional parts, group from left to right after the decimal point, padding with trailing zeros. - **Example:** $(10.11001101)_2 \approx (2.632)_8$ #### Conversion: Hexadecimal to Binary - Convert each hexadecimal digit to its $4$-bit binary equivalent. - **Example:** $(2.6)_{16}$ - $2_{16} = 0010_2$ - $6_{16} = 0110_2$ - Answer: $(0010.0110)_2$ #### Conversion: Hexadecimal to Decimal - Multiply each hexadecimal digit by $16$ raised to its positional power and sum the results. - **Example:** $(13A2)_{16} = 1 \times 16^3 + 3 \times 16^2 + 10 \times 16^1 + 2 \times 16^0 = 4096 + 768 + 160 + 2 = (5026)_{10}$ - For fractional parts: - **Example:** $(BD17.93)_{16} = 11 \times 16^3 + 13 \times 16^2 + 1 \times 16^1 + 7 \times 16^0 + 9 \times 16^{-1} + 3 \times 16^{-2} \approx (48407.574)_{10}$ ### Set Theory & Relations #### Set Definitions - **Set:** A well-defined collection of distinct objects (elements). - **Notation:** $A = \{1, 2, 3, 4\}$ or $B = \{x \mid x \text{ is a positive integer } #### Inclusion-Exclusion Principle - **For two sets A and B:** $|A \cup B| = |A| + |B| - |A \cap B|$ - **For three sets A, B, and C:** $|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |B \cap C| + |A \cap C|) + |A \cap B \cap C|$ - **Example:** Given $|A|=6, |B|=8, |C|=6, |A \cup B \cup C|=11, |A \cap B|=3, |A \cap C|=2, |B \cap C|=5$. Find $|A \cap B \cap C|$. - $11 = 6 + 8 + 6 - (3 + 5 + 2) + |A \cap B \cap C|$ - $11 = 20 - 10 + |A \cap B \cap C|$ - $11 = 10 + |A \cap B \cap C| \implies |A \cap B \cap C| = 1$ #### Relations - **Relation R:** A subset of the Cartesian product $A \times B$. It associates elements of $A$ with elements of $B$. - **Example:** $A=\{1,2\}, B=\{a,b\} \implies R = \{(1,a),(2,b)\}$ is a relation from $A$ to $B$. - **"If and only if" (iff) Statement:** A relation $R$ on set $A$ is defined using 'iff': $aRb \iff (a,b) \in R$. - **Example:** $R = \{(a,b) \mid a \text{ divides } b\}$ means $aRb$ iff $a$ divides $b$. - **Digraph (Directed Graph):** A graphical representation of a relation. Elements are vertices, ordered pairs are directed arrows (edges). A loop at vertex $a$ if $(a,a) \in R$. - **Example:** For $A=\{1,2,3,4,6,9\}$, $aRb \iff a$ is a multiple of $b$. - $R = \{(1,1),(2,1),(2,2),(3,1),(3,3),(4,1),(4,2),(4,4),(6,1),(6,2),(6,3),(6,6),(9,1),(9,3),(9,9)\}$ - **Matrix Relation:** A boolean ($0/1$) matrix $M$ where $M_{ij} = 1$ if $(a_i, b_j) \in R$, and $M_{ij} = 0$ if $(a_i, b_j) \notin R$. ### Logical Operations #### Statements - **Statement (or Proposition):** A declarative sentence that is either TRUE (T) or FALSE (F), but not both. - **Examples:** 'The sun rises in the east' (True), '2 + 2 = 5' (False). - **Non-examples:** Questions ('Are you there?'), commands. #### Mathematical Induction Principle (PMI) - To prove $P(n)$ is true for all $n \ge 1$: 1. **Base Case:** Show $P(1)$ is true. 2. **Inductive Step:** Assume $P(k)$ is true for some $k \ge 1$ (Inductive Hypothesis). Then show $P(k+1)$ is also true. - **Conclusion:** $P(n)$ is true for all $n \ge 1$. - **Examples:** - **$1^2 + 3^2 + 5^2 + \dots + (2n-1)^2 = \frac{n(2n+1)(2n-1)}{3}$** - Base Case (n=1): LHS = $1^2 = 1$. RHS = $\frac{1(3)(1)}{3} = 1$. (True) - Inductive Hypothesis: Assume true for $n=k$. - Inductive Step: Prove for $n=k+1$. - **$1+2+3+\dots+n = \frac{n(n+1)}{2}$** - **$2+4+6+\dots+2n = n(n+1)$** #### Logical Operations & Definitions - **Negation ($\neg p$ or $\sim p$):** 'NOT p'. Reverses the truth value of p. | p | $\neg p$ | |---|--------| | T | F | | F | T | - **Conjunction ($p \land q$):** 'p AND q'. TRUE only when BOTH p and q are TRUE. | p | q | $p \land q$ | |---|---|-----------| | T | T | T | | T | F | F | | F | T | F | | F | F | F | - **Disjunction ($p \lor q$):** 'p OR q'. TRUE when at least one of p or q is TRUE, FALSE only when both are FALSE. | p | q | $p \lor q$ | |---|---|-----------| | T | T | T | | T | F | T | | F | T | T | | F | F | F | - **Conditional ($p \to q$):** 'If p then q'. FALSE only when p is TRUE and q is FALSE. | p | q | $p \to q$ | |---|---|-----------| | T | T | T | | T | F | F | | F | T | T | | F | F | T | - **Biconditional ($p \leftrightarrow q$):** 'p if and only if q'. TRUE when p and q have the same truth value. This is equivalent to $(p \to q) \land (q \to p)$. | p | q | $p \leftrightarrow q$ | |---|---|-------------------| | T | T | T | | T | F | F | | F | T | F | | F | F | T | #### Tautology, Contradiction, Contingency - **Tautology:** A compound statement that is always TRUE, regardless of the truth values of its component statements. - **Example:** $p \lor \neg p$ (Law of Excluded Middle) - **Contradiction:** A compound statement that is always FALSE, regardless of truth values. - **Example:** $p \land \neg p$ - **Contingency:** A compound statement that is neither a tautology nor a contradiction (TRUE for some assignments, FALSE for others). - **Example:** $p \leftrightarrow q$ ### Recurrence Relations & Numerical Methods #### Recurrence Relations (RR) - **Definition:** An equation that defines a sequence where each term is a function of its preceding terms. - **Example:** $a_n = a_{n-1} + a_{n-2}$ (Fibonacci Sequence). - The **order** of an RR is determined by how many previous terms are used. - **Types of RR:** 1. **Linear RR:** Each term is a linear combination of previous terms. (e.g., $a_n = 2a_{n-1} + 3$) 2. **Non-linear RR:** Terms involve powers or products. (e.g., $a_n = a_{n-1}^2$) 3. **Homogeneous RR:** $f(n) = 0$ (no separate function of $n$). (e.g., $a_n = a_{n-1} + a_{n-2}$) 4. **Non-Homogeneous RR:** $f(n) \neq 0$. (e.g., $a_n = 2a_{n-1} + n$) - **Examples of RR (Order 1 and 2):** - Order 1: $a_n = 3a_{n-1}$; $a_n = 2a_{n-1} + 1$ - Order 2: $a_n = a_{n-1} + a_{n-2}$ (Fibonacci); $a_n = 2a_{n-1} - a_{n-2}$ - **General Solution for RR with distinct roots ($r_1, r_2$):** For a 2nd order linear homogeneous RR, $a_n = C_1 r_1^n + C_2 r_2^n$. - **General Solution for RR with repeated roots ($r$):** - For repeated root $r$: $a_n = (C_1 + C_2 n) r^n$. - For k-fold repeated root: $a_n = (C_1 + C_2 n + C_3 n^2 + \dots + C_k n^{k-1}) r^n$. - **Solving Non-Homogeneous RR:** - Find homogeneous solution $a_n^{(h)}$ and particular solution $a_n^{(p)}$. - Total solution $a_n = a_n^{(h)} + a_n^{(p)}$. - **Example:** $a_n = 2a_{n-1} + 1$ with $a_1 = 7$. - Homogeneous: $a_n^{(h)} = C \cdot 2^n$. - Particular: Assume $a_n^{(p)} = A$ (constant). $A = 2A + 1 \implies A = -1$. - General solution: $a_n = C \cdot 2^n - 1$. - Apply I.C. $a_1 = 7$: $7 = C \cdot 2^1 - 1 \implies 2C = 8 \implies C = 4$. - Answer: $a_n = 4 \cdot 2^n - 1 = 2^{n+2} - 1$. - **Telescoping Sums:** - **Example:** $a_n = a_{n-1} + n$, $a_1 = 4$. - $a_n = a_1 + \sum_{i=2}^n i = 4 + \frac{n(n+1)}{2} - 1 = 3 + \frac{n(n+1)}{2}$. #### Numerical Methods - **Difference Table:** An organized table of values of a function $f(x)$ and its forward differences ($\Delta f, \Delta^2 f$, etc.) used for interpolation. - **Finite Difference Table:** Records function values at equally spaced intervals and computes differences. Used for polynomial interpolation and numerical integration. - **Formula for Finite Difference ($ \Delta^n f_0 $):** - $\Delta^n f_0 = \sum_{r=0}^n (-1)^{n-r} C(n,r) f_r$ - Simplified: $f_n - C(n,1)f_{n-1} + C(n,2)f_{n-2} - \dots + (-1)^n f_0$ - **Formula for Divided Difference ($f[x_0, x_1, x_2, \dots]$):** - **First divided difference:** $f[x_0, x_1] = \frac{f(x_1)-f(x_0)}{x_1-x_0}$ - **Second divided difference:** $f[x_0, x_1, x_2] = \frac{f[x_1, x_2]-f[x_0, x_1]}{x_2-x_0}$ - **Nth divided difference:** $f[x_0, \dots, x_n] = \frac{f[x_1, \dots, x_n]-f[x_0, \dots, x_{n-1}]}{x_n-x_0}$ - **Example of Divided Difference Table:** | x | f(x) | 1st Div Diff | 2nd Div Diff | 3rd Div Diff | 4th Div Diff | |-----|------|--------------|--------------|--------------|--------------| | -2 | 33 | | | | | | | | 71 | | | | | -1 | 104 | | -61 | | | | | | -94 | | 83.67 | | | 0 | 10 | | 62 | | -14.33 | | | | 20 | | 14 | | | 1 | 30 | | -24 | | 7.33 | | | | 90 | | 14 | | | 2 | 120 | | -26 | | | | | | 11 | | | | | 3 | 131 | | | | | ### Groups and Semi-Groups #### Definitions - **Commutativity:** A binary operation $*$ on a set $G$ is commutative if for all $a, b \in G$, $a * b = b * a$. - **Example:** Addition: $a+b = b+a$ for all real numbers. - **Semi-Group:** An algebraic system $(G, *)$ satisfying: 1. **Closure:** For all $a, b \in G \implies a * b \in G$ 2. **Associativity:** $(a * b) * c = a * (b * c)$ for all $a, b, c \in G$ - **Example:** $(\mathbb{Z}, +)$ (integers under addition) - **Monoid:** A semi-group with an identity element. It is $(G, *)$ satisfying Closure, Associativity, and: 3. **Identity:** There exists an element $e \in G$ such that $a * e = e * a = a$ for all $a \in G$. - **Example:** $(\mathbb{Z}, +)$ with identity $0$; $(\mathbb{Z}, \times)$ with identity $1$. - **Identity Element ($e$):** An element $e$ in a set $G$ with operation $*$ is an identity if for all $a \in G$, $a * e = e * a = a$. - **Example:** $0$ is identity for addition ($a+0=a$); $1$ is identity for multiplication ($a \times 1 = a$). - **Group:** An algebraic structure $(G, *)$ satisfying: 1. **Closure:** For all $a, b \in G \implies a * b \in G$ 2. **Associativity:** $(a * b) * c = a * (b * c)$ for all $a, b, c \in G$ 3. **Identity:** There exists an element $e \in G$ such that $a * e = e * a = a$ for all $a \in G$. 4. **Inverse:** For each $a \in G$, there exists an element $a^{-1} \in G$ such that $a * a^{-1} = a^{-1} * a = e$. - **Example:** $(\mathbb{Z}, +)$ (integers under addition). - **Abelian Group:** A group $(G, *)$ is Abelian (or commutative) if in addition to the four group axioms, it satisfies **Commutativity**: $a * b = b * a$ for all $a, b \in G$. - **Example:** $(\mathbb{Z}, +)$ is an Abelian group. - **Cancellation Laws (in a group):** For all $a, b, c \in G$: - Left Cancellation: $a * b = a * c \implies b = c$ - Right Cancellation: $b * a = c * a \implies b = c$ - **Subgroup:** A non-empty subset $H$ of a group $(G, *)$ is a subgroup if $(H, *)$ is itself a group. - **Subgroup Test:** $H$ is a subgroup iff for all $a, b \in H \implies a * b^{-1} \in H$. #### Group Examples and Proofs - **Show $(G, *)$ is an Abelian Group where $G$ is the set of all non-zero real numbers and $a * b = ab/2$.** - **Closure:** $a,b \in G \implies ab/2 \in G$. (True, since $a,b \neq 0 \implies ab/2 \neq 0$) - **Associativity:** $(a * b) * c = (ab/2) * c = (ab/2)c/2 = abc/4$. $a * (b * c) = a * (bc/2) = a(bc/2)/2 = abc/4$. (True) - **Identity:** $a * e = a \implies ae/2 = a \implies e = 2$. (True) - **Inverse:** $a * a^{-1} = e \implies a a^{-1}/2 = 2 \implies a^{-1} = 4/a$. (True) - **Commutativity:** $a * b = ab/2 = ba/2 = b * a$. (True) - **Conclusion:** $(G, *)$ is an Abelian Group. - **Determine if $(\mathbb{R}, *)$ with $a * b = a+b+2$ is a group. If yes, check if Abelian.** - **Closure:** $a,b \in \mathbb{R} \implies a+b+2 \in \mathbb{R}$. (True) - **Associativity:** $(a * b) * c = (a+b+2) * c = (a+b+2)+c+2 = a+b+c+4$. $a * (b * c) = a * (b+c+2) = a+(b+c+2)+2 = a+b+c+4$. (True) - **Identity:** $a * e = a \implies a+e+2 = a \implies e = -2$. (True) - **Inverse:** $a * a^{-1} = e \implies a+a^{-1}+2 = -2 \implies a^{-1} = -a-4$. (True) - **Commutativity:** $a * b = a+b+2 = b+a+2 = b * a$. (True) - **Conclusion:** $(\mathbb{R}, *)$ is an Abelian Group with identity $-2$ and inverse $a^{-1} = -a-4$. - **Show that if $x^2 = x$ for some $x$ in a group $G$ with identity $e$, then $x = e$.** - Given $x * x = x$. - Multiply by $x^{-1}$ on the right: $(x * x) * x^{-1} = x * x^{-1}$ - By associativity: $x * (x * x^{-1}) = e$ - $x * e = e \implies x = e$. - **Show that group $G$ is Abelian $\iff (ab)^{-1} = a^{-1}b^{-1}$ for all $a,b \in G$.** - ($\Rightarrow$) Assume $G$ is Abelian. $(ab)^{-1} = b^{-1}a^{-1}$. Since $G$ is Abelian, $b^{-1}a^{-1} = a^{-1}b^{-1}$. Thus $(ab)^{-1} = a^{-1}b^{-1}$. - ($\Leftarrow$) Assume $(ab)^{-1} = a^{-1}b^{-1}$. Also, by standard group properties, $(ab)^{-1} = b^{-1}a^{-1}$. - So $a^{-1}b^{-1} = b^{-1}a^{-1}$. - Replace $a$ with $a^{-1}$ and $b$ with $b^{-1}$: $(a^{-1})^{-1}(b^{-1})^{-1} = (b^{-1})^{-1}(a^{-1})^{-1} \implies ab = ba$. - Thus $G$ is Abelian. - **If $a^2 = e$ for all $a \in G$ (every element is its own inverse), show $G$ is Abelian.** - Given $a * a = e$ for all $a \in G$. - Consider any $a,b \in G$. We want to show $ab = ba$. - We know $(ab)^2 = e \implies (ab)(ab) = e$. - Multiply by $a$ on the left: $a(ab)(ab) = ae \implies a(ab)(ab) = a$. - Since $a^2=e$, $a$ is its own inverse, so $a(ab)(ab) = a \implies e(b)(ab) = a \implies b(ab) = a$. - Multiply by $b$ on the right: $b(ab)b = ab$. - Since $b^2=e$, $b$ is its own inverse, so $b(ab)b = ab \implies b(a)e = ab \implies ba = ab$. - Thus $G$ is Abelian.