# Types of Proof
1. **Axiomatic Proof:** using agreed-upon rules of inference to establish truth in a formal system.
2. **Proof by Cases:** brute force method
3. **Proof by Contradiction:** starting by assuming the proposition is *False* and would subsequently lead to contradictions of what previously assumed *True*
4. **Contrapositive:** if *p* then *q* $\rightarrow$ if -*q* then -*p*.
5. **Induction:**
- Weak Induction: just need to find first P(1) base case.
- Strong Induction: need to find $n \leq k$ previous terms.
7. **Pigeonhole Principle:** if all pigeon must belong to a hole, and there are $n-1$ holes and $n$ pigeons there will be two pigeons in the same hole (figure out what is the pigeon and what is the hole).

## Logical Operators

# Summation / Product Notations
### Summation Rule Basic Properties

#### Summation Multiplication Rule
$$\sum_{i=0}^{n} 5i = 5\sum_{i=0}^{n} i = (5 \times 1) + (5 \times 2) + (5 \times 3) ... + (5 \times n)$$

#### Summation Addition Rule

\begin{align*}
\sum_{i=0}^{n} (i^2 + i) &= 1^2 + 1 + 2^2 + 2 + \ldots + n^2 + 1 \\
&= (1^2 + 2^2 + \ldots + n^2) + (1 + 1 + \ldots + 1) \\
&= \sum_{i=0}^{n} i^2 + \sum_{i=0}^{n} i
\end{align*}

This is also written as:
\begin{equation*}
\sum_{i=0}^{n} \left[ f(i) + g(i) \right] = \sum_{i=0}^{n} f(i) + \sum_{i=0}^{n} g(i)
\end{equation*}

### Product Rule Properties

This is used when there's a series of multiplications.
\begin{align*}
\prod_{i=1}^{n} i &= 1 \times 2 \times \ldots \times n = n!
\end{align*}
However, this may be inefficient thus we apply $\log(n)$
\begin{align*}
\ln \left( \prod_{i=1}^{n} i \right) &= \ln(1 \times 2 \times \ldots \times n) \\
&= \ln(1) + \ln(2) + \ldots + \ln(n)
\end{align*}
Thus, it could be summarized as:
\begin{align*}
\sum_{i=1}^{n} \ln i
\end{align*}

#### Additional Product Properties (APP)

\begin{align*}
n \ln n - n + 1 &\leq \ln n! \leq n \ln n - n + 1 + \ln n \\
\end{align*}

This implies that:
1. $\ln n! = n \ln n - n$
2. $n! = n^{n}e^{-n}$

#### Double Sum
\begin{align*}
\sum_{i=1}^{4} \sum_{j=1}^{3} ij &= \sum_{i=1}^{4}(i + 2i + 3i) \\
&= (1 \times 1 + 2 \times 1 + 3 \times 1) + \\
&\phantom{=}\; (1 \times 2 + 2 \times 2 + 3 \times 2) + \\
&\phantom{=}\; (1 \times 3 + 2 \times 3 + 3 \times 3) + \\
&\phantom{=}\; (1 \times 4 + 2 \times 4 + 3 \times 4) \\
&= (1 \times 3 + 2 \times 3 + 3 \times 3) + \\
&\phantom{=}\; (1 \times 4 + 2 \times 4 + 3 \times 4)
\end{align*}

This is also written as:
\begin{align*}
\sum_{i=1}^{4} \sum_{j=1}^{3} ij &= \left(\sum_{i=1}^{4} i\right) \times \left(\sum_{j=1}^{3} j\right)
\end{align*}

#### Double Product
\begin{align*}
\prod_{i=0}^{n-1} \prod_{j=0}^{p} i^jx^{j^p} &= \prod_{i=0}^{p} (jp)^y \times \prod_{i=0}^{p} (jp)^x \\
\prod_{i=1}^{n} \left(\prod_{j=1}^{i^3} (ij2j)\right) &= \left(\prod_{i=1}^{n^2} i\right) \times \left(\prod_{j=1}^{i^3} j^2\right)
\end{align*}

-----
## Finding Lower/Upper Bounds of Summation

### Question 1:

$$S=\sum_{i=1}^{n} f(i) = \sum_{i=1}^{n} \sqrt {\pi}$$
**Visualization**
- **Step 1:** Defining Theorem:
- $\mathcal{F}: \mathbb{R}^+ \rightarrow \mathbb{R}^+$ is a *non-decreasing continuous function*
- **Step 2:** Define Integral
- **Upper Bound:** $I + f(x)$
$$I + f(x) = \int_{x=1}^{x=n} \frac{1}{\sqrt{x}} \, dx + 1 \times \frac{1}{\sqrt{n}}$$
- **Lower Bound:** $I + g(x)$
$$I + g(x) = \int_{x=1}^{x=n} \frac{1}{\sqrt{x} + 1} \, dx + 1 \times \frac{1}{\sqrt{n} - 1}$$
- **Step 3:** Refer Back to Visuals
- $f(1)\ \text{or} \ f(x) \rightarrow$ **Leftmost** Rectangle
- $f(n)\ \text{or} \ f(x+1) \rightarrow$ **Rightmost** Rectangle

We thus get the range between **upper $ lower** bound. This shows that both $S \leq I + f(1) \quad \text{and} \quad S \geq 1 + f(n)$ is such that we get:

$$1 + f(n) \leq S \leq I + f(1).$$
-------
### Question 2:
$$S = \sum_{i=1}^{n} f(i) = \sum_{i=1}^{n} \frac{1}{\sqrt{i}}$$
- **Step 1:** Defining Theorem:
- $\mathcal{F}: \mathbb{R}^+ \rightarrow \mathbb{R}^+$ is a *non-decreasing continuous function*
- **Step 2:** Define Integral
- Upper Bound: $I + f(x)$
$$I + f(x) = \int_{x=1}^{x=n} \frac{1}{\sqrt{x}} \, dx + 1 \times \frac{1}{\sqrt{n}}$$

- Lower Bound: $I + g(x)$
$$I + g(x) = \int_{x=1}^{x=n} \frac{1}{\sqrt{x} + 1} \, dx + 1 \times \frac{1}{\sqrt{n} + 1}$$

- **Step 3:** Refer Back to Visuals

- $f(1)\ \text{or} \ f(x) \rightarrow$ **Leftmost** Rectangle
- $f(n)\ \text{or} \ f(x+1) \rightarrow$ **Rightmost** Rectangle

We thus get the range between **upper $ lower** bound. This shows that:
$$
I = \int_{1}^{n} f(x) \, dx = \frac{2}{3} (n^2 - 1)
$$
Therefore, we come to the conclusion that.
$$
\frac{2}{3} (n^2) + \frac{1}{3} \leq S \leq \frac{2}{3} (n^2) + \sqrt{n} - \frac{2}{3}
$$
Or we can just put it as:
$$
2(\sqrt{n} - 1) + 1 \geq \sum_{x=1}^{n} \frac{1}{\sqrt{x}} \geq 2(\sqrt{n} - 1) + \frac{1}{\sqrt{n}}
$$

### Question 3:
$$S = \sum_{i=1}^{n} f(i) = \sum_{i=1}^{n} \frac{1}{i^2}$$

### Question 4:
$$S = \sum_{i=1}^{n} f(i) = \sum_{i=1}^{n} \frac{1}{x^{\frac{3}{2}}}$$

-----
# Logarithm Properties
- $e^{\ln x} = x \quad \text{if } x \in \mathbb{R}^+$
- $\ln e^x = x \quad \text{if } x \in \mathbb{R}$
- $\ln(x \cdot y) = \ln x + \ln y$
- $\ln\left(\frac{x}{y}\right) = \ln x - \ln y$
- $\ln e = 1$

- **Integral**
$\ln a = \int_{1}^{a} \frac{1}{x} \, dx$
-------

# Recurrence Relations
1. $T(n) = T(n-1) + n, \quad T(1) = 1$
\begin{align*}
T(n) &= T(n-1) + n \\
&= T(n-2) + (n-1) + n \\
& \; \vdots \\
&= 1 + 2 + \ldots + (n-1) + n \\
&= \frac{n(n+1)}{2}.
\end{align*}

2. $T(n) = T(n - 1) + n^3, \quad T(1) = 1$
\begin{align*}
T(n) &= T(n - 1) + n^3 \\
&= T(n - 2) + (n - 1)^3 + n^3 \\
& \; \vdots \\
&= 1^3 + 2^3 + \ldots + (n - 1)^3 + n^3 \\
&= \left(\frac{n(n + 1)}{2}\right)^2.
\end{align*}

3. $T(n) = T\left(\frac{n}{2}\right) + 1, \quad T(1) = 1$

\begin{align*}
T(n) &= T\left(\frac{n}{2}\right) + 1 \\
&= T\left(\frac{n}{4}\right) + 1 + 1 \\
& \; \vdots \\
&= 1 + 1 + \ldots + 1 \quad (\text{lg } n \text{ times}) \\
&= \text{lg } n + 1.
\end{align*}

4. $T(n) = T\left(\frac{n}{2}\right) + n, \quad T(1) = 1$
\begin{align*}
T(n) &= T\left(\frac{n}{2}\right) + n \\
&= T\left(\frac{n}{4}\right) + \frac{n}{2} + n \\
& \; \vdots \\
&= 1 + 2 + \ldots + \frac{n}{2} + n \\
&= 2n - 1.
\end{align*}

5. T$(n) = 2 \cdot T\left(\frac{n}{2}\right) + n, \quad T(1) = 1$
\begin{align*}
T(n) &= 2 \cdot T\left(\frac{n}{2}\right) + n \\
&= 2 \cdot \left(2 \cdot T\left(\frac{n}{4}\right) + \frac{n}{2}\right) + n \\
& \; \vdots \\
&= n + n + \ldots + n = n(\lg n + 1) \quad (\text{lg } n+1 \text{ times})
\end{align*}

6. $T(n) = 2 \cdot T\left(\frac{n}{2}\right) + 1, \quad T(1) = 1$

\begin{align*}
T(n) &= 2 \cdot T\left(\frac{n}{2}\right) + 1 \\
&= 2 \cdot \left(2 \cdot T\left(\frac{n}{4}\right) + 1\right) + 1 \\
&= 4 \cdot T\left(\frac{n}{8}\right) + 4 \cdot 1 + 2 \cdot 1 + 1 \\
& \; \vdots \\
&= n + \frac{n}{2} + \ldots + 2 + 1 = 2n - 1.
\end{align*}

7. $T(n) = 2 \cdot T\left(\frac{n}{2}\right) + \lg n, \quad T(1) = 1$

\begin{align*}
T(n) &= 2 \cdot T\left(\frac{n}{2}\right) + \lg n \\
&= 2 \cdot \left(2 \cdot T\left(\frac{n}{4}\right) + \frac{\lg n}{2}\right) + \lg n \\
&= 4 \cdot T\left(\frac{n}{8}\right) + 4 \cdot \frac{\lg n}{4} + 2 \cdot \frac{\lg n}{2} + \lg n \\
& \; \vdots \\
&= n + \frac{n}{2} \lg 2 + \ldots + 4 \cdot \frac{\lg n}{4} + 2 \cdot \frac{\lg n}{2} + \lg n
\end{align*}

## Homogeneous Recurrence Relations
- A homogeneous recurrence relation is one where every term is equal to zero when the sequence is equal to zero.

### Question 1:
- $T_i = 5T_{i-1} - 6T_{i-2}; \quad T_0 = 8, \quad T_1 = 17$
- Assume that $T$ is in the form of $x^i$ where $x$ is some integer:

\begin{align*}
x^i &= 5x^{i-1} - 6x^{i-2}, \\
x^2 &= 5x - 6, \\
x^2 - 5x + 6 &= 0
\end{align*}

- Apply **Characteristic Equation**: $ax^2+bx+c=0$
$$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$
- Base on the root ($r=2$), and ($r=3$) we can express the general solution to recurrence relations as:

\begin{align*}
T_i = A \cdot 2^i + B \cdot 3^i
\end{align*}

- $A$ and $B$ are constants determined by the initial conditions. Given that $\quad T_0 = 8, \quad T_1 = 17$

\begin{align*}
\text{For } i = 0: & \quad 8 = A \cdot 2^0 + B \cdot 3^0 \\
\text{For } i = 1: & \quad 17 = A \cdot 2^1 + B \cdot 3^1
\end{align*}

- This gives us:
\begin{align*}
8 &= A + B \\
17 &= 2A + 3B
\end{align*}

- Therefore $A=7, B=1$ and the solution is $T_i = 7 \cdot 2^i + 1 \cdot 3^i$.

### Question 2:
- $T_i = T_{i-1} + 12T_{i-2}; \quad T_0 = 0, \quad T_1 = -7$
- Assume that $T$ is in the form of $x^i$ where $x$ is some integer:

\begin{align*}
x^i &= -x^{i-1} + 12x^{i-2}, \\
x^2 &= -x + 12 \\
x^2 + x - 12 &= 0
\end{align*}

- Apply **Characteristic Equation:** $ax^2+bx+c=0$
$$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$

- Base on the root ($r=-4$), and ($r=3$) we can express the general solution to recurrence relations as:

\begin{align*}
Ti = A · (−4)^i + B · 3^i
\end{align*}

- $A$ and $B$ are constants determined by the initial conditions. Given that $\quad T_0 = 0, \quad T_1 = -7$

\begin{align*}
\text{For } i = 0: & \quad 0 = A \cdot (-3)^0 + B \cdot 4^0 \\
\text{For } i = 1: & \quad -7 = A \cdot (-3)^1 + B \cdot 4^1
\end{align*}

- This gives us:
\begin{align*}
0 &= A + B \\
-7 &= 2A + 3B
\end{align*}

- Therefore $A=1, B=-1$ and the solution is $T_i = 1 \cdot (-3)^i - 1 \cdot 4^i$.

#### More Proofs