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

เราจะแสดงว่า $T(n)=n!+2^{n}\,$ สำหรับจำนวนเต็ม $n\geq 0\,$ ทุกจำนวน

(Base Case) มีอยู่สามกรณี

• $T_{0}=2=2^{0}+0!\,$
• $T_{1}=3=2+1=2^{1}+1!\,$
• $T_{2}=6=4+2=2^{2}+2!\,$

(Induction Case) ให้ $n\,$ เป็นจำนวนเต็มบวกที่มีค่ามากกว่าหรือเท่ากับ 2 และสมมติให้ $T_{k}=k!+2^{k}\,$ สำหรับจำนวนเต็ม $k\,$ ทุกตัวที่มีค่าตั้งแต่ 0 ถึง $n\,$ เราได้ว่า

$T_{n+1}\,$	$=\,$	$(n+1+4)T_{n}-4(n+1)T_{n-1}+(4n-4)T_{n-2}\,$
	$=\,$	$(n+1+4)(n!+2^{n})-(4n+4)((n-1)!+2^{n-1})+(4n-4)((n-2)!+2^{n-2})\,$
	$=\,$	$(n+1)!+4n!+n\cdot 2^{n}+5\cdot 2^{n}-4n!-4(n-1)!-2n\cdot 2^{n}-2\cdot 2^{n}+4(n-1)!+n\cdot 2^{n}-2^{n}\,$
	$=\,$	$(n+1)!+2\cdot 2^{n}=(n+1)!+2^{n+1}\,$

ดังนั้นเราสามารถสรุปได้ว่า $T_{n}=n!+2^{n}\,$ สำหรับจำนวนเต็ม $n\,$ ที่มีค่าไม่เป็นลบทุกจำนวน