CoE KKU

$$ 𝑋^𝐴 * 𝑋^𝐵 = 𝑋^{(𝐴+𝐵)} $$ $$ 𝑋^𝐴/𝑋^𝐵 = 𝑋^{(𝐴−𝐵)} $$ $$ (𝑋^𝐴)^𝐵 = 𝑋^{𝐴𝐵} $$ $$ 𝑋^𝑁 + 𝑋^𝑁 = 2𝑋^𝑁 ≠ 𝑋^{2𝑁} $$ $$ 2^𝑁+2^𝑁 = 2^{(𝑁+1)} $$

ส่วนใหญ่ที่ใช้เป็น logarithms ฐาน 2

นิยาม: $𝑋^𝐴 = 𝐵$ 𝑖𝑓 𝑎𝑛𝑑 𝑜𝑛𝑙𝑦 𝑖𝑓 $𝑙𝑜𝑔_𝑥 𝐵 = 𝐴$ $$ log⁡(𝐴𝐵)=log⁡𝐴+log⁡𝐵 $$ $$ log⁡(𝐴/𝐵)=log⁡𝐴−log⁡𝐵 $$ $$ log⁡(𝐴^𝐵)=B log⁡𝐴 $$ $log⁡ 𝑋 < X$ for all $X > 0$

log 1 = 0, log 2 = 1, log 1,024 = 10, log 1,048,576 = 20

THEOREM

$$ log_𝐴⁡𝐵 = \frac{log_𝑐⁡𝐵}{log_𝑐⁡𝐴} ; A, B, C > 0, A≠1 $$

PROOF: ให้ $X = log_c B, Y = log_c A, และ Z = log_A B.$ ดังนั้น จากนิยามของ logarithms

จะได้ $C^X = B, C^Y = A, และ A^Z = B$ รวมทั้งสามสมการจะได้ $(C^Y)^Z = C^X = B$ ดังนั้น X = YZ, ซึ่งก็คือ Z = X/Y

$$ ∑_{i=0}^N 2^i = 2^0+2^1+2^2+2^3+⋯+2^{N-1}+2^N = 2^{(N+1)}-1 $$ และ $$ ∑_{i=0}^N A^i = \frac{(A^{N+1}-1)}{(A-1)} $$ ถ้า 0 < A < 1, จะได้ $$ ∑_{i=0}^N A^i ≤ \frac{1}{(1-A)} $$

ถ้า N เข้าหา $ \infty $, ผลบวกจะเข้าหา $ \frac{1}{(1-A)} $

โดยปกติแล้วเทคนิคในการหาผลลัพธ์ที่เป็นสูตรของผลบวกของอนุกรมสามารถทำได้ดังตัวอย่างเช่น ต้องการสูตรของ

$$ ∑_{i=0}^\infty A^i \ \ \ (0<A<1) $$

ให้ S เป็นผลบวกของอนุกรมข้างบน ดังนั้น

$$ S = 1 + A + A^2 + A^3 + A^4 + A^5 + .. (1) $$

และคูณทั้งสมการ (1) ด้วย A จะได้

$$ AS = A + A^2 + A^3 + A^4 + A^5 + . . (2)$$

(1) – (2) จะได้

$$S – AS = 1 \ \ \ ซึ่งก็คือ \ \ S=\frac{1}{(1-A)} $$

ดังนั้น

$$ ∑_{i=0}^\infty A^i = \frac{1}{(1-A)} \ \ \ (0<A<1) $$

ด้วยวิธีการที่คล้ายกันเราสามารถหาผลลัพธ์ของอนุกรม

$$ S=∑_{i=0}^\infty \frac{i}{2^i} $$

ให้ S เป็นผลบวกของอนุกรมข้างบน ดังนั้น \begin{align*} s & = 1/2+2/2^2 +3/2^3 +4/2^4 + ⋯ \\ 2s & =1+2/2+3/2^2 +4/2^3 +5/2^4 + ⋯ \\ 2s-s & =1+1/2+1/2^2 +1/2^3 +1/2^4 + ⋯ \\ s & =1+ 1/(1-1/2)=3 \\ \end{align*}

อนุกรมเลขคณิตสามารถหาได้ด้วยการใช้สูตรพื้นฐาน ดังนี้

$$ ∑_{i=1}^N i= \frac{(N(N+1))}{2} ≈ \frac{N^2}{2}$$

ตัวอย่าง $$1+2+3+…+100 = \frac{(100×(100+1))}{2}$$

ซึ่งสามารถนำมาประยุกต์ใช้ประโยชน์ในบางสถานการณ์ เช่น

ต้องการหาผลบวก $2 + 5 + 8 + ... + (3k - 1)$ เมื่อ k คือค่าเลขจำนวนเต็ม

ให้เขียนใหม่เป็น $3(1 + 2+ 3 +...+ k) - (1 + 1 + 1 +...+ 1)$, ซึ่งก็คือ $ \frac{(3k(k + 1))}{2}–k $

หรือทำได้อีกวิธีหนึ่ง กล่าวคือ ให้บวกเทอมแรกและเทอมสุดท้ายจะได้ 3k + 1, บวกเทอมที่สองและเทอมรองสุดท้ายจะได้ 3k + 1 และทำเช่นนี้ไปเรื่อย ๆ จะพบว่าจะมีคู่เทอมทั้งหมด $\frac{k}{2}$ ตัว, ดังนั้นผลบวกทั้งหมด คือ $\frac{k(3k + 1)}{2}$

อนุกรมอื่น ๆ ที่อาจพบได้

$$∑_{i=1}^N i^2 = \frac{N(N+1)(2N+1)}{6} ≈ \frac{N^3}{3}$$ $$∑_{i=1}^N i^k ≈ \frac{N^(k+1)}{|k+1|} \ \ k ≠ -1 $$

Harmonic Number และ harmonic sum:

$$H_n=∑_{i=1}^N \frac{1}{i} ≈ log_e⁡N $$

สำหรับอนุกรมโดยทั่วไปแล้วจะเป็นไปดังนี้:

$$∑_{i=1}^N f(n) = Nf(N) $$ $$∑_{i=n_0}^N f(i) = ∑_{i=1}^N f(i)- ∑_{i=1}^{n_0-1} f(i)$$

เรียก a ว่าเป็น congruent to b modulo n, ซึ่งเขียนเป็น $a \equiv b(mod\ n)$,

ถ้า n หาร a – b ลงตัว เศษที่ได้จากการนำ n ไปหาร a หรือหาร b มีค่าเท่ากัน ดังนั้น $81 \equiv 61 \equiv 1(mod\ 10) $

และถ้า $a \equiv b (mod\ n) $, จะได้ว่า $$a + c \equiv b + c (mod\ n) $$ และ $$ ad \equiv bd (mod\ n)$$

สำหรับจำนวนจริงใด ๆ x, กำหนดให้ จำนวนเต็ม ที่มากที่สุด ที่น้อยกว่าหรือเท่ากับ x คือ ⌊x⌋ (เรียก “the floor of x”) และ จำนวนเต็มที่น้อยที่สุด ที่มากกว่าหรือเท่ากับ x คือ ⌈x⌉ (เรียก “the ceiling of x”). สำหรับ x ทั้งหมด $$ x-1<⌊x⌋≤x≤⌈x⌉<x+1 $$ สำหรับจำนวนเต็ม n, $$⌊n/2⌋+⌈n/2⌉=n$$

ในการวิเคราะห์ ในเรื่อง โครงสร้างข้อมูล และ อัลกอริทึม ใช้การพิสูจน์ แบบ Proof by Contradiction, Proof by Counterexample และ Proof by Induction เป็นส่วนใหญ่ โดยมีหลักการ ดังนี้

Proof by Contradiction

เริ่มต้นทำด้วยการสมมติให้ทฤษฎีที่เราต้องการพิสูจน์นั้นว่าไม่จริง (คือ เป็น false) และจะทำการแสดงให้เห็นว่าข้อสมมติของเราไม่เป็นความจริง ดังนั้นคำกล่าวที่เราสมมติให้ทฤษฎีที่เราต้องการพิสูจน์นั้นว่าไม่จริงนั้นจึงไม่ถูกต้อง

• If P is the proposition to be proved:
  • 1. P is assumed to be false, that is ¬P is true.
  • 2. It is shown that ¬ P implies two mutually contradictory assertions, Q and ¬ Q.
  • 3. Since Q and ¬ Q cannot both be true, the assumption that P is false must be wrong, and P must be true.

ตัวอย่างที่นิยมยกมาแสดงกันบ่อย ๆ คือการพิสูจน์ว่าจำนวนของค่า prime number มีจำนวนเป็นอนันต์ (infinite) โดย Euclid (300BC)

ทฤษฎี: prime numbers มีจำนวนเป็นอนันต์
การพิสูจน์:

Proof by Counterexample

การพิสูจน์ โดยยกตัวอย่างแย้ง ไม่ใช่เทคนิคในการพิสูจน์ เป็นเพียงการแสดงให้เห็นว่า ประโยคที่กล่าว ไม่เป็นจริง โดยการยกตัวอย่าง ที่ค้าน ประโยคดังกล่าว

ตัวอย่างแย้ง ของประโยคที่ว่า “เลข prime ทุกตัวเป็นเลขคี่” คือ 2 เป็น เลข prime แต่ไม่เป็นเลขคี่

Proof by Mathematical Induction

เป็นการพิสูจน์ความถูกต้องของผลลัพธ์หรือสูตร (หรือคือ Proposition P) ซึ่งประกอบด้วย 3 ขั้นตอน คือ

Basic Step: ขั้นพิสูจน์กรณีฐาน (base case) เพื่อแสดงให้เห็นว่า Proposition P($n_0$) เป็นจริง

Inductive step: Proposition เป็นจริงสำหรับค่าเลขจำนวนเต็ม k ใด ๆ ที่ $k > n_0$ (inductive hypothesis) กล่าวคือ Proposition เป็นจริงทุกกรณีจนถึงค่า k คือ Proposition P(k) เป็นจริง

แสดงให้เห็นว่าทฤษฎีเป็นจริงกรณีค่าถัดไป กล่าวคือกรณีค่า k+1 คือพิสูจน์ว่า P(k+1) เป็นจริง

ตัวอย่าง 1 พิสูจน์ Fibonacci numbers, $F_0 = 1, F_1 = 1, F_2 = 2, F_3 = 3, F_4 = 5, . . . , F_i = F_{i-1} + F_{i-2} $ แล้ว ให้ $P(n): Fn < (\frac{5}{3})^n$, for $n>=1$ เป็นจริง (บางครั้งนิยามให้ $F_0 = 0$)

เริ่มด้วย basic step คือพิสูจน์ P(1) เป็นจริงกรณีนี้ $n_0 = 1$ ซึ่งเป็นกรณีที่ชัดเจนคือ $F_1 = 1 < \frac{5}{3}$ และ $F_2 = 2 < (\frac{5}{3})^2 = \frac{25}{9}$;

สมมติในทฤษฎีเป็นจริงสำหรับค่า i = 1, 2, . . . , k; (นี่คือ inductive hypothesis)

พิสูจน์กรณี k+1 คือ $F_{k+1} < (\frac{5}{3})^{k+1}$.

จาก $F_{k + 1} = F_k + F_{k-1}$

ใช้ inductive hypothesis กับด้านขวามือ จะได้

\begin{align*} F_{k+1} & < (\frac{5}{3})^k + (\frac{5}{3})^{k-1} \\ & < (\frac{3}{5})(\frac{5}{3})^{k+1} + (\frac{3}{5})^2(\frac{5}{3})^{k+1} \\ & < (\frac{3}{5})(\frac{5}{3})^{k+1} + (\frac{9}{25})(\frac{5}{3})^{k+1} \\ \end{align*} ซึ่งเขียนใหม่ได้ \begin{align*} F_{k+1} & < (\frac{3}{5} + \frac{9}{25})(\frac{5}{3})^k+1 \\ & < (\frac{24}{25})(\frac{5}{3})^k+1 \\ & < (\frac{5}{3})^k+1 \\ \end{align*}

ตัวอย่าง 2 พิสูจน์ว่าทุก ๆ ค่าเลขจำนวนเต็ม n ใด ๆ, $$ ∑_{i=1}^N i = \frac{(N(N+1))}{2} $$

ให้ $P(N): ∑_{i=1}^N i = \frac{(N(N+1))}{2} $

Basis step: แสดงให้เห็นว่า P(1) เป็นจริง (ในกรณีนี้ $n_0 = 1$) นั่นคือ

เมื่อ n = 1, $$RHS = 1(1+1)/2 = 1 = ∑_{i=1}^1 i = LHS $$ ดังนั้น P(1) เป็นจริง

Induction step: ให้ k เป็นเลขจำนวนเต็มใด ๆ เราต้องแสดงให้เห็นว่า P(k + 1) เป็นจริง: โดย สมมติให้ P(k) เป็นจริง นั่นคือ $$ ∑_{i=1}^k i = \frac{(k(k+1))}{2} $$ เป็นจริง ← inductive hypothesis

เพื่อที่จะพิสูจน์ว่า P(k + 1) เป็นจริง คือ $$∑_{i=1}^{k+1} i = \frac{((k+1)(k+2))}{2} $$

เราเริ่มด้วย LHS ของสมการข้างบนนี้ \begin{align*} ∑_{i=1}^{k+1} i & = ∑_{i=1}^k i + (k+1) \\ & = \frac{(k(k+1))}{2}+(k+1) \text{ by induction hypothesis }\\ & = \frac{(k(k+1)+2(k+1))}{2} = \frac{(k^2+3k+2)}{2} \\ & = \frac{((k+1)(k+2))}{2} \end{align*}

ดังนั้น ถ้า P(k) เป็นจริงนั่นคือ P(k+1) ย่อมเป็นจริงด้วย และ จึงแสดงให้เห็นว่า P(n) เป็นจริงสำหรับทุก ๆ ค่าของ n > 1 นั่นคือสูตรดังกล่าวจึงเป็นจริงสำหรับทุกค่า n ที่เป็นเลขจำนวนเต็มบวก

ตัวอย่าง 3 พิสูจน์ว่าทุก ๆ ค่าเลขจำนวนเต็ม N ใด ๆ, (THEOREM 1.3) $$ ∑_{i=1}^N i^2 = \frac{(N(N+1)(2N+1))}{6} \ \ \ ; N ≥ 1 $$

Basic step: เมื่อ N = 1,

$$∑_{i=1}^N i^2 = ∑_{i=1}^1 i^2 = 1 = \frac{(N(N+1)(2N+1))}{6} = \frac{(1(1+1)(2+1))}{6} $$

ดังนั้น P(1) เป็นจริง

Induction step: สมมติให้ P(k) เป็นจริง ที่ 1 < k < N นั่นคือ

$$∑_{i=1}^k i^2 =\frac{(k(k+1)(2k+1))}{6}$$

เพื่อที่จะพิสูจน์ว่า $P(k) \to P(k + 1) $ เป็นจริง คือ. $$∑_{i=1}^{k+1} i^2 = \frac{((k+1)((k+1)+1)(2(k+1)+1))}{6}= \frac{((k+1)(k+2)(2k+3))}{6}$$

เราเริ่มด้วย LHS ของสมการข้างบนนี้ \begin{align*} ∑_{i=1}^{k+1} i^2 & = ∑_{i=1}^k i^2 + (k+1)^2 \\ & = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 = (k+1)[\frac{k(2k+1)}{6}+(k+1)] \\ & = (k+1)[\frac{(2k^2+k)}{6} + \frac{(6k+6)}{6}] = (k+1)[\frac{(2k^2+7k+6)}{6}] \\ & = \frac{((k+1)(k+2)(2k+3))}{6} \\ \end{align*} ดังนั้น ถ้า P(k) เป็นจริงนั่นคือ P(k+1) ย่อมเป็นจริงด้วย

ตัวอย่าง 4 จงพิสูจน์ว่า $ 2n^3+3n^2+n $ หารด้วย 6 ลงตัวสำหรับทุกค่าเลขจำนวนเต็ม n > 1

ให้ $P(n):2n^3+3n^2+n$ หารด้วย 6 ลงตัว

Basic step: เมื่อ n = 1, $2n^3+3n^2+n=2(1)+3(1)+1 = 6 $ ซึ่งหารด้วย 6 ลงตัว ดังนั้น P(1) เป็นจริง

Induction step: ให้ P(k) เป็นจริง นั่นคือ $2k^3+3k^2+k$ หารด้วย 6 ลงตัวที่ค่าใด ๆ ของ k > 1

ซึ่งก็คือ $2k^3+3k^2+k = 6m$ สำหรับจำนวนเต็ม m และจะต้องแสดงให้เห็นว่า P(k+1) เป็นจริง

กล่าวคือ $2(k+1)^3+3(k+1)^2+(k+1)$ หารด้วย 6 ลงตัว โดยจะเห็นได้ว่า \begin{align*} 2(k+1)^3 + 3(k+1)^2 + (k+1) & = 2(k^3+3k^2+3k+1)+3(k^2+2k+1)+(k+1) \\ & = (2k^3+3k^2+k) + 6(k^2+2k+1) \\ & = 6m+6(k^2+2k+1) \ \ \ \text{by the induction hypothesis} \\ & = 6(m+k^2+2k+1) \ \ \ \text{ซึ่งหารด้วย 6 ลงตัว ดังนั้น P(k+1) เป็นจริง} \\ \end{align*}

ตัวอย่าง 5 Bernoulli's Inequality

ให้ x เป็นเลขจำนวนจริงใด ๆ ที่มีค่ามากกว่า -1 ให้พิสูจน์ว่า $(1+x)^n ≥ 1 + nx $ ที่ $n ≥ 0$

ให้ $P(n): (1+x)^n ≥ 1 + nx $ (Note: การทำ Induction ทำบนค่า discrete ของ n)

Basic step: แสดงให้เห็นว่า P(0) เป็นจริง ซึ่งคือ $$ (1+x)^0 = 1 $$ $$ ≥ 1 + 0x $$

ดังนั้น P(0) เป็นจริง (ในที่นี้ $n_0 = 0$)

Induction step: ให้ P(k) เป็นจริง นั่นคือ $(1+x)^k ≥ 1 + kx $ สำหรับค่าเลขจำนวนเต็ม k ใด ๆ ที่ k > 0

เราจะต้องแสดงให้เห็นว่า P(k+1) เป็นจริง กล่าวคือ $(1+x)^(k+1) ≥ 1 + (k+1)x$

จาก Inductive hypothesis เรามี $(1+x)^k ≥ 1 + kx$ ดังนั้น \begin{align*} (1+x)^{k+1} & = (1+x) (1+x)^k \\ & ≥ (1+x)(1+xk) \ \ \ \text{โดย Inductive hypothesis และเนื่องจาก 1+x > 0} \\ & = 1+(k+1)x+kx^2 \\ & ≥ 1+(k+1)x \ \ \ \text{เนื่องจาก }\ kx^2 ≥ 0\\ \end{align*} นั่นคือ P(k+1) เป็นจริง ดังนั้น $(1+x)^n ≥ 1 + nx $ ที่ n ≥ 0

ตัวอย่าง 6 A เป็น finite set ที่มีสมาชิกจำนวน n ตัวจะมีจำนวน subsets ได้ทั้งสิ้นจำนวน $2^n^ subsets.

Basic step: แสดงให้เห็นว่า P(0) เป็นจริง ซึ่งคือ เมื่อ n = 0, A = $\Phi $ ดังนั้น A จึงมีจำนวน subset คือ $1 = 2^0$ ดังนั้น P(0) เป็นจริง

Induction step: ให้ finite set ใด ๆ ที่มีจำนวนสมาชิก k ตัว จะมีจำนวน subset ได้ $2^k$ subsets เมื่อ k > 0 และกำหนดให้ A เป็น set ที่มีจำนวนสมาชิก k+1 ตัว ซึ่งเราต้องแสดงให้เห็นว่า A มีจำนวน sunsets ได้ทั้งสิ้น $2^{k+1}$ subsets.

สมมติให้ x $\in$ A และให้ B = A – {x} ดังนั้น เนื่องจาก |B| = k ทำให้มีจำนวน subset ได้ $2^k$ subsets (ด้วย inductive hypothesis) และแต่ละ subset ของ B ก็เป็น subset ของ A ด้วย ซึ่งถ้าเราเพิ่ม x ลงในแต่ละ subset ดังกล่าวนั้น ก็จะทำให้ได้ผลเป็น set ใหม่ที่มีสมาชิก x ด้วย เป็นจำนวน $2^k$ เซต และ เซตใหม่นี้ก็เป็น subset ของ A ด้วย ดังนั้นจำนวน subset ทั้งสิ้นของ A (ทั้งที่มี x และไม่มี x เป็นสมาชิก) จึงรวมกันเป็น $2^k + 2^k = 2^{k+1}$ subsets

Basic step และ Induction step ล้วนมีความสำคัญการใช้ PMI ดังจะเห็นได้จากตัวอย่างข้างล่างนี้

ตัวอย่าง 7 ให้ $g(n)$ เป็นจำนวนสูงสุดของพื้นที่ที่ไม่ซ้อนทับกันที่เกิดขึ้นภายในรูปวงกลมจากการลากเส้นเชื่อมระหว่างจุดจำนวน $n$ จุดบนวงกลม รูปที่ 1 ถึง 5 ข้างล่างแสดงกรณีที่ $n = 1, 2, 3, 4,$ และ $5$ และพื้นที่แสดงด้วยหมายเลข $1, 2, 3, …$ ตารางที่ 1 แสดงผลที่ได้

1	2	3	4	5	6

ตาราง 1

จากตารางดูเหมือนว่า $g(n) = 2^{n-1}$ นั่นคือ $g(1) = 2^0 = 1$ เป็นจริง (basic step) อย่างไรก็ตาม นี่ไม่ได้ประกันว่า $g(n) = 2^{n-1}$ สำหรับทุกค่าของ n > 1 จะเห็นว่าถ้าสูตรดังกล่าวนี้เป็นจริงเราจะได้ว่า $g(6) = 2^5 = 32$ เป็นจำนวนพื้นที่ที่ไม่ซ้อนทับกันที่เกิดจากจุด 6 จุด แต่ความจริงมีพื้นที่เกิดขึ้นเพียง 31 เท่านั้น ดังรูปที่ 6 Dividing a circle into areas

ดังนั้นเราจึงกล่าวได้ว่า เพียงแต่ basic step เป็นจริงบวกกับรูปแบบที่ปรากฏนั้นไม่สามารถประกันได้ว่า $P(n)$ จะเป็นจริงสำหรับทุกค่าของ $n$

ตัวอย่างต่อไปนี้แสดงให้เห็นว่าความถูกต้องของ induction step เป็นสิ่งจำเป็น แต่ไม่ได้หมายความว่ามันจะเป็นการเพียงพอที่จะประกันว่า $P(n)$ เป็นจริงเป็นจริงได้สำหรับทุก ๆ ค่าเลขจำนวนเต็มใน universe of discourse นั้น ๆ

ตัวอย่าง 8 พิจารณาสูตร $P(n): 1 + 3 + 5 + … + (2n – 1)= n^2 + 1$

สมมติ P(k) เป็นจริง: $$∑_{i=1}^k (2i-1) = k^2+1 $$ ดังนั้น \begin{align*} ∑_{i=1}^{k+1} (2i-1) & = ∑_{i=1}^k (2i-1) + (2k+1) \\ & = (k^2+1)+(2k+1) \\ & = (k+1)^2+1 \\ \end{align*} ดังนั้น ถ้า $P(k)$ เป็นจริง $P(k+1)$ จึงเป็นจริง อย่างไรก็ตาม สูตรดังกล่าวนี้ไม่เป็นจริงทุก ๆ ค่า $n$ ใด ๆ ที่เป็นเลขจำนวนเต็มบวก ซึ่งทดสอบได้ด้วย $P(1)$

ตัวอย่าง 9 กำหนดให้ $a_1,a_2, a_3,⋯ $ เป็น sequence ของเลขจำนวนเต็มที่ $a_1=0$ และสำหรับ $n > 1$, $ a_n= n^3+a_{n-1} $ จงพิสูจน์ว่าทุก ๆ จำนวนเต็ม $n$

$$a_n=((n-1)(n+2)(n^2+n+2))/4$$

ให้ $P(n)= a_n = ((n-1)(n+2)(n^2+n+2))/4$

Basis step: เมื่อ $n = 1$, จากสูตรจะได้ $(1-1)(1+2)(12+1+2)/4 = 0$, ซึ่งคือค่า $a_1$

Induction step: ให้ $P(k)$ เป็นจริง นั่นคือ $a_k=((k-1)(k+2) (k^2+k+2) )/4$

เราจะต้องแสดงให้เห็นว่า $P(k+1)$ เป็นจริง นั่นคือ

$$a_{k+1}=(((k+1)-1)((k+1)+2) ((k+1)^2+(k+1)+2) )/4$$