418531 ภาคต้น 2552/โจทย์ปัญหาการพิสูจน์ II/เฉลยข้อ 3

การพิสูจน์ข้อความในโจทย์นี้เราจะใช้เทคนิคการพิสูจน์ที่เรียกว่า backward induction (induction กลับหลัง) ซึ่งมีโครงร่างดังต่อไปนี้

สมมติให้ P(n) เป็นข้อความที่เรา้ต้องการพิสูจน์ ในกรณีนี้คือข้อความ ${\frac {a_{1}+a_{2}+\dotsb +a_{n}}{n}}\geq {\sqrt[{n}]{a_{1}a_{2}\cdots a_{n}}}$

1. เราจะแสดงว่า P(n) เป็นจริงสำหรับ n ซึ่งมีค่าเท่ากับ $2^{k}$ เมื่อ k เป็นจำนวนจริงที่ไม่เป็นลบ กล่าวคือเราจะแสดงว่า P(1), P(2), P(4), P(8), ...
2. เสร็จแล้วเราจะแสดงว่าถ้า P(n) เป็นจริง แล้ว P(n-1) จะเป็นจริงด้วย

ทำไมเมื่อแสดงว่าข้อความข้างบนสองข้อความเป็นจริงแล้ว เราถึงสามารถสรุปได้ว่า P(n) เป็นจริงสำหรับจำนวนเต็มบวก n ทั้งหมดได้?

สังเกตว่าเราแสดงว่า P(8) เป็นจริงก่อน แล้วถ้า P(8) เป็นจริง เราจะได้ว่า P(7) เป็นจริงด้วย เมื่อ P(7) เป็นจริง P(6) ก็จะเป็นจริง ซึ่งส่งผลให้ P(5) เป็นจริงด้วย (เราไม่ต้องแสดงว่า P(4) เป็นจริงอีกรอบเนื่องจากเราได้เคยแสดงว่ามันเป็นจริงมาก่อนหน้านี้แล้ว)

เช่นเดียวกับ สำหรับจำนวนเต็ม n ใดๆ ถ้า n ไม่อยู่ในรูป $2^{k}$ ก็จะมีจำนวนเต็ม k ที่ทำให้ $2^{k}>m$ เสมอ ดังนั้นเราสามารถสรุปได้ว่า P(n) เป็นจริงเนื่องจาก $P(2^{k})$ เป็นจริงนั่นเอง

การพิสูจน์ของเราจะใช้ lemma ต่อไปนี้เป็นเครื่องมือที่สำคัญ

lemma 1: ถ้า a และ b เป็นจำนวนเต็มบวกใดๆ แล้ว ${\frac {a+b}{2}}\geq {\sqrt {ab}}$

พิสูจน์ (lemma 1): ให้ a และ b เป็นจำนวนเต็มบวกใดๆ เราได้ว่า

$({\sqrt {a}}-{\sqrt {b}})^{2}$	$\geq \,$	$0\,$
$a-2{\sqrt {ab}}+b$	$\geq \,$	$0\,$
$a+b\,$	$\geq \,$	$2{\sqrt {ab}}$
${\frac {a+b}{2}}$	$\geq \,$	${\sqrt {ab}}$

ต่อไปเราจะพิสูจน์ว่า $P(n)$ เป็นจริืงสำหรับ $n=2^{k}$ เมื่อ $k$ เป็นจำนวนเต็มที่ไม่เป็นลบ

lemma 2: ให้ k เป็นจำนวนเต็มที่ไม่เป็นลบใดๆ และให้ $a_{1},a_{2},a_{3},\ldots ,a_{2^{k}}$ เป็นจำนวนจริงบวกใดๆ แล้ว

${\frac {a_{1}+a_{2}+\dotsb +a_{2^{k}}}{2^{k}}}\geq (a_{1}a_{2}\cdots a_{2^{k}})^{1/2^{k}}$

พิสูจน์ (lemma 2): (Base Case) ในกรณีนี้ k มีค่าเท่ากับ 0 และเราจะได้ว่า ${\frac {a_{1}}{1}}=a_{1}=(a_{1})^{1/2^{0}}$

(Induction Case) ให้ k เป็นจำนวนเต็มที่ไม่เป็นลบใดๆ สมมติว่า ${\frac {a_{1}+a_{2}+\dotsb +a_{2^{k}}}{2^{k}}}\geq (a_{1}a_{2}\cdots a_{2^{k}})^{1/2^{k}}$ สำหรับจำนวนจริืงบวก $a_{1},a_{2},\ldots ,a_{2^{k}}$ ใดๆ

ให้ $a_{1},a_{2},\ldots ,a_{2^{k+1}}$ เป็นจำนวนเต็มบวก $2^{k+1}$ ใดๆ กำหนดให้

• $A_{0}={\frac {a_{1}+a_{2}+\dotsb +a_{2^{k}}}{2^{k}}}$
• $A_{1}={\frac {a_{2^{k}+1}+a_{2^{k}+2}+\dotsb +a_{2^{k+1}}}{2^{k}}}$
• $G_{0}=(a_{1}a_{2}\cdots a_{2^{k}})^{1/2^{k}}$
• $G_{1}=(a_{2^{k}+1}a_{2^{k}+2}\cdots a_{2^{k+1}})^{1/2^{k}}$

จากสมมติฐานที่ตั้งไว้ เราได้ว่า $A_{0}\geq G_{0}$ และ $A_{1}\geq G_{1}$

จาก lemma 1 เราได้ว่า ${\frac {A_{0}+A_{1}}{2}}\geq {\sqrt {A_{0}A_{1}}}$ แต่จากสมมติฐาน เราทราบว่า ${\sqrt {A_{0}A_{1}}}\geq {\sqrt {G_{0}G_{1}}}$ ดังนั้น ${\frac {A_{0}+A_{1}}{2}}\geq {\sqrt {G_{0}G_{1}}}$

นอกจากนี้เรายังทราบอีกว่า ${\frac {A_{0}+A_{1}}{2}}={\frac {(a_{1}+\dotsb +a_{2^{k}})/2^{k}+(a_{2^{k}+1}+\dotsb +a_{2^{k+1}})/2^{k}}{2}}={\frac {a_{1}+a_{2}+\dotsb +a_{2^{k+1}}}{2^{k+1}}}$

และ ${\sqrt {G_{0}G_{1}}}=[(a_{1}a_{2}\cdots a_{2^{k}})^{1/2^{k}}(a_{2^{k}+1}a_{2^{k}+2}\cdots a_{2^{k+1}})^{1/2^{k}}]^{1/2}=(a_{1}a_{2}\cdots a_{2^{k+1}})^{1/2^{k+1}}$

ดังนั้นเราจึงสามารถสรุปได้ว่า ${\frac {a_{1}+a_{2}+\dotsb +a_{2^{k}}}{2^{k}}}\geq (a_{1}a_{2}\cdots a_{2^{k}})^{1/2^{k}}$ เป็นจริงสำหรับจำนวนเต็ม k ที่ไม่เป็นลบทุกจำนวน

ต่อไปเราจะพิสูจน์ขั้น "induction กลับหลัง"

lemma 3: ให้ $n\,$ เป็นจำนวนเต็มที่มากกว่า 1 และให้ $a_{1},a_{2},\ldots ,a_{n}\,$ เป็นจำนวนจริงบวกใดๆ ถ้า ${\frac {a_{1}+a_{2}+\dotsb +a_{n}}{n}}\geq (a_{1}a_{2}\cdots a_{n})^{1/n}$ แล้ว ${\frac {a_{1}+a_{2}+\dotsb +a_{n-1}}{n-1}}\geq (a_{1}a_{2}\cdots a_{n-1})^{1/(n-1)}$

พิสูจน์ (lemma 3): เนื่อกจากอสมการ ${\frac {a_{1}+a_{2}+\dotsb +a_{n}}{n}}\geq (a_{1}a_{2}\cdots a_{n})^{1/n}$ เราสามารถกำหนดใ้ห้ $a_{n}=(a_{1}a_{2}\cdots a_{n-1})^{1/(n-1)}$ และเราจะได้ว่า

${\frac {a_{1}+a_{2}+\dotsb +a_{n-1}+(a_{1}a_{2}\cdots a_{n-1})^{1/(n-1)}}{n}}\,$	$\geq \,$	${\big (}a_{1}a_{2}\cdots a_{n-1}(a_{1}a_{2}\cdots a_{n-1})^{1/(n-1)}{\big )}^{1/n}\,$
${\frac {a_{1}+a_{2}+\dotsb +a_{n-1}}{n}}+{\frac {(a_{1}a_{2}\cdots a_{n-1})^{1/(n-1)}}{n}}\,$	$\geq \,$	${\big (}a_{1}^{n/(n-1)}a_{2}^{n/(n-1)}\cdots a_{n-1}^{n/(n-1)}{\big )}^{1/n}\,$
${\frac {a_{1}+a_{2}+\dotsb +a_{n-1}}{n}}+{\frac {(a_{1}a_{2}\cdots a_{n-1})^{1/(n-1)}}{n}}\,$	$\geq \,$	$a_{1}^{1/(n-1)}a_{2}^{1/(n-1)}\cdots a_{1-1}^{1/(n-1)}\,$
${\frac {a_{1}+a_{2}+\dotsb +a_{n-1}}{n}}+{\frac {(a_{1}a_{2}\cdots a_{n-1})^{1/(n-1)}}{n}}\,$	$\geq \,$	$(a_{1}a_{2}\cdots a_{1-1})^{1/(n-1)}\,$
${\frac {a_{1}+a_{2}+\dotsb +a_{n-1}}{n}}\,$	$\geq \,$	${\frac {n-1}{n}}(a_{1}a_{2}\cdots a_{1-1})^{1/(n-1)}\,$
${\frac {a_{1}+a_{2}+\dotsb +a_{n-1}}{n-1}}\,$	$\geq \,$	$(a_{1}a_{2}\cdots a_{1-1})^{1/(n-1)}\,$

ดังนั้นเราจึงสรุปได้ว่า

ทฤษฏีบท (อสมการ AM-GM): ถ้า $a_{1},a_{2},\ldots ,a_{n}\,$ เป็นจำนวนจริงบวกใดๆ แล้ว ${\frac {a_{1}+a_{2}+\dotsb +a_{n}}{n}}\geq (a_{1}a_{2}\cdots a_{n})^{1/n}$