نمونه سوال ریاضی علم کامپیوتر - استقرا

مثال: نشان دهید برای هر عدد طبیعی n:

پاسخ: اثبات را با استفاده از اصل استقرای ریاضی انجام می دهیم:
1- درستی حکم داده شده را برای n=1 بررسی می کنیم: (مرحله مبنایی استقرا)
سمت راست تساوی: 4
سمت چپ تساوی:
پس برای n=1 طرفین تساوی دادهشده با هم برابر می شوند که نشان می دهد حکم برای n=1 درست است.
2- فرض می کنیم تساوی داده شده به ازای عدد طبیعی n=k برقرار باشد(فرض استقرا) یعنی:

حال نشان میدهیم حکم برای n=k+1 هم برقرار است(حکم استقرا) یعنی:

برای اثبات حکم استقرا از فرض استقرا کمک می گیریم. برای این کار به طرفین فرض استقرا عبارت را اضافه میکنیم:

حال در سمت راست تساوی فوق داریم:

پس نشان داده شد:
به این ترتیب بر طبق اصل استقرا حکم فوق برای هر n عضو اعداد طبیعی برقرار است.

.......................................................................................................................................

مثال2: نشان دهید عدد طبیعی مناسبی مانند m وجود دارد که برای هر عدد طبیعی n بزرگتر یا مساوی m داریـم:

پاسخ: با قرار دادن مقادیر طبیعی برای m متوجه می شویم که m مناسب 3 است چرا که برای اولین بار حکم برای m=3 درست است.حال نشان میدهیم حکم برای هر عدد طبیعی

برقرار است.
1-

2- اکنون در این مرحله فرض (فرض استقرا) می کنیم نامساوی فوق برای هر عدد طبیعی

درست باشد یعنی:

نشان میدهیم حکم داده شده برای (n=k+1 ،(k>2 درست است، یعنی:

(حکم استقرا)
برای این منظور از فرض استقرا استفاده کرده و به طرفین فرض عدد 2 را اضافه می کنیم، داریم:

حال با مقایسه نامساوی اخیر و حکم استقرا کافی است نشان دهیم:

برای این کار از اثبات بازگشتی کمک میگیریم:

مشاهده می شود نامساوی برای K>2 همواره درست است و چون تمامی روابط برگشت پذیرند، لذا برقرار بوده و به این ترتیب حکم برای هر عدد طبیعی برقرار است.

........................................................................................................................................

مثال3: نشان دهید در هر n ضلعی محدب تعداد قطرها برابر است با:

می دانیم یک 3 ضلعی محدب،دارای قطر نیست و چهار ضلعی محدب فقط دو قطر دارد . به این ترتیب حکم را برای n>3 اثبات می کنیم. مرحله اول (مبنا) را با n=4 آغاز می کنیم:
1-

حال فرض می کنیم که حکم برای n=k درست باشد، یعنی تعداد قطرهای هر k ضلعی محدب برابر باشد با:

نشان می دهیم که حکم برای n=k+1 هم درست است، یعنی تعداد قطرهای هر k+1 ضلعی محدب برابر است با:

برای اثبات سعی می کنی به گونه ای از فرض استقرا استفاده کنیم. به این صورت که می دانیم که اگر به تعداد ضلعهای یک n ضلعی، یک ضلع اضافه کنیم یا به تعداد رئوس آن یک راس اضافه کنیم به تعداد قطرهای آن n-1 واحد اضافه می شود. لذا: (k-1)+تعداد قطرهای k ضلعی محدب=تعداد قطرهای k+1 ضلعی محدب
بنابراین رابطه زیر برقرار است: