(۲۷ خرداد ۱۳۹۴ ۰۶:۴۴ ب.ظ)pani*joon نوشته شده توسط:  سلام
چند روزه برای درک استقرا مشکل دارم
برای یاد گیری استقرا لطفا منبعی معرفی کنید. نحوه ی حل مسائل با استقرا متوجه نمیشم. مثلا فصل اول لینز با استقرا ثابت شده |x.y|=|x|+|y| یا مخصوصا تمرینات مربوط به استقرا.ممنون میشم یک نمونه توضیح بدید

سلام

اصل استقرای ریاضی روشی مفیدی اغلب در اثبات یک گزاره ی ریاضی می باشد که به عنوان منبع درسی برای یادگیری می توونی به کتب گسسته مراجعه کنی. البته من اینجا یه توضیحاتی می دهم و امیدوارم مفید باشه:

- اصل استقرای ریاضی:
فرض کنید [tex]S(n)[/tex] یک گزاره ی باز (open statemet) یا مجموعه ای از این نوع گزاره های باز باشد که شامل یک یا چند مورد از متغیر n که عدد صحیح مثبتی است می باشد:
هر گاه الف) [tex]S(1)[/tex] راست بوده (گام پایه) و ب) هر گاه [tex]S(k)[/tex] به ازای هر مقدار دلخواه [tex]k\in Z^ [/tex] راست فرض کنیم، [tex]S(k 1)[/tex] نیز راست باشد (گام استقرا)، آنگاه [tex]S(n)[/tex] به ازای همه [tex]n\in Z^ [/tex] راست خواهد بود.
البته در گام پایه ضرورتی ندارد که پایه از ۱ شروع شود و آنچه لازم است این است که گزاره ی باز [tex]S(n)[/tex] به ازای عنصر اولیه ای مثل [tex]n_0\in Z^ [/tex] راست باشد تا نقطه شروعی برای استقرا باشد.

برای درک شهودی و بهتر اعتبار این روش اثبات، مهره های دومینو رو در نظر بگیر که چطور وقتی یک مهره هل داده می شود بقیه مهره ها نیز به دنبال آن و یکی یکی به مهره بعدی برخورد می کنند و همه به زمین می افتند. روش اثبات با استقرا هم دقیقاً مثل دومینو می باشد و گام پایه مثل همان هل دادن اولین مهره است که فرآیند اثبات (زمین خوردن های مهره های دومینو) را شروع می کند و گام استقرا هم مثل برخورد هر مهره به مهره بعدی خود می باشد، یعنی اگر مهره ای بیافتید ([tex]S(k)[/tex] را راست فرض کنیم) مهره ی بعدی نیز می افتد ([tex]S(k 1)[/tex] نیز راست باشد) و بنابراین اثبات برای همه مقادیر صورت گرفته است (همه مهره های در نهایت یکی یکی به زمین می افتند).