مقدمه‌ای بر اثبات · استقرای ریاضی
گزاره‌ای را برای همهٔ اعداد صحیح از یک نقطهٔ آغاز مشخص اثبات کنید. حالت پایه را انتخاب کنید، فرض استقرا را به کار ببرید و گام استقرا را بدون فرض گرفتن نتیجه بررسی کنید.
پیش از شروع
باید بتوانید حاصل‌ضرب را بسط دهید، جمله‌ای به مجموع متناهی بیفزایید و یک گزارهٔ شرطی را بخوانید. در صورت نیاز درس پیشین دربارهٔ اثبات مستقیم را مرور کنید.
اصل استقرا
فرض کنید P(n) گزاره‌ای دربارهٔ عدد صحیح n و b اولین عدد صحیح در ادعا باشد. ابتدا P(b) را مستقیم اثبات کنید. سپس عدد صحیح دلخواه k ≥ b را بگیرید، P(k) را برای همان k فرض کنید و P(k + 1) را نتیجه بگیرید. با این دو گام، P(n) برای هر عدد صحیح n ≥ b برقرار است.
دلیل اعتبار: اگر مثال نقضی وجود داشته باشد، کوچک‌ترین آن m ≥ b است. حالت پایه m = b را رد می‌کند. بنابراین m − 1 ≥ b گزاره را برآورده می‌کند و گام استقرا نشان می‌دهد که m نیز آن را برآورده می‌کند. این با انتخاب m تناقض دارد.
مثال‌های حل‌شده
جمع یک دنبالهٔ حسابی
ادعا: مجموع 4j + 1 برای j از ۱ تا n برابر n(2n + 3) است، برای n ≥ 1. در n = 1 هر دو طرف ۵ هستند. فرض کنید مجموع تا k برابر k(2k + 3) است. جملهٔ بعدی 4(k + 1) + 1 = 4k + 5 است. با جمع کردن، 2k² + 7k + 5 = (k + 1)(2(k + 1) + 3) به دست می‌آید که همان فرمول در k + 1 است.
اثبات بخش‌پذیری
ادعا: 5ⁿ − 1 برای هر n ≥ 0 بر ۴ بخش‌پذیر است. در n = 0 عبارت صفر است. فرض کنید 5ᵏ − 1 = 4q برای عدد صحیح q. آنگاه 5ᵏ⁺¹ − 1 = 5(5ᵏ − 1) + 4 = 4(5q + 1) که باز هم مضرب ۴ است.
اشتباه‌های رایج
- از اولین عدد صحیح ادعا آغاز کنید. حالت پایه در n = 2 گزاره را در n = 1 اثبات نمی‌کند.
- فقط P(k) را فرض کنید. پیش از جبر، هدف P(k + 1) را جداگانه بنویسید.
- چند مقدار برابر می‌توانند از یک حدس پشتیبانی کنند. گام کلی است که ادعا را اثبات می‌کند.
تمرین
- نشان دهید مجموع n عدد فرد مثبت نخست برابر n² است، برای n ≥ 1.
- نشان دهید n! ≥ 2ⁿ⁻¹ برای n ≥ 1. توضیح دهید چرا ضرب جهت نامساوی را حفظ می‌کند.
پاسخ‌های تشریحی
- در n = 1 داریم 1 = 1². فرض کنید مجموع k جمله k² است. جملهٔ فرد بعدی 2k + 1 است، پس مجموع جدید k² + 2k + 1 = (k + 1)² است. اصل استقرا ادعا را اثبات می‌کند.
- در n = 1 داریم 1! = 2⁰ = 1. فرض کنید k! ≥ 2ᵏ⁻¹. چون k + 1 ≥ 2 و مثبت است، (k + 1)! = (k + 1)k! ≥ (k + 1)2ᵏ⁻¹ ≥ 2ᵏ. این همان هدف در k + 1 است.
ارزیابی · ۱۰ نمره
- ۵ نمره. اثبات کنید 2 + 4 + … + 2n = n(n + 1) برای n ≥ 1.
- ۵ نمره. اثبات کنید 7ⁿ − 1 برای n ≥ 0 بر ۶ بخش‌پذیر است.
پاسخ‌نامه و نمره‌دهی
برای هر اثبات، ۱ نمره برای حالت پایه، ۱ برای فرض در k دلخواه، ۲ برای به‌دست‌آوردن حالت بعد و ۱ برای نتیجه و دامنه در نظر بگیرید.
- در n = 1 هر دو طرف ۲ هستند. فرض کنید مجموع تا k برابر k(k + 1) است. با افزودن 2(k + 1)، حاصل (k + 1)(k + 2) می‌شود. بنابراین فرمول برای هر n ≥ 1 برقرار است.
- در n = 0 داریم 7⁰ − 1 = 0. فرض کنید 7ᵏ − 1 = 6q برای عدد صحیح q. آنگاه 7ᵏ⁺¹ − 1 = 7(7ᵏ − 1) + 6 = 6(7q + 1). بنابراین 7ⁿ − 1 برای هر n ≥ 0 بر ۶ بخش‌پذیر است.
مطالعهٔ رایگان
بخش‌های ۳٫۱ تا ۳٫۲ را برای اصل استقرا و الگوی اثبات بخوانید. برای مسائل حل‌شدهٔ بیشتر، جلسهٔ تمرین ۲ را ببینید.
آزمایش مجازی · مقایسهٔ دو فرمول
اولین اختلاف دو فرمول را بیابید و توضیح دهید چرا برابری چند نمونه ادعا را اثبات نمی‌کند.
ابزار رایگان در همین صفحه. در مرورگر و بدون حساب کاربری یا دانلود استفاده کنید.
روش انجام
از ماشین‌حساب همین صفحه استفاده کنید. به‌ترتیب n را ۱، ۲، ۳، ۴ و ۵ قرار دهید. خروجی‌ها به‌ترتیب n² و n² + n(n − 1)(n − 2)(n − 3) هستند. اولین اختلاف را ثبت کنید. کدام عامل هر برابری قبلی را توضیح می‌دهد؟ آیا برابری در n = 3 برابری در n = 4 را نتیجه می‌دهد؟
نتایج مورد انتظار و بررسی پاسخ
در n برابر ۱، ۲ و ۳ به‌ترتیب عامل‌های n − 1، n − 2 و n − 3 صفر می‌شوند. در n = 4 خروجی‌ها ۱۶ و ۴۰ هستند، پس برابری در ۳ برابری در ۴ را نتیجه نمی‌دهد. در n = 5 خروجی‌ها ۲۵ و ۱۴۵ هستند.
ماشین‌حساب نمونه‌های متناهی را مقایسه می‌کند. یک مثال نقض می‌تواند ادعا را رد کند و اثبات یک اتحاد کلی به استدلال عمومی نیاز دارد.