استقرا

[atefeh]

1-ثابت کنيد تمام مردم دنيا دريک اتوبوس جا مي گيرند.
اثبات با استقراء رياضي:
براي n=1 : بديهي است يک نفر دراتوبوس جا مي گيرد.
فرض استقراء : فرض مي کنيم براي n=k حکم درست باشد.
بايد نشان دهيم براي n=k+1 نيز حکم درست است. يک نفر را جدا مي کنيم ، k نفر باقي مانده طبق فرض در اتوبوس جا مي گيرند، حال اگر مسافران کمي جا به جا شوند يک نفر به راحتي در اتوبوس جا مي شود. بنابراين حکم ثابت است.

2-ثابت كنيد تمام اسب هاي دنيا هم رنگند.
اثبات به استقراء: براي n=1 در مجموعه اي شامل يک عضو بديهي است.
n=k فرض کنيم در مجموعه اي شامل k اسب، اسب ها همرنگند.
براي n=k+1 ابتدا يکي از اسب ها را بيرون بکشيد k اسب باقي مانده بنابر فرض استقراء همرنگند اينک اسب بيرون کشيده شده را بر مجموعه بازگردانده ، اسب ديگري بيرون بياوريد اين بار هم k اسب باقي مانده از فرض استقراء همرنگند و حکم ثابت است.
به نظر شما اشكال استدلال هاي بالا در چيست ؟
آيا تمام مردم دنيا در يك اتوبوس جا مي گيرند ؟!
واقعاً تمام اسب هاي دنيا هم رنگند ؟!
منبع:سرزمین ریاضیات

 

[Admin2]

پاسخ : استقرا

آخه نمیشه که در مورد هرچیزی استقرا زد.
به احتمال زیاد یک نکته پنهان مفهومی داره که ما ازش غافلیم.

 

[trustme]

پاسخ : استقرا

اشکال استدلال های بالا اینه که استقرا نیستن!!

 

[Admin2]

پاسخ : استقرا

بله. استقرا نیست.
در ضمن پرشدن اتوبوس با اون استدلال یک مفهوم حدی داره. بالاخره ظرفیت تکمیل میشه.

 

[R-Σntezari]

پاسخ : استقرا

چند هفته قبل که استادمون(دکتر فلاح)داشت استقرا رو تو نظریه اعداد درس می داد(آخه بازم ما گسسته داریم :-X) گفت که یه نفر واسش میل زده ثابت کرده هر چقدر از درخت های جنگلو بکنیم بازم تموم نمیشه
ولی مشکل استدلالی در تعریفی که از استقرا کرده بود وجود داشت مثه همین استدلال های بالا

 

[lale]

پاسخ : استقرا

بله در استقراباید از nبهn_1رسید نه ازn بهn+1

 

[Admin2]

پاسخ : استقرا

اتفاقا در استقرا از n به n+1 می رسند !

 

[fzgm]

پاسخ : استقرا

نکته اینه که تو استقرا اتوبوس،از یه حدی که بیشتر بشه به ازای هر نفر ورودی یکی از 5ره میره بیرون!!!

 

[lale]

پاسخ : استقرا

نخیر چون تو مجموعه ی n+1ممکنه جوابایی بیشتر از مجموعه ی nباشه نکته اصلی استقرا هم همینه ولی در بعضی موارد این دو حالت با هم فرقی ندارن

 

[شاهزاده ریاضی]

پاسخ : استقرا

بحث جالبیست !
در استقرای ریاضی دو رکن مهم n=1 , n=k است که به کمک هم می آیند.
بدین صورت که در صورتی که برای 1 ثابت شود و نیزثابت شود می توان از n به n+1 برسیم یعنی ثابت کردیم از 1 می توان به 2 رسید و از 2 به 3 و به همین صورت برای تمام اعداد طبیعی. بنا براین سعی در این است که از n به n+1 برسیم. ^-^

 

[lale]

پاسخ : استقرا

نه ببینید این جا پایه 2 غلطه و نباید بتونیم از 1 بهش برسیم این جا ما داریم n+1امی رو انتخاب می کنیم در حالی که اگه ازn به n_1برسیم اسبا انتخاب شده هستند و امکان اشتباه نیست مثال های واضح تر رو بعدا براتو ن می نویسم

 

[lale]

پاسخ : استقرا

ببخشید منظور من دقیقا این بود که روn-1 فرض می گیریم و بعد طی گام بهn می رسیم

 

[shatoonak]

پاسخ : پاسخ : استقرا

اشکال استدلال های بالا اینه که استقرا نیستن!!

راست میگه !!!!!! من ثابت میکنم (نشونت میدم) حداقل یه اسب بین بقیه رنگ متضاد داره :P :P

 

[error]

پاسخ : استقرا

ببینید بچه ها اینا جوب های استقرا است
شما برای اتوبوس پر تعریف مشخص ندارید
مثلا با این استقرا می تونید اثبات کنید همه ی مردم کچل ان
اما بازم برا کچلی تعریف مشخصی نداریم

الان برای اسب ها اثبات درست تر اینه
پایه استقرا که درسته
حالا فرض کیند برای n نفر هم درست باشه یعنی هر اسب هم رنگ باشه اسب در نظر بگیرید
اسب ها را از 1 تا n+1 شماره گذاری کنید
اسب های شماره 1تا n را در نظر بگیرید اینا هم رنگ اند
اسب های 1 تا n-1 و n+1 را در نظر بگیرید اینا هم رنگند
پس همه یک رنگ اند و حکم ثابت شد


ولی اشتباه اینه
اگه بخایم از (p(n به (p(n+1 برسیم تعداد اسب ها حداقل باید 3تا باشه بنابر این از (p(1 به (p(2 نمیشه رسید

 

[arash.marashian]

پاسخ : استقرا

نه کاملا این استدلالت مشکل داره،از کجا معلوم که اون یه نفر جا شه!؟

 

[AlirezaRajabi]

پاسخ : استقرا

ببخشید بحث تاپیک رو منحرف میکنم،اما به نظرم سوالی که من دارم جاش همین جاس:
کسی میدونه استقرای دوگانه چیه؟ و به چه دردی میخوره؟واصلن چطور باید ازش استفاده بشه؟

 

[rezaezio]

پاسخ : استقرا

یه سری از مسائل هستند که مثلا حالت های زوج و فردشون با هم فرق داره !
توی حل یه اینچنین سوالی می تونی از استقرای دوگانه استفاده کنی
یه بار فرض می کنی n فرده و از فرض استقرا کمک میگیری و یه بار هم بر عکس ؛ در کل میشه گفت 2 تا گام استقرا داری

مسئله ای هم که الان معرفی می کنم ، یکی از راه های حلش استقرای دوگانه بوده !
مرحله دوم - دوره 4 المپیاد کامپیوتر - روز دوم - مسئله اول



این هم حلش با استقرای دوگانه

استقرا رو n میزنیم.ابتدا میبینیم که پایه استقرا به ازا 1 و 2 درسته!
بعد میگیم: به ازایn=k هم درسته. یعنی فرض میکنیم!
حالا حکم یعنی k+2 را باید اثبات کنیم!
میگیم k تا از این را k+2 انتخاب کرده طبق فرض استقرا میدونیم که این k تا به 3k/2-2 وزن کردن بزرگترین و کوچیکترین وزنه در میاد!حالا اون بزرگترین و کوچکترین رو b و a مینامیم. , و اون دوتایی رو هم که وزن نکردیم c و d می نامیم.
حال یکبار c و d وزن کرده و میفهمیم که کدوم کوچیکتر و کدوم بزرگتره!حال فرض میکنیم c از d بزرگتره.
ویکبار دیگه a و c و بار دیگر b و d وزن کرده و به ترتیب کوچیکترین و بزرگترین وزنه بدست میاد!
پس:3k/2-2 +3 = 3(k+2)/2-2 است!
حکم اثبات شد!
در اصل ما یکبار برای زوج ها و یکبار برای فرد ها گفتیم!

 

[arvin.a]

پاسخ : استقرا

1-ثابت کنيد تمام مردم دنيا دريک اتوبوس جا مي گيرند.
اثبات با استقراء رياضي:
براي n=1 : بديهي است يک نفر دراتوبوس جا مي گيرد.
فرض استقراء : فرض مي کنيم براي n=k حکم درست باشد.
بايد نشان دهيم براي n=k+1 نيز حکم درست است. يک نفر را جدا مي کنيم ، k نفر باقي مانده طبق فرض در اتوبوس جا مي گيرند، حال اگر مسافران کمي جا به جا شوند يک نفر به راحتي در اتوبوس جا مي شود. بنابراين حکم ثابت است.

2-ثابت كنيد تمام اسب هاي دنيا هم رنگند.
اثبات به استقراء: براي n=1 در مجموعه اي شامل يک عضو بديهي است.
n=k فرض کنيم در مجموعه اي شامل k اسب، اسب ها همرنگند.
براي n=k+1 ابتدا يکي از اسب ها را بيرون بکشيد k اسب باقي مانده بنابر فرض استقراء همرنگند اينک اسب بيرون کشيده شده را بر مجموعه بازگردانده ، اسب ديگري بيرون بياوريد اين بار هم k اسب باقي مانده از فرض استقراء همرنگند و حکم ثابت است.
به نظر شما اشكال استدلال هاي بالا در چيست ؟
آيا تمام مردم دنيا در يك اتوبوس جا مي گيرند ؟!
واقعاً تمام اسب هاي دنيا هم رنگند ؟!
منبع:سرزمین ریاضیات

نمیشه ثابت کرد چون همرنگی یه چیز نسبیه و حداقل باید یه مقایسه ای بین دو چیز باشه ولی اگه بخواید بر فرض از k و k+1 استفاده کنید یعنی هیچ مقایسه ای نشده پس نقض شد به قول مسعود بهرامی سنگ قبر

 

[sourna]

پاسخ : استقرا

با تشکر از همه ی عزیزان
ببینید استقرا انواع مختلفی داره مثلا:قهقرایی،تعمیم یافته و...
و همچنین ایرادهایی هم به اثبات از طریق استقرا وارده.

 

[Karo]

پاسخ : استقرا

با تشکر از همه ی عزیزان
ببینید استقرا انواع مختلفی داره مثلا:قهقرایی،تعمیم یافته و...
و همچنین ایرادهایی هم به اثبات از طریق استقرا وارده.

هیچ ایرادی در اثبات به طریق استقرا وارد نیست چون اصل استقرا ریاضی اثبات میشه
مشکل از ما است که اشتباه اثبات میکنیم