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

Cardcaptor เมื่อ 11:08, 11 กรกฎาคม 2552

2009-07-11T11:08:25Z

Cardcaptor เมื่อ 11:04, 11 กรกฎาคม 2552

2009-07-11T11:04:59Z

158.108.183.136 เมื่อ 03:16, 10 กรกฎาคม 2552

2009-07-10T03:16:34Z

Cardcaptor: สร้างหน้าใหม่: === วิธีการพิสูจน์ === การพิสูจน์ข้อความในโจทย์นี้เราจะใช้...

2009-07-09T21:29:07Z

สร้างหน้าใหม่: === วิธีการพิสูจน์ === การพิสูจน์ข้อความในโจทย์นี้เราจะใช้...

หน้าใหม่

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

สมมติให้ P(n) เป็นข้อความที่เรา้ต้องการพิสูจน์ ในกรณีนี้คือข้อความ <math>\frac{a_1 + a_2 + \dotsb + a_n}{n} \geq \sqrt[n]{a_1 a_2 \cdots a_n}</math>
# เราจะแสดงว่า P(n) เป็นจริงสำหรับ n ซึ่งมีค่าเท่ากับ <math>2^k</math> เมื่อ k เป็นจำนวนจริงที่ไม่เป็นลบ กล่าวคือเราจะแสดงว่า P(1), P(2), P(4), P(8), ...
# เสร็จแล้วเราจะแสดงว่าถ้า P(n) เป็นจริง แล้ว P(n-1) จะเป็นจริงด้วย

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

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

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

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

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

''พิสูจน์ (lemma 1):'' ให้ a และ b เป็นจำนวนเต็มบวกใดๆ เราได้ว่า
<table cellpadding="5">
<tr>
<td align="right"><math>(\sqrt{a} - \sqrt{b})^2</math></td>
<td align="center"><math>\geq\,</math></td>
<td align="left"><math>0 \,</math></td>
</tr>
<tr>
<td align="right"><math>a - 2\sqrt{ab} + b</math></td>
<td align="center"><math>\geq\,</math></td>
<td align="left"><math>0 \,</math></td>
</tr>
<tr>
<td align="right"><math>a + b\,</math></td>
<td align="center"><math>\geq\,</math></td>
<td align="left"><math>2\sqrt{ab}</math></td>
</tr>
<tr>
<td align="right"><math>\frac{a + b}{2}</math></td>
<td align="center"><math>\geq\,</math></td>
<td align="left"><math>\sqrt{ab}</math></td>
</tr>
</table>

เราพร้อมแล้วที่จะพิสูจน์ข้อความ 1

'''lemma 2:''' ให้ k เป็นจำนวนเต็มที่ไม่เป็นลบใดๆ และให้ <math>a_1, a_2, a_3, \ldots, a_{2^k}</math> เป็นจำนวนเต็มบวกใดๆ แล้ว
: <math>\frac{a_1 + a_2 + \dotsb + a_{2^k}}{2^k} \geq (a_1 a_2 \cdots a_{2^k})^{1 / 2^k}</math>

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

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

ให้ <math>a_1, a_2, \ldots, a_{2^{k+1}}</math> เป็นจำนวนเต็มบวก <math>2^{k+1}</math> ใดๆ กำหนดให้
* <math>A_0 = \frac{a_1 + a_2 + \dotsb + a_{2^k}}{2^k}</math>
* <math>A_1 = \frac{a_{2^k+1} + a_{2^k+2} + \dotsb + a_{2^{k+1}}}{2^k}</math>
* <math>G_0 = (a_1 a_2 \cdots a_{2^k})^{ 1 / 2^k}</math>
* <math>G_1 = (a_{2^k+1} a_{2^k+2} \cdots a_{2^{k+1}})^{ 1 / 2^k}</math>
จากสมมติฐานที่ตั้งไว้ เราได้ว่า <math>A_0 \geq G_0</math> และ <math>A_1 \geq G_1</math>

จาก lemma 1 เราได้ว่า <math>\frac{A_0 + A_1}{2} \geq \sqrt{A_0 A_1}</math> แต่จากสมมติฐาน เราทราบว่า <math>\sqrt{A_0 A_1} \geq \sqrt{G_0 G_1}</math> ดังนั้น <math>\frac{A_0 + A_1}{2} \geq \sqrt{G_0 G_1}</math>

นอกจากนี้เรายังทราบอีกว่า <math>\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}}</math>

และ <math>\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}}</math>

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

@@ แถว 87: / แถว 87: @@
 <td align="center"><math>\geq \,</math></td>
 <td align="left"><math> a_1^{1/(n-1)} a_2^{1/(n-1)} \cdots a_{1-1}^{1/(n-1)}  \,</math></td>
 </tr>
 </table>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 03:16, 10 กรกฎาคม 2552
แถว 1:		แถว 1:
−	~~=== วิธีการพิสูจน์ ===~~
	การพิสูจน์ข้อความในโจทย์นี้เราจะใช้เทคนิคการพิสูจน์ที่เรียกว่า backward induction (induction กลับหลัง) ซึ่งมีโครงร่างดังต่อไปนี้		การพิสูจน์ข้อความในโจทย์นี้เราจะใช้เทคนิคการพิสูจน์ที่เรียกว่า backward induction (induction กลับหลัง) ซึ่งมีโครงร่างดังต่อไปนี้

@@ แถว 41: / แถว 41: @@
-เราพร้อมแล้วที่จะพิสูจน์ข้อความ 1
+ต่อไปเราจะพิสูจน์ว่า <math>P(n)</math> เป็นจริืงสำหรับ <math>n = 2^k</math> เมื่อ <math>k</math> เป็นจำนวนเต็มที่ไม่เป็นลบ
-'''lemma 2:''' ให้ k เป็นจำนวนเต็มที่ไม่เป็นลบใดๆ และให้ <math>a_1, a_2, a_3, \ldots, a_{2^k}</math> เป็นจำนวนเต็มบวกใดๆ แล้ว
+'''lemma 2:''' ให้ k เป็นจำนวนเต็มที่ไม่เป็นลบใดๆ และให้ <math>a_1, a_2, a_3, \ldots, a_{2^k}</math> เป็นจำนวนจริงบวกใดๆ แล้ว
 : <math>\frac{a_1 + a_2 + \dotsb + a_{2^k}}{2^k} \geq (a_1 a_2 \cdots a_{2^k})^{1 / 2^k}</math>
@@ แถว 64: / แถว 64: @@
 ดังนั้นเราจึงสามารถสรุปได้ว่า <math>\frac{a_1 + a_2 + \dotsb + a_{2^k}}{2^k} \geq (a_1 a_2 \cdots a_{2^k})^{1 / 2^k}</math> เป็นจริงสำหรับจำนวนเต็ม k ที่ไม่เป็นลบทุกจำนวน