[toc]

# Proof
## 逆反命題
p -> q = ¬q -> ¬p
若 P，則Q = 若非 Q，則非P

ex.
proof that integer n, if **3n+2 is odd** `(p)` -> **n is odd** `(q)`

Assume that n is even (¬q)
3n+2 = 3(2k)+2 = 6k+2 = 2(3k+1), it is even (found ¬p)

## 反證
prove that p is ture
find an r such that ¬p -> (r^¬r) is true then p is true, (r ^ ¬r) always false

# Set

## Cardinality `|S|`

The number of distinct element of S.
`∣∅∣ = 0`

S is finite if its cardinality is finite; otherwise, S is infinite.
Z+, N, Z, Q, and R are infinite.

## Power Set P(S)
The set of all subset of S.
∅ and S itself are the member of P(S)
`P({a,b}) = {∅, {a}, {b}, {a, b}}`
`P(∅) = {∅}`
`P({∅}) = {∅, {∅}}`
if S has n elements, `|P(S)| = 2^n`

## Cartesian Products

AxB = {(a,b) | a∈A ∧ b∈B}

AxB != BxA unless A=∅ or B=∅ (so A=B=∅) or A=B.

# Binary Relation

A binary relation from A to B is a subset of AxB

A set of ordered pairs (a, b), where a∈A and b∈B

A relation on the set A is a relation from A to A.

## Properties of Relations

全部: n^2
主對角線數: n
左下半數: n(n-1)/2

### Reflexive:
連號都有
2 ^ (n ^ 2 − n)
2 ^ (非主對角線數)

### Irreflexive:
無連號
2 ^ (n ^ 2 − n)
2 ^ (非主對角線數)

### Symmetric:
如果AB在,BA要在
2 ^ (n(n + 1) / 2)
2 ^ (主對角線數 + 左下半數)

### AntiSymmetric:
2^n * 3^(n(n-1)/2)
如果A,B在且B,A在, 則A=B
2^(主對角線數) * (左下半邊數 * 3)

3指的是:(假設a != b) (a,b) , (b,a) , 無

### ASymmetric:
3^(n(n-1)/2)
AntiSymmetric但是沒有連號

## Set Operations
### Union A ∪ B
### Intersection A ⋂ B
### Difference A - B, A\B
# Function
### injective (one to one)
單映射
### surjective (on-to)
value都有被對映到
### bijective
injective and surjective

# 解遞迴關係式

## 齊次
ex.

an = 3(an-1) - 3(an-2) + (an-3), a0 = a1 = 2, a2 = 4

1. Let an = r^n, 解特徵方程
r^n = 3r^(n-1) - 3r^(n-2) + r^(n-3)
r^n - 3r^(n-1) + 3r^(n-2) - r^(n-3) = 0
r^3 - 3r^2 + 3r - 1 = 0
r = 1 (三重根)

2. r帶回去，寫出通解，重根的話要填n
an = α * 1^n + β * **n** * 1^n + γ * **n^2** * 1^n

:::info

三重根 r 通解 (α + β * **n** + γ * **n^2**) * r^n

二重根 r1, r1, r2 通解 (α + β * **n**) * r1^n + γ * r2^n

r1, r2, r3 通解 α * r1^n + β * r2^n + γ * r3^n
:::

3. 帶初始值, 解
a0 = 2 = α
a1 = 2 = α + β + γ
a2 = 4 = α + 2β + 4γ
求得α, β, γ
-> an = 2 - n + n^2

## 非齊次

(先解齊次解)

ex.
an = 5(an-1) - 6(an-2) + 2^n

1. Let an = r^n, 解特徵方程 (先解齊次解)
r^n = 5r^(n-1) - 6r^(n-2)
r^n - 5r^(n-1) + 6r^(n-2) = 0
r^2 - 5r + 6 = 0
r = 2 or 3

2. r 帶回去，寫出齊次解
an = α * 2^n + β * 3^n

3. 找特解 (重根的話要填n)
Let an = **n** * r2^n
nr2^n = 5(n-1)r2^(n-1) - 6(n-2)r2^(n-2) + 2^n
8r = 10r + 4
r = -2
an = -2n2^n

4. 合併
an = α * 2^n + β * 3^n - 2n2^n

3. 帶初始值, 解
求得α = -2, β = 3
-> an = -2 * 2^n + 3 * 3^n - 2n2^n ...