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

ข้อย่อย 1

สูตรคือ ${\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+\cdots +{\frac {1}{2^{n}}}={\frac {2^{n}-1}{2^{n}}}$

base case: ให้ $n=1$

${\frac {1}{2^{1}}}={\frac {2^{1}-1}{2^{1}}}={\frac {1}{2}}$ เป็นจริง

inductive step: inductive hypothesis คือสมมติให้ p(n) คือ ${\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+\cdots +{\frac {1}{2^{n}}}={\frac {2^{n}-1}{2^{n}}}$ เป็นจริง ต้องการพิสูจน์ว่า p(n+1) คือ ${\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+\cdots +{\frac {1}{2^{n+1}}}={\frac {2^{n+1}-1}{2^{n+1}}}$ เป็นจริงด้วย

จากที่สมมติไว้คือ ${\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+\cdots +{\frac {1}{2^{n}}}={\frac {2^{n}-1}{2^{n}}}$

บวกทั้งสองข้างของสมการด้วย ${\frac {1}{2^{n+1}}}$

จะได้ ${\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+\cdots +{\frac {1}{2^{n}}}+{\frac {1}{2^{n+1}}}={\frac {2^{n}-1}{2^{n}}}+{\frac {1}{2^{n+1}}}$

$={\frac {2}{2}}.{\frac {2^{n}-1}{2^{n}}}+{\frac {1}{2^{n+1}}}$

$={\frac {2^{n+1}-2}{2^{n+1}}}+{\frac {1}{2^{n+1}}}$

$={\frac {2^{n+1}-1}{2^{n+1}}}$

ดังนั้นจึงสรุปได้ว่า ${\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+\cdots +{\frac {1}{2^{n}}}={\frac {2^{n}-1}{2^{n}}}$

ข้อย่อย 2

สูตรคือ ${\frac {1}{1\cdot 2}}+{\frac {1}{2\cdot 3}}+{\frac {1}{3\cdot 4}}+\cdots +{\frac {1}{n(n+1)}}={\frac {n}{n+1}}$

base case: ให้ $n=1$

${\frac {1}{1(1+1)}}={\frac {1}{1+1}}={\frac {1}{2}}$ เป็นจริง

inductive step: inductive hypothesis คือสมมติให้ p(n)คือ ${\frac {1}{1\cdot 2}}+{\frac {1}{2\cdot 3}}+{\frac {1}{3\cdot 4}}+\cdots +{\frac {1}{n(n+1)}}={\frac {n}{n+1}}$ เป็นจริง ต้องการพิสูจน์ว่า ${\frac {1}{1\cdot 2}}+{\frac {1}{2\cdot 3}}+{\frac {1}{3\cdot 4}}+\cdots +{\frac {1}{(n+1)(n+2)}}={\frac {n+1}{n+2}}$ เป็นจริงด้วย

จากที่สมมติไว้คือ ${\frac {1}{1\cdot 2}}+{\frac {1}{2\cdot 3}}+{\frac {1}{3\cdot 4}}+\cdots +{\frac {1}{n(n+1)}}={\frac {n}{n+1}}$

บวก ${\frac {1}{(n+1)(n+2)}}$ ทั้งสองข้างของสมการ

จะได้ ${\frac {1}{1\cdot 2}}+{\frac {1}{2\cdot 3}}+{\frac {1}{3\cdot 4}}+\cdots +{\frac {1}{n(n+1)}}+{\frac {1}{(n+1)(n+2)}}={\frac {n}{n+1}}+{\frac {1}{(n+1)(n+2)}}$

$={\frac {n}{(n+1)}}.{\frac {(n+2)}{(n+2)}}+{\frac {1}{(n+1)(n+2)}}$

$={\frac {(n+1)(n+1)}{(n+1)(n+2)}}$

$={\frac {(n+1)}{(n+2)}}$

ดังนั้นเราจึงสรุปได้ว่า ${\frac {1}{1\cdot 2}}+{\frac {1}{2\cdot 3}}+{\frac {1}{3\cdot 4}}+\cdots +{\frac {1}{n(n+1)}}={\frac {n}{n+1}}$ เป็นจริง

ข้อย่อย 3

(Base Case) เนื่องจาก $n=0\,$ เราได้ว่า $1=(2\cdot 0+1)^{2}=(0+1)(2\cdot 0+1)(2\cdot 0+3)/3\,$

(Induction Case) สมมติให้ n เป็นจำนวนเต็มที่มีค่ามากกว่าหรือเท่ากับ 0 และสมมติให้สมการในโจทย์เป็นจริง เราได้ว่า

$1^{2}+3^{2}+\dotsb +(2(n+1)+1)^{2}\,$	$=\,$	$(1^{2}+3^{2}+\dotsb +(2n+1)^{2})+(2n+3)^{2}\,$
	$=\,$	${\frac {(n+1)(2n+1)(2n+3)}{3}}+(2n+3)^{2}\,$
	$=\,$	$(2n+3){\bigg [}{\frac {(n+1)(2n+1)}{3}}+(2n+3){\bigg ]}\,$
	$=\,$	$(2n+3){\bigg [}{\frac {2n^{2}+3n+1+3(2n+3)}{3}}{\bigg ]}\,$
	$=\,$	$(2n+3){\bigg [}{\frac {2n^{2}+9n+10}{3}}{\bigg ]}\,$
	$=\,$	$(2n+3){\frac {(n+2)(2n+5)}{3}}\,$
	$=\,$	${\frac {((n+1)+1)((2(n+1)+1)(2(n+1)+3)}{3}}\,$

ฉะนั้นเราจึงสามารถสรุปได้ว่าสมการในโจทย์เป็นจริงสำหรับจำนวนเต็ม n ที่ไม่เป็นลบทุกจำนวน

ข้อย่อย 4

base case: คือ n=5 แทนค่าจะได้

$2^{5}>5^{2}$ เป็นจริง

inductive step: inductive hypothesis คือ สมมติให้ p(n) คือ $2^{n}>n^{2}$ เป็นจริง ต้องการแสดงว่า $2^{n+1}>(n+1)^{2}$ เป็นจริงด้วย

จากที่สมมติ $2^{n}>n^{2}$

คูณ 2 ทั้งสองข้างของสมการจะได้

$2.2^{n}>2.n^{2}$

$2^{n+1}>n^{2}+n^{2}$

$\geq n^{2}+5n$ เนื่องจาก n>4

$\geq n^{2}+2n+1$

$=(n+1)^{2}$

ดังนั้นเราจึงสรุปได้ว่า $2^{n}>n^{2}$ เป็นจริง เมื่อ n เป็นจำนวนเต็มบวกที่มีค่ามากกว่า 4

ข้อย่อย 5

(Base Case) n มีค่าเท่ากับ 2 และเราได้ว่า $1+1/4=5/4<3/2=2-1/2\,$

(Induction Case) สมมติให้ n เป็นจำนวนเต็มบวกที่มีค่ามากกว่า 2 และให้สมการในโจทย์เป็นจริง เราได้ว่า

$1+{\frac {1}{4}}+\dotsb +{\frac {1}{n+1}}^{2}\,$	$=\,$	$(1+{\frac {1}{4}}+\dotsb +{\frac {1}{n^{2}}})+{\frac {1}{(n+1)^{n}}}\,$
	$<\,$	$2-{\frac {1}{n}}+{\frac {1}{(n+1)^{2}}}\,$
	$<\,$	$2-{\frac {1}{n}}+{\frac {1}{n(n+1)}}\,$
	$=\,$	$2-{\frac {1}{n}}{\Bigg [}1-{\frac {1}{n+1}}{\Bigg ]}\,$
	$=\,$	$2-{\frac {1}{n}}{\frac {n}{n+1}}\,$
	$=\,$	$2-{\frac {1}{n+1}}\,$

ดังนั้นเราสามารถสรุปได้ว่าสมการในโจทย์เป็นจริงสำหรับจำนวนจริง $n>1$ ทุกจำนวน

ข้อย่อย 6

(Base Case) n มีค่าเท่ากับ 0 และเราได้ว่า $0^{3}-0=0$ ซึ่งหารด้วย 6 ได้ลงตัว

(Induction Case) สมมติว่า n เป็นจำนวนเต็มที่ไม่เป็นลบ และสมมติให้ $n^{3}-n$ หารด้วย 6 ลงตัว

พิจารณาค่า $(n+1)^{3}-(n+1)=n^{3}+3n^{2}+3n+1-n-1=(n^{3}-n)+3n^{2}+3n=(n^{3}-n)+3n(n+1)$

เราได้ว่า 6 หาร $3n(n+1)$ ลงตัวเนื่องจาก 3 หาร $3n(n+1)$ ลงตัว นอกจากนี้ 2 ยังหาร $3n(n+1)$ ลงตัวเนื่องจากในค่า $n$ และ $n+1$ ลงตัว จะต้องมีสักตัวที่เป็นจำนวนคู่

เนื่องจาก 6 หารทั้ง $n^{3}-n$ และ $3n(n+1)$ ลงตัว เราจึงได้ว่า 6 หาร $(n^{3}-n)+3n(n+1)=(n+1)^{3}-(n+1)$ ลงตัวด้วย

ดังนั้นเราจึงสรุปได้ว่า 6 หาร $n^{3}-n$ ลงตัวสำหรับจำนวนเต็ม n ที่ไม่เป็นลบทุกจำนวน

ข้อย่อย 7

ก่อนเราจะทำการพิสูจน์ข้อความในโจทย์ เราจะทำการพิสูจน์ lemma ต่อไปนี้

lemma: ให้ $A\,$, $B\,$, $C\,$ และ $D\,$ เป็นเซตใดๆ ที่ $A\subseteq C\,$ และ $B\subseteq D\,$ แล้ว $A\cap B\subseteq C\cap D$

พิสูจน์ (lemma): ให้ x เป็นค่าใดๆ สมมติให้ $x\in A\cap B$ เราได้ว่า $x\in A$ และ $x\in B$

เนื่องจาก $A\subseteq C$ และ $B\subseteq D$ เราได้ว่า $x\in C$ และ $x\in D$ ด้วย ดังนั้น $x\in C\cap D$

เนื่องจาก x เป็นค่าใดๆ เราจึงสามารถสรุปได้ว่า $\forall x,[x\in A\cap B\rightarrow x\in C\cap D]$ ฉะนั้น $A\cap B\subseteq C\cap D$

พิสูจน์ (โจทย์)

(Base Case) n มีค่าเท่ากับ 1 ในกรณีนี้เราได้ว่า $\bigcap _{i=1}^{1}A_{i}=A\subseteq B=\bigcap _{i=1}^{1}B_{i}\,$

(Induction Case) ให้ n เป็นจำนวนเต็มบวก และสมมติให้ข้อความที่โจทย์ต้องการพิสูจน์เป็นจริง

เราได้ว่า $\bigcap _{i=1}^{n+1}A_{i}=A_{n+1}\cap \bigcap _{i=1}^{n}A_{i}$ และ

โจทย์กำหนดว่า $A_{n+1}\subseteq B_{n+1}$ และจาำกสมมติฐานเราได้ว่า $\bigcap _{i=1}^{n}A_{i}=A\bigcap _{i=1}^{n}B_{i}\,$ ฉะนั้นด้วย lemma เราได้ว่า

ฉะนั้นเราจึงสรุปได้ว่าข้อความในโจทย์เป็นจริงสำหรับจำนวนเต็มบวก n ทุกค่า

ข้อย่อย 8

(Base Case) n มีค่าเท่ากับ 1 และเราจะได้ว่า $1\cdot 2^{1-1}=1=(1-1)2^{1}+1$

(Induction Case) ให้ n เป็นจำนวนเต็มที่มีค่ามากกว่า 0 และสมมติให้สมการในโจทย์เป็นจริง ได้ว่า

$1\cdot 2^{0}+2\cdot 2^{1}+\dotsb +(n+1)\cdot 2^{n}\,$	$=\,$	$(1\cdot 2^{0}+2\cdot 2^{1}+\dotsb +n\cdot 2^{n-1})+(n+1)\cdot 2^{n}\,$
	$=\,$	$(n-1)2^{n}+1+(n+1)\cdot 2^{n}\,$
	$=\,$	$(2n)\cdot 2^{n}+1\,$
	$=\,$	$n\cdot 2^{n+1}+1\,$

ดังนั้นเราสรุปได้ว่าสมการเป็นจริงสำหรับจำนวนเต็มบวก n ทุกจำนวน

ข้อ 9

(Base Case) n มีค่าเท่ากับ 1 และเราได้ว่า $4^{1+1}+5^{2\cdot 1-1}=16+5=21$ ซึ่งหารด้วย 21 ลงตัว

(Induction Case) ให้ n เป็นจำนวนเต็มบวก และสมมติให้ $4^{n+1}+5^{2n-1}$ หารด้วย 21 ลงตัว

เราได้ว่า $4^{n+2}+5^{2n+1}=4\cdot 4^{n+1}+25\cdot 5^{2n-1}=(25-21)4^{n+1}+25\cdot 5^{2n-1}=25(4^{n+1}+5^{2n-1})+21\cdot 4^{n+1}$

จากสมมติฐาน เราได้ว่า 21 หาร $4^{n+1}+5^{2n-1}$ ลงตัว ดังนั้นมันจึงหาร $25(4^{n+1}+5^{2n-1})$ ลงตัว และเนื่องจาก 21 หาร $21\cdot 4^{n+1}$ ลงตัว เราจึงได้ว่า 21 หาร $25(4^{n+1}+5^{2n-1})+21\cdot 4^{n+1}=4^{n+2}+5^{2n+1}$

ฉะนั้นเราจึงสามารถสรุปได้ว่า 21 หาร $4^{n+1}+5^{2n-1}$ ลงตัวสำหรับจำนวนเต็มบวก n ทุกจำนวน

ข้อ 10

lemma: สำหรับจำนวนเต็มบวก n ใดๆ $2{\sqrt {n+1}}+{\frac {1}{\sqrt {n+1}}}>2{\sqrt {n+2}}$

พิสูจน์ (lemma): เราได้ว่า

${\sqrt {n+2}}+{\sqrt {n+1}}$	$>\,$	$2{\sqrt {n+1}}$
$({\sqrt {n+2}}+{\sqrt {n+1}}){\frac {{\sqrt {n+2}}-{\sqrt {n+1}}}{{\sqrt {n+2}}-{\sqrt {n+1}}}}$	$>\,$	$2{\sqrt {n+1}}$
${\frac {1}{{\sqrt {n+2}}-{\sqrt {n+1}}}}$	$>\,$	$2{\sqrt {n+1}}$
${\frac {1}{\sqrt {n+1}}}$	$>\,$	$2{\sqrt {n+2}}-2{\sqrt {n+1}}$
$2{\sqrt {n+1}}+{\frac {1}{\sqrt {n+1}}}$	$>\,$	$2{\sqrt {n+2}}$

พิสูจน์ (โจทย์)

(Base Case) n มีค่าเท่ากับ 1 เราได้ว่า $1>0.82842712474619029\dotsb =2({\sqrt {1+1}}-1)\,$

(Induction Case) ให้ n เป็นจำนวนเต็มบวก และสมมติให้อสมการในโจทย์เป็นจริง เราได้ว่า

$1+{\frac {1}{\sqrt {2}}}+\dotsb +{\frac {1}{\sqrt {n+1}}}>2({\sqrt {n+1}}-1)+{\frac {1}{\sqrt {n+1}}}=2{\sqrt {n+1}}+{\frac {1}{\sqrt {n+1}}}-2>2{\sqrt {n+2}}-2=2({\sqrt {n+2}}-1)$

ดังนั้นเราสามารถสรุปได้ว่าอสมการในโจทย์เป็นจริงสำหรับจำนวนเต็มบวก n ทุกตัว