# Discrete Math

$$\overline{\bar{A}} = A$$ $$\overline{A ∪ B} = \bar{A} ∩ \bar{B}$$ $$\overline{A ∩ B} = \bar{A} ∪ \bar{B}$$ Let $f(x) = a_nx^n + a_{(n-1)}x^{(n-1)} + ... + a_1x + a_0.$ Then $f(x) = O(x^n).$ $${n \choose r}$$ $$\lceil N/k \rceil$$ $$P(n,r) = \frac{n!}{(n - r)!}$$ $$C(n,r) = \frac{n!}{r!(n - r)!}$$ $$(x + y)^n = \sum_{k=0}^{n} C(n,k)x^{n-k}y^k$$ $$n^r$$ $$\sum_{k=0}^{n} C(n,k) = 2^n$$ $$C(m + n,r) = \sum_{k=0}^{n} C(m,r - k)C(n,k)$$ $$\sum_{k=0}^{n} (-1)^k C(n,k) = 0$$ $$a_n = c_1a_{n-1} + c_2a_{n-2} + \cdots + c_k a_{n-k}$$ $$a_n = r^n$$ $$a_n = c_1r^{n-1} + c_2r^{n-2} + \cdots + c_k r^{n-k}$$ $$r^k - c_1r^{k-1} - c_2r^{k-2} - \cdots - c_{k-1}r - c_k = 0$$ $$a_n = a_{n-1} + a_{n-2}^2 \textrm{ is not an LHRR because}$$ $$H_n = 2H_{n-1} + 1 \textrm{ is not an LHRR because}$$ $$B_n = nB_{n-1} \textrm{ is not an LHRR because}$$ $$\{a_n\} \textrm{ is a solution to an LHRR of degree } 2$$ $$a_n = c_1 a_{n-1} + c_2 a_{n-2}$$ $$r^2 - c_1r - c_2 = 0$$ $$a_n = \alpha_1 r_1^n + \alpha_2 r_2^2$$ $$r^2 - c_1r - c_2 = 0$$ $$a_n = \alpha_1 r_0^n + \alpha_2 nr_0^2$$ $$\{a_n\} \textrm{ is a solution to an LHRR of degree } k$$ $$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$$ $$r^k - c_1r^{k-1} - \cdots - c_k = 0$$ $$a_n = \alpha_1 r_1^n + \alpha_2 r_2^2 + \cdots + \alpha_k r_k^n$$ $$n^m - C(n,1)(n - 1)^m + C(n,2)(n - 2)^m - \cdots + (-1)^{n-1}C(n,n - 1)^m$$ $$D_n = n!\left[1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n\frac{1}{n!}\right]$$