مفیدترین پستها به نظر کاربران در این تاپیک را در اینجا ببینید!

+ پاسخ به مبحث
نمایش نتایج 1 تا 7 از 7

مبحث: استقرا

  1. #1
    مدیر بازنشسته
    39,161 امتیاز ، سطح 48
    39% کامل شده  امتیاز لازم برای سطع بعدی 989
    0% فعالیت
    دستاورد ها:
    SocialRecommendation First ClassCreated Album picturesVeteranTagger First Class
    نماد soroush_tayyebi
    تاريخ عضويت
    Jan 1970
    محل سکونت
    Tehran
    پست
    1,294
    گيپا
    640,650
    پس انداز
    0
    امتیاز
    39,161
    سطح
    48
    تشكرها
    2,568
    716 بار در 433 پست از اين كاربر تشكر شده


    تعداد 1 نفر از 1 کاربر این پست را مفید دانسته اند! به نظر شما این پست مفید است؟ بله | خیر

    پیش فرض استقرا

    آگهی تبلیغات (برای حمایت از گیگاپارس)
    مقدمه

    برای درک مفهوم استقرا به مراحل اثبات یکی از برابری‌های ساده در ریاضیات توجه کنید:
    مجموع اعداد طبیعی زیر را در نظر بگیرید:










    اگر به طور که بخواهیم را بدست بیاوریم یک راه این است که الگویی از مجموع اعداد بالا بدست آورده و سعی در اثبات آن نمائیم.










    و به این ترتیب الگوی را برای مجموعة فوق در نظر می‌گیریم.
    این الگو در حقیقت یک گزاره بر روی
    اعداد طبیعی می‌باشد که می‌توان آن را با به معنی نمایش داد.
    اگر چه اثبات این الگو به طور مستقیم و بدون کمک به استقرا به سادگی ممکن می‌باشد ولی در حل مسائل ریاضی به دفعات به حدس‌هایی برمی‌خوریم که اثبات آنها می‌تواند مشکل باشد در ایدة استقرا یکی از زیباترین ایده‌های موجود برای کمک به ما می‌باشد.
    برای آنکه بیشتر آمادگی ذهنی برای درک استقرا پیدا کنیم به همان مثال مجموع اعداد 1 تا می‌رویم، و می‌خواهیم گزارة را که گزاره‌ای دربارة عدد می‌باشد ثابت کنیم.
    در ایدة استقرا که جلوتر به تعریف دقیق آن می‌پردازیم نخست باید برای های کوچک درستی را نشان دهیم مانند:




    حال می‌دانیم لااقل برای تعدادی از ابتدای اعداد طبیعی درست است. اکنون با فرض آنکه برایحکم درست باشد، درستیرا نتیجه می‌گیریم (دقت کنید درستی را فرض می‌کنیم.



    خوب حال شما بگوئید ما برای چند عدد طبیعی کوچکترین درستیرا ثابت کرده و با فرض درستی درستی را ثابت کردیم، با این حساب آیا می‌توان گفت که برای تمامی اعداد طبیعی برقرار است؟ !
    به موضوع بالا فکر کنید چون اگر چه بعداً توضیح داده می‌شود ولی اگر اکنون آن را برای خود تجزیه و تحلیل کنید برای درک مطالب آینده راحت‌تر خواهید بود.

    چند نماد پرکاربرد

    نماد مجموع : از این جا به بعد با مجموع پشت سرهم دنباله‌ای از اعداد سروکار خواهیم داشت. برای نشان دادن مجموع از نماد استفاده می‌کنیم، و این نماد یعنی [تنها کاربرانی که عضو شده اند و از طریق ایمیل عضویتشان فعال شده می تواند این لینک را ببینند. ] از حداقل مقدار 1 شروع شده و تا حداکثر می‌رود و حاصل تمام مقادیر با هم جمع می‌شود. به طور کلی چند نمونه پرکاربرد:
    به جای
    به جای
    به جای
    و به همین ترتیب …
    و به طور کلی
    از به جای
    استفاده می‌شود.
    دقت کنید در نماد که آن را سیگما بخوانید سه قسمت مهم وجود دارد که در شکل قبل نشان داده شده است.

    قضیه .

    می‌توان سیگمای مجموع دو تابع یعنی را به صورت مجموع دو سیگما هر یک از توابع یعنی نوشت.

    قضیه .

    که k عددی ثابت است.
    دو قضیه بالا به راحتی قابل اثبات بوده و از اثبات آنها صرف‌نظر می‌کنیم.

    نماد حاصل‌ضرب

    به طریق مشابه برای حاصل‌ضرب داریم:


    به عنوان نمونه:
    به جای
    به جای .
    BYE 4 EVER

  2. 3 نفر از soroush_tayyebi برای این مطلب مفید تشکر کرده اند:


  3. #2
    مدیر بازنشسته
    39,161 امتیاز ، سطح 48
    39% کامل شده  امتیاز لازم برای سطع بعدی 989
    0% فعالیت
    دستاورد ها:
    SocialRecommendation First ClassCreated Album picturesVeteranTagger First Class
    نماد soroush_tayyebi
    تاريخ عضويت
    Jan 1970
    محل سکونت
    Tehran
    پست
    1,294
    گيپا
    640,650
    پس انداز
    0
    امتیاز
    39,161
    سطح
    48
    تشكرها
    2,568
    716 بار در 433 پست از اين كاربر تشكر شده


    به نظر شما این پست مفید است؟ بله | خیر

    پیش فرض اصل استقرای ریاضی:

    این اصل بیان میکند اگر S زیرمجموعه ای ناتهی از اعداد طبیعی باشد به طوری که:
    1) عدد یک عضو این مجموعه باشد.
    2) هرگاه عدد طبیعی n در مجموعه S باشد آنگاه n+1 نیز عضو این مجموعه باشد.
    میتوان تنیجه گرفت هر عدد طبیعی عضو S است و به عبارت دیگر S همان مجموعه اعداد طبیعی است.



    • لازم به توضیح است این اصل با پذیرش [تنها کاربرانی که عضو شده اند و از طریق ایمیل عضویتشان فعال شده می تواند این لینک را ببینند. ] قابل اثبات است.
    برهان:

    برای اثبات از برهان خلف کمک می گیریم. به برهان خلف فرض می کنیم با مفروضات فوق مجموعه S برابر مجموعه اعداد طبیعی نباشد. پس مجموعه ای چون T وجود دارد که S=N-T. حال داریم: مجموعه T زیر مجموعه اعداد طبیعی است و ناتهی است(چرا؟) پس بنا بر اصل خوشترتیبی T دارا عضو مینیمم است چون واضح است که و چون پس داریم: و چون برابر مینیمم مجموعه T است پس و لذا از شرط دوم مجموعه S داریم:
    که این تناقض است چون پس فرض خلف باطل و حکم(اصل اسقرا) برقرار است.



    • به این ترتیب برای اثبات برخی از مسائل و احکام ریاضی که درباره اعداد طبیعی می باشند می توان از اصل استقرای ریاضی استفاده کرد که اثبات به این روش، یک روش مستقیم در استدلال ریاضی است.
    صورتی دیگر از اصل استقرای ریاضی:(اثبات به کمک اصل استقرای ریاضی)

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

    اگر (P(n حکمی در مورداعداد طبیعی باشد (P(n برای هر عدد طبیعی n درست است اگر و فقط اگر:
    1- حکم (P(1 درست باشد. به عبارت دیگر حکم برای n=1 برقرار باشد. (این مرحله را مرحله مبنای استقرا می گوییم.)
    2- به ازای هر عدد طبیعی k از فرض درستی (P(k (فرض استقرا) بتوان درستی (P(k+1 (حکم استقرا) را نتیجه گرفت.


    به عبارت دیگر نشان می دهیم عدد 1 در دامنه حکم است و چون هر k طبیعی که در دامنه حکم باشد k+1 هم در دامنه است می توان گفت دامنه حکم هر عدد طبیعی است و هر عدد طبیعی در حکم صدق می کند.
    • لازم به توضیح است که در اثبات به کمک اصل استقرا هر یک دو شرط فوق باید برقرار باشد تا بتوان درستی حکم را نتیجه گرفت.
    مثال: نشان دهید برای هر عدد طبیعی n:

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

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

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

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


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

    اصل استقراء تعمیم یافــته:
    گاهی ممکن است با احکامی روبه رو شویم که برای n=1 برقرار نمی باشند و باید در بررسی شرط اول (مرحله مبنا) از عددی طبیعی بزرگتر استفاده کنیم به این ترتیب از اصل استقراء تعمیم یافــته استفاده می کنیم.


    اصل استقرای تعمیم یافته:
    اگر (P(nحکمی در باره اعداد طبیعی n (یا صحیح) باشد در صورتی که:
    1- برای هر عدد طبیعی P(m) ، m>1 درست باشد
    2- به ازای هر عدد طبیعی ، از درستی (P(k درستی (P(k+1 نتیجه شود
    آنگاه میتوان گفت حکم (P(n برای هر عدد طبیعی برقرار است.


    • به این ترتیب در اثبات مسائل به کمک اصل استقرای تعمیم یافته باید m مناسب را برای بررسی شرط اول بیابیم.
    مثال: نشان دهید عدد طبیعی مناسبی مانند m وجود دارد که برای هر عدد طبیعی n بزرگتر یا مساوی m داریـم:

    پاسخ: با قرار دادن مقادیر طبیعی برای m متوجه می شویم که m مناسب 3 است چرا که برای اولین بار حکم برای m=3 درست است. حال نشان میدهیم حکم برای هر عدد طبیعی برقرار است.
    1-
    2- اکنون در این مرحله فرض (فرض استقرا) می کنیم نامساوی فوق برای هر عدد طبیعی درست باشد یعنی:
    نشان میدهیم حکم داده شده برای (n=k+1 ،(k>2 درست است، یعنی:
    (حکم استقرا)
    برای این منظور از فرض استقرا استفاده کرده و به طرفین فرض عدد 2 را اضافه می کنیم، داریم:

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

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


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

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

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

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

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


    (k-1)+تعداد قطرهای k ضلعی محدب=تعداد قطرهای k+1 ضلعی محدب

    بنابراین رابطه زیر برقرار است:

    تعداد قطرهای k+1 ضلعی محدب



    و لذا حکم برای هر n>3 برقرار است.

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

    اصل استقرای قوی ریاضی:
    اگر S زیرمجموعه ای از اعداد طبیعی باشد، به طوری که:
    1- عدد یک عضوی از مجموعه S باشد.
    2- اگر اعداد طبیعی کوچکتر از n در مجموعه S باشند، آنگاه n نیز عضو S باشد
    در این صورت هر عدد طبیعی عضوی از S است و به عبارت دیگر S همان مجموعه اعداد طبیعی است.


    • لازم به تذکر است در ریاضیات برای اثبات احکام طبیعی بیشتر از اصل استقرای قوی ریاضی استفاده میشود.
    روش اثبات احکام بوسیله اصل استقرای قوی ریاضی:

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


    با یک مثال روش اثبات را بررسی می کنیم:

    دنباله به
    دنباله لوکا معروف است که در بین جملات آن رابطه بازگشتی زیر برقرار است:


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


    پاسخ: اگر


    آنگاه 1و2 عضوی از S می باشند زیرا نامساویهای:


    درست می باشند.(مرحله مبنا)
    حال فرض میکنیم (فرض استقرا) و به ازای هر عدد طبیعی k که k، k<n در مجموعه S قرار دارد. بنابراین:


    لذا چون پس:




    و از طرفی دیگر:


    و لــذا:


    یعنی n نیز در مجموعه S قرار دارد، پس مجموعه S همان مجموعه اعداد طبیعی است. و لذا برای هر عدد طبیعی n حکم برقرار است.

    • لازم به توضیح است که از این اصل هم می توان برای اثبات برخی قضایای هندسه استفاده کرد و در ضمن می توان احکامی طبیعی که از یک هم آغاز نمی شوند را به این وسیله اثبات نمود.
    مثال: نشان دهید مجموع زوایای هر n ضلعی محدب برابر است با:
    پاسخ: می دانیم در این سوال n>2 زیرا n ضلعی حداقل از سه ضلع بوجود می آید.
    به این ترتیب در مرحله مبنا حکم را برای n=3 بررسی می کنیم:


    که همان گونه که می دانیم در هندسه نشان داده شده است که مجموع زوایای داخلی هر سه ضلعی محدب(مثلث) برابر می باشد.
    اکنون فرض می کنیم (فرض استقرا) که مجموع زاویه های داخلی هر k ضلعی محدب که k<n برابر:
    باشد.
    اکنون نشان می دهیم (حکم استقرا) که مجموع زاویه های داخلی هر n ضلعی محدب نیز برابر:
    است.
    برای این منظور n ضلعی را در نظر می گیریم. قطر را رسم می کنیم تا n ضلعی به یک k ضلعی: و یک (n-k+2) ضلعی تقسیم شود. مطابق فرض استقرا، مجموع زاویه های داخلی k ضلعی و (n-k+2) ضلعی به ترتیب برابر است با:

    و

    بنابراین مجموع زاویه های داخلی n ضلعی برابر است با:


    و لذا حکم برقرار است.

    مزیت و محدودیت استدلال به کمک استقرای ریاضی:

    استدلال به کمک استقرای ریاضی یک روش مستقیم برای اثبات و حل مسایل ریاضی محسوب می شود. این روش هم امتیازاتی دارد و هم محدودیت هایی. از مزایای استقرای ریاضی، مرحله ای بودن این روش است. یعنی عموما بدون نیاز به ابتکارهای زاید، مفید است و لذا شخص نتها لازوم دارد که برای استدلال خود، از مراحل مشخصی پیروی کند و برای این کار به بینش خاص نیاز نیست. مزیت دیگر این روش این است که استقرای ریاضی در حل مسایل خاصی که در آنها سایر روشهای عملی نیستند و یا بسیار مشکل اند، مفید است.
    اما محدودیت استقرای ریاضی در این است که فقط برای مسائلی به کار می رود که با اعداد طبیعی سروکار دارند. لذا این روش اساسا یک روش تحقیق است، و تنها در اثبات نتایجی که درستی آنها را معلوم کرده یا حدس زده ایم، به کار می رود.
    BYE 4 EVER

  4. #3
    مدیر بازنشسته
    39,161 امتیاز ، سطح 48
    39% کامل شده  امتیاز لازم برای سطع بعدی 989
    0% فعالیت
    دستاورد ها:
    SocialRecommendation First ClassCreated Album picturesVeteranTagger First Class
    نماد soroush_tayyebi
    تاريخ عضويت
    Jan 1970
    محل سکونت
    Tehran
    پست
    1,294
    گيپا
    640,650
    پس انداز
    0
    امتیاز
    39,161
    سطح
    48
    تشكرها
    2,568
    716 بار در 433 پست از اين كاربر تشكر شده


    به نظر شما این پست مفید است؟ بله | خیر

    پیش فرض تعمیم اولیه اصل استقرا i

    تعمیم اولیه اصل استقرا

    استقرای ضعیف

    اصل استقرای ریاضی ضعیف :
    اگر یک عدد صحیح و یک جمله بر اساس پارامتر باشد، به طوری که:
    الف. برقرار باشد.
    ب. به ازای هر ، .
    در این صورت، به ازای هر ، برقرار است.
    اثبات .
    فرض کنید که چنین نباشد، یعنی حکم برای برخی مقادیر صحیح صحیح نباشد. در این صورت طبق اصل خوش ترتیبی، عددی مثل p وجود دارد به طوری که:
    1.حکم به ازای برقرار نباشد.
    2.برای تمام مقادیر ، حکم برقرار باشد.
    به عبارت دیگر اولین [تنها کاربرانی که عضو شده اند و از طریق ایمیل عضویتشان فعال شده می تواند این لینک را ببینند. ] بزرگ تر یا مساوی باشد که به ازای آن، حکم مفروض نیست.
    واضح است که است، زیرا به ازای طبق شرط الف، حکم صحیح است. بنابراین یک عدد صحیح بزرگ تر یا مساوی است. از اینجا نتیجه می شود که برای عدد صحیح بعد از آن برقرار نیست و این با فرض ب، متناقض است.
    را پایه استقرا و را فرض استقرا و را حکم استقرا می گوییم. بنابراین برای اثبات یک مساله با استقرا، ابتدا باید درستی پایه استقرا را ثابت کنیم. سپس، با فرض درستی فرض استقرا، درستی حکم استقرا را نتیجه بگیریم. اگر هر کدام از دو گام فوق را انجام ندهیم، مساله ما ثابت نمی شود.



    حال بهتر است به بررسی چند مثال بپردازیم.

    چند مثال

    مثال1

    به ازای هر، ثابت کنید:


    حل
    قدم اول در استفاده از استقرا بررسی درستی پایه ی استقرا است. پس باید بررسی کنیم که آیا ؟ می بینیم که پایه ی استقرا برقرار است.
    قدم دوم باید فرض کنید که درست است یعنی:


    و از درستی آن، درستی را نتیجه بگیریم؛ یعنی:


    طبق فرض استقرا داریم:


    بنابراین، با اضافه کردن به طرفین تساوی داریم:


    پس اثبات مساله کامل شد.



    مثال2

    نامساوی برنولی : به ازای هر عدد صحیح و هر عدد حقیقی ثابت کنید:


    حل
    برقراری پایه ی استقرا :

    یا

    طبق فرض استقرا داریم:


    حال با توجه به این که داریم:


    پس حکم استقرا ثابت شد و اثبات به پایان می رسد.
    دقت کنید که اگر شرط را نداشتیم، نمی توانستیم طرفین را در ضرب کنیم و علامت نامساوی تغییر نکند. به این مسایل دقت داشته باشید، چون می تواند باعث خطا در اثبات شود؛ به خطاهای استقرا در بخش های بعدی خواهیم پرداخت.



    مثال3

    فرض کنید تیم در یک تورنمنت (هر تیم با هر یک از تیم دیگر دقیقاً یک بار بازی کرده است) با یکدیگر بازی کرده اند. اگر هیچ دو تیمی مساوی نکرده باشند ثابت کنید دنباله از تیم ها وجود دارد به طوری که، تیم از تیم برده، تیم از تیم برده، ... و تیم از تیم برده است.


    به عنوان مثال شکل بالا یک تورنمنت 5 رأسی را نشان می دهد که در آن تیم 5 از تیم 3، تیم 3 از تیم 4، تیم 4 از تیم 2 و تیم 2 از تیم 1 برده است.
    حل
    پایه ی استقرا : در یک تورنمنت تیمی، دنباله ی (تنها تیم شرکت کننده) جواب است.


    حال فرض کنید برای هر تورنمنت با تیم، چنین دنباله ای وجود دارد. می خواهیم ثابت کنیم برای هر تورنمنت تیمی نیز، چنین دنباله ای وجود دارد. یکی از تیم مثلاً تیم را در نظر نگیرید. با در نظر گرفتن بازی بین تیم باقی مانده، ما یک تورنمنت تیمی داریم و طبق فرض استقرا، دنباله ی از این تیم وجود دارد که تیم از تیم برده است.


    اگر تیم به تیم باخته باشد، دنباله ی جواب مساله است. همچنین اگر تیم تیم را برده باشد، دنباله ی جواب مساله است. در غیر این حالات فرض کنید تیم اولین تیمی (کوچک ترین ای) باشد که به باخته است. چنین تیمی وجود دارد زیرا تیم حداقل یک برد از تیم دارد. پس تیم، را برده و تیم هم را برده است. پس دنباله ی جواب مساله است.



    مثال4

    عدد مثبت و متمایز مفروض اند. اگر باشد. ثابت کنید از بین مقداری که، می تواند بگیرد، حداقل عدد متمایز پیدا می شود.
    حل
    بدون این که به کلیت مساله لطمه بخورد فرض کنید. با استقرا روی ثابت می کنیم که لااقل تعداد از جملات فوق متمایز هستند.
    برای پایه ی استقرا که حکم برقرار است. دو جمله ی مورد نظر است.
    حال حکم را به ازای درست فرض کنید؛ می خواهیم درستی آن را به ازای اثبات کنیم. با اعداد ، حداقل جمله ی متمایز ساخته می شود. باید جمله ی دیگر بسازیم. این جمله را به روش زیر می سازیم.
    فرض کنید. (در نتیجه بزرگتر یا مساوی تمام جملات قبلی است.) حال ادعا می کنیم که


    جمله ی متمایز هستند و هر کدام از سایر جملات قبلی بزرگتر می باشد زیرا اگر یکی از جمله ی ساخته شده ی قبلی باشد، ولی می باشد. پس حکم اثبات شد.


    مثال5

    در یک مدرسه دبیر تدریس می کنند. این دبیرها را با شماره های 1 تا شماره گذاری می کنیم. می دانیم که دبیر ام، نفر از دانش آموزان را می شناسد. هر دانش آموز می تواند توسط بیش از یک دبیر شناخته شود. هر یک از این دبیرها می خواهد یکی از دانش آموزانی را که می شناسد به عنوان نماینده ی خود برگزیند به شرط این که هیچ دانش آموزی به عنوان نماینده ی بیش از یک دبیر انتخاب نشود. ثابت کنید که انتخاب این نماینده ها حداقل به حالت مختلف امکان پذیر است.
    حل
    باز مساله را با استقرا روی تعداد دبیرها حل می کنیم. برای ، حکم بدیهی است. اگر برای دبیر، حداقل حالت وجود داشته باشد، می خواهیم ثابت کنیم برای دبیر هم، حداقل حالت وجود دارد. طبق فرض استقرا دبیرهای اول تا ام به طریق می توانند نماینده های خود را انتخاب کنند؛ و چون دبیر ام حداقل نفر را می شناسد که حداکثر نفر از آنها قبلاً به عنوان نماینده انتخاب شده اند، پس دبیر ام - در هر کدام از حالت- حداقل به 2 طریق می تواند نماینده ی خود را انتخاب کند. بنابراین دبیر حداقل به طریق می توانند نماینده های خود را انتخاب کنند.



    مثال6

    ثابت کنید برای هر عدد طبیعی می توان دایره به شعاع واحد را درون یک دایره به شعاع جا داد به طوری که هیچ دو دایره ای متقاطع نباشند (هر دو دایره حداکثر در یک نقطه می توانند با هم اشتراک داشته باشند).
    حل
    با استقرا روی ثابت می کنیم که دایره به شعاع واحد را می توان درون یک دایره به شعاع جا داد. برای ، دایره ها را به صورتی که در شکل نشان داده شده است قرار می دهیم.


    حال فرض کنید که حکم برای درست باشد، می خواهیم حکم را برای ثابت کنیم. ابتدا درون دایره ای به شعاع، مانند حالت ، 7 دایره به شعاع رسم می کنیم. حال طبق فرض استقرا می توان دورن هر یک از این 7 دایره، دایره به شعاع واحد رسم کرد. چون هیچ کدام از 7 دایره ی به شعاع، بیش از یک نقطه ی تلاقی ندارند، بنابراین توانستیم درون یک دایره به شعاع ، دایره به شعاع واحد رسم کنیم که هیچ دو [تنها کاربرانی که عضو شده اند و از طریق ایمیل عضویتشان فعال شده می تواند این لینک را ببینند. ] ای در بیش از یک نقطه با یکدیگر تقاطع نداشته باشند. پس حکم ثابت شد.



    مثال7

    و دو مجموعه ی متناهی و جدا از هم از عددهای صحیح هستند به طوری که برای هر، یا است. ثابت کنید که تعداد عناصر مجموعه ی دو برابر تعداد عناصر مجموعه ی است.
    حل
    از استقرا روی تعداد عناصر استفاده می کنیم. اگر تعداد عناصر صفر باشد، یعنی تهی باشد، نشان می دهیم که نیز تهی است. چون برای هر عنصر، نیز می باشد، در نتیجه طبق فرض مسئله باید باشد. بنابراین اگر تهی نباشد، باید نامتناهی باشد و این برخلاف فرض مساله است.
    حالا فرض کنید که مسئله برای ثابت شده باشد، حال آن را برای ثابت می کنیم. برای این منظور کوچک ترین عضو را در نظر گرفته و آن را می نامیم. چون کوچک ترین عضو است، پس ؛ در نتیجه است. در نتیجه چون و (زیرا کوچک ترین عصو است). بنابراین. چون مجموعه های و جدا از هم می باشند، بنابراین و .
    حال مجموعه های و را در نظر بگیرید. به ازای هر، داریم یا. زیرا اگر باشد، آن گاه است و طبق فرض مساله یا می باشد. اگر مثلاً باشد، با توجه به این که (چرا؟)، پس. به طریق مشابه اگر باشد، با توجه به این که، پس باید باشد. از طرف دیگر واضح است که چون مجموعه های و جدا از هم می باشند، پس مجموعه های و هم جدا از هم می باشند. پس مجموعه های و دارای شرایط مساله هستند و، پس طبق فرض استقرا. ولی و پس.



    مثال8

    تعداد دیسک داریم که روی هر کدام، یکی از عددهای 1 تا نوشته شده است. میله با شماره های صفر تا در یک ردیف پشت سر هم قرار گرفته اند. در ابتدا، دیسک ها با یک ترتیب داده شده در میله ی صفر روی هم قرار دارند. در هر حرکت می توان بالاترین دیسک موجود روی میله ی را برداشته و روی میله ی ام قرار داد. این حرکت را با نمایش می دهیم. حالت نهایی مرتب، حالتی است که در آن تمام دیسک ها به ترتیب از شماره ی 1 تا (پایین به بالا) روی میله ی شماره ی ام قرار گرفته باشند. برای مثال، به ازای ، حرکت های لازم برای رسیدن به حالت نهایی مرتب از حالت اولیه ای به شکل زیر می تواند به صورت باشد.
    ثابت کنید به ازای هر می توان از هر ترتیب اولیه ی دیسک ها روی میله ی شماره ی صفر به یک حالت نهایی مرتب رسید.
    حل
    اگر باشد که حکم بدیهی است. حال فرض کنید مسئله برای حل شده باشد؛ درستی آن را برای ثابت می کنیم. حالمیله و مهره داریم. اگر مهره های شماره ی تا وجود نداشتند، می توانستیم مهره های شماره ی 1 تا را بدون استفاده از میله ی شماره ی 1 به میله ی شماره منتقل کنیم. ولی این مشکل را می توان به این صورت حل کرد که هر گاه نوبت حرکت یک مهره با شماره ی 1 تا شد و مهره یا مهره هایی با شماره ی تا بالاتر از آن روی میله ی شماره ی صفر قرار داشت، آن مهره ها را به میله ی شماره ی یک منتقل می کنیم و بعد حرکت مورد نظر را انجام می دهیم. توجه کنید که در حرکات مورد نظر، حرکت به حرکت و حرکت به حرکت های لازم برای [تنها کاربرانی که عضو شده اند و از طریق ایمیل عضویتشان فعال شده می تواند این لینک را ببینند. ] مهره های با شماره ی تا و سپس حرکت به تبدیل شده است.


    حال مهره های با شماره ی 1 تا با ترتیب پایین به بالا روی میله ی شماره ی قرار گرفته اند. حال دیسک با شماره های تا راکه روی میله ی شماره ی یک قرار گرفته اند، طبق فرض استقرا به میله ی شماره ی منتقل می کنیم. بنابراین دیسک ها از شماره ی 1 تا به ترتیب ( از پایین به بالا) روی میله ی شماره ی قرار گرفته اند و حکم ثابت شد.
    BYE 4 EVER

  5. #4
    مدیر بازنشسته
    39,161 امتیاز ، سطح 48
    39% کامل شده  امتیاز لازم برای سطع بعدی 989
    0% فعالیت
    دستاورد ها:
    SocialRecommendation First ClassCreated Album picturesVeteranTagger First Class
    نماد soroush_tayyebi
    تاريخ عضويت
    Jan 1970
    محل سکونت
    Tehran
    پست
    1,294
    گيپا
    640,650
    پس انداز
    0
    امتیاز
    39,161
    سطح
    48
    تشكرها
    2,568
    716 بار در 433 پست از اين كاربر تشكر شده


    به نظر شما این پست مفید است؟ بله | خیر

    پیش فرض تعمیم اولیه اصل استقرا ii

    استقرای چند پایه

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




    چند مثال

    مثال1

    فرض کنید دنباله ای از اعداد حقیقی ناصفر باشند که در رابطه ی زیر صدق می کنند:


    شرط لازم و کافی- روی و- برای این که به ازای تعداد نامتناهی مقدار، صحیح باشد را به دست آورید.
    حل
    بهتر است برای فهمیدن مساله چند جمله ی اول این دنباله را- بر اساس و- محاسبه کنیم؛ شاید بتوانیم یک الگوی کلی برای جمله ی عمومی این [تنها کاربرانی که عضو شده اند و از طریق ایمیل عضویتشان فعال شده می تواند این لینک را ببینند. ]- بر اساس و- به دست آوریم.
    برای چند جمله ی اول این دنباله داریم:











    اگر خوب به جملات بالا نگاه کنیم می توانیم یک الگوی کلی حدس بزنیم و آن به این صورت است که


    یا به عبارت دیگر:


    حال اگر بتوانیم فرمول بالا را اثبات کیم، می بینیم که اگر باشد به ازای های بزرگ قدر مطلق مخرج از صورت بیشتر می شود (چرا؟) و لذا نمی تواند صحیح باشد. در نتیجه شرط لازم برای این که تعداد نامتناهی جمله از دنباله ی صحیح باشند این است که . حال اگر باشد، آن گاه کلیه ی جملات دنباله ی فوق برابر می شوند؛ بنابراین شرط لازم و کافی این است که.
    حال بیایید با هم فرمولرا ثابت کنیم.
    حکم به ازایبرقرار است. حال فرض کنید حکم به ازای وبرقرار باشد، می خواهیم درستی حکم را به ازای ثابت کنیم:





    پس حکم با استقرای چند پایه روی ثابت شد.


    مثال2

    در دو انتهای قطری از [تنها کاربرانی که عضو شده اند و از طریق ایمیل عضویتشان فعال شده می تواند این لینک را ببینند. ]، عددهای 1 را قرار داده ایم. هر یک از نیم دایره های حاصل را نصف کرده ایم و در وسط کمان هر نیم دایره، مجموع دو عددی که در دو انتهای آن وجود دارند قرار داده ایم (مرحله ی اول). در مرحله ی بعدی باز هر یک از چهار کمان حاصل را نصف کرده و در نقطه ی وسط آنها، مجموع دو عددی را که در دو انتهای آن ها است، قرار داده ایم (مرحله ی دوم). این عمل را n بار ادامه داده ایم. در پایان مرحله ی ام مجموع همه ی عددهایی را پیدا کنید که روی محیط دایره نوشته ایم.


    حل
    باز مجموع اعداد را در چند گام اول حساب می کنیم و سعی می کنیم یک رابطه برای آن حدس بزنیم.
    همان طور که در شکل بالا می بینید مجموع اعداد دور دایره در مرحله ی ام احتمالاً باید برابر با باشد. حال بیایید حدس خود را ثابت کنیم.
    حکم به ازای برقرار است. حال فرض کنید که مجموع اعداد در گام n ام برابر با باشد. در مرحله ام، مجموع اعدادی که تازه روی محیط دایره نوشته می شوند برابر است با (چرا؟). مجموع اعداد قبلی نیز برابر با می باشد. بنابراین مجموع اعداد در گام ام برابر است با


    در نتیجه حکم با استقرا روی مراحل ثابت شد.



    مثال3

    مجموع اعداد سطر ام مثلث زیر را بیابید.


    حل
    با پیدا کردن مجموع اعداد چند سطر اول، حدس می زنیم که مجموع اعداد سطر ام برابر با باشد. می خواهیم این مسئله را اثبات کنیم، ولی نمی دانیم که چه اعدادی در سطر ام قرار دارند. پس چه کار کنیم؟
    پس بیایید ببینیم که مجموع اعداد سطر ام با مجموع اعداد سطر ام چقدر اختلاف دارد؟ اگر حدس ما درست باشد باید این اختلاف به اندازه ی باشد. ببینیم آیا می توانیم این اختلاف را بشماریم؟ می دانیم که تعداد اعداد سطر ام، یکی بیشتر از اعداد سطر ام است و اختلاف عدد امسطر ام با عدد ام سطر ام برابر است. زیرا عدد ام سطر ام، امین عدد فرد بعد از عدد ام سطر ام است و اختلاف هر دو عدد فرد متوالی، برابر 2 است.
    پس اگر آخرین عدد سطر ام برابر باشد آنگاه، اختلاف مجموع اعداد سطر ام و مجموع اعداد سطر ام برابر است. پس اگر حدس ما درست باشد باید داشته باشیم. بنابراین حدس می زنیم که آخرین عدد سطر ام برابر باشد. حال سعی می کنیم که حدس خود را با [تنها کاربرانی که عضو شده اند و از طریق ایمیل عضویتشان فعال شده می تواند این لینک را ببینند. ] روی ثابت کنیم.



    لم

    آخرین سطر ام مثلث فوق برابر است با .
    اثبات لم
    به ازای که حکم واضح است. حال فرض کنید آخرین عدد سطر ام برابر است با (فرض استقرا). می خواهیم ثابت کنیم که آخرین عدد سطر ام برابر است با (حکم استقرا).
    می دانیم بین آخرین عدد سطر ام و آخرین عدد سطر ام، دقیقا عدد فرد دیگر وجود دارد. یا به عبارت دیگر آخرین عدد سطر ام، امین عدد فرد بعد از آخرین عدد سطر ام است. پس اختلاف آخرین عدد سطر ام با آخرین عدد سطر ام برابر است با . درنتیجه آخرین عدد سطر ام برابر است با . در نتیجه لم ثابت شد. با توجه به لم بالا و مطالبی که در بالا گفته شد با استقرا روی به راحتی ثابت می شود که مجموع اعداد سطر ام برابر است با .

    چند مثال

    مثال1

    برای عددهای می دانیم:


    ثابت کنید در مجموع می توان علامت ها را طوری تعیین کرد که داشته باشیم .


    حل
    بیایید باز حکم را با استقرا ثابت کنیم. به ازایکه حکم واضح است. حال برای عدد حکم را درست فرض کنید یعنی فرض کنید بتوانیم در عبارت




    جدول 4.3: طی کردن صفحات شطرنجیوبا حرکت اسب

    علامت های مثبت و منفی را طوری انتخاب کنیم که باشد.
    می خواهیم ثابت کنیم در عبارت


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





    پس با توجه به این که می باشد. براساس این که مقدار در کدام یک از دو محدوده ی یا باشد، می توان عبارت را طوری علامت گذاری کرد که باشد.



    مثال2

    ثابت کنید اسب بازی شطرنج را روی صفحه ی شطرنجی می توان طوری حرکت داد که در همه ی خانه ها، و در ضمن در هر کدام، تنها یک بار قرار گیرد.
    حل
    در مسایلی مثل مساله ی فوق که مسئله به صورت پارامتری داده نشده است ما باید حدس بزنیم که مساله برای چه پارامترهایی درست است که 2001 هم یکی از آنها باشد. به عبارت دیگر باید رابطه ی بین هایی را پیدا کنیم که مسئله برای آنها درست است و 2001 هم در آن رابطه صدق می کند؛ سپس با استفاده از استقرا درستی آن مسئله را برای آن ها ثابت کنیم. اگر این کار ار انجام دهیم مسئله برای آن عدد خاص هم ثابت شده است.
    پس ابتدا درستی حکم را برای صفحات شطرنجی ، وقتی کوچک باشد امتحان می کنیم. می بینیم که حکم به ازایدرست است. در جدول 3.4 حرکت اسب در صفحات شطرنجی ونشان داده شده است (اسب از خانه ی شماره ی 1 شروع می کند و از خانه ی شماره ی به خانه ی شماره یمی رود).
    پس توانستیم نشان دهیم که حکم به ازای درست است. بنابراین احتمالاً باید حکم به ازای درست باشد. همان طور که در دو مثال نشان داده شده است اسب از وسط صفحه شطرنجی حرکت خود را آغاز کرده است و در خانه ی گوشه ی بالا سمت راست حرکت خود را به پایان رسانده است. همچنین حرکت اسب تا حد امکان در جهت حرکت عقربه های ساعت می باشد. پس سعی می کنیم برای n بزرگتر هم از این قوانین پیروی کنیم.
    پایه ی استقرا به ازای درست است. فرض کنید اسب بتواند با شروع از مرکز یک صفحه ی شطرنجی از تمام خانه ها یک و فقط یک بار عبور کند و خود را به خانه ی گوشه ی بالای سمت راست، برساند. می خواهیم ثابت کنیم می تواند در صفحه ی شطرنجی نیز این کار را انجام دهد.
    ابتدا اسب صفحه ی شطرنجی وسطی را طبق فرض استقرا پیمایش می کند. حالا در خانه یقرار دارد و فقط ستون های و سطرهای طی نشده اند. حال برای طی کردن خانه های باقی مانده از خانه های به ترتیب به خانه های زیر می رویم (در جهت عقربه های ساعت حرکت می کنیم).



    جدول 4.4: طی کردن صفحه ی شطرنجیبا حرکت اسب

















































    واضح است که پیمایش بالا تمام سطر و ستون های باقی مانده را طی می کند و به گوشه ی سمت راست بالای صفحه ی شطرنجی ختم می شود. پس حکم مساله با استقرا روی ثابت شد و چون 2001 را می توان به صورتنوشت، مساله ثابت شد.

    مثال3

    عدد طبیعی دلخواه است. یک ترتیب دلخواه از اعداد 1 تا که در آن هر یک از اعداد 1 تا دقیقاً یک بار آمده باشند را یک [تنها کاربرانی که عضو شده اند و از طریق ایمیل عضویتشان فعال شده می تواند این لینک را ببینند. ] از می نامیم. می گوییم جایگشت در دنباله ی ظاهر شده است، اگر اندیس های وجود داشته باشند به طوری که برای هر داشته باشیم. به عنوان مثال جایگشت 2 , 3 , 1 در دنباله ی 3 , 2 , 3 , 2 , 1 , 3 ظاهر شده است.
    یک دنباله از اعداد 1 تا «دنباله ی جالب» نامیده می شود، اگر هر جایگشت دلخواهی از
    در این دنباله ظاهر شده باشد.
    ثابت کنید برای هر عدد طبیعی حداقل یک دنباله ی جالب به طول وجود دارد.


    حل
    راه حل اول:
    اگر بخواهیم از استقرا استفاده کنیم باید ساختار ساختن دنباله ی جالب برای از ساختار دنباله ی جالب برای به دست آید. بنابراین با این فرض بیایید چند دنباله ی جالب برای
    بسازیم.


    در حالت کلی دنباله ی جالب به طول را برای به این صورت می سازیم. ابتدا یک دنباله ی جالب به طول برایمی سازیم، سپس را به آن اضافه می کنیم و بعد باز یک دنباله ی جالب به طول برای به انتهای آن اضافه می کنیم. به عبارت دیگر اگردنباله ی جالب برای باشد، داریم:
    واضح است که طول این دنباله برابر با می باشد و یک دنباله ی جالب برای می باشد. زیرا اگر یک جایگشت از اعداد 1 تا باشد و باشد، طبق فرض استقرا زیر دنباله ی در دنباله ی جالب سمت چپ برایوجود دارد و باز طبق فرض استقرا زیر دنباله ی در دنباله ی جالب سمت راست برای وجود دارد، بنابراین جایگشت در دنباله ی جالب برای وجود دارد.
    راه حل دوم:
    اگر برای یک دنباله ی جالب ساخته باشیم، برای نیز یک دنباله ی جالب به این شکل می سازیم که در ابتدا و انتها و همچنین بین هر دو عنصر از دنباله ی جالب برای ، عدد را می نویسیم. حال به وضوح دیده می شود که دنباله ی ساخته شده یک دنباله ی جالب برای است و اگر دنباله ی جالب برای به طول باشد، دنباله ی جالب ساخته شده برای، به طول می باشد.


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



    مثال 4

    نفر با شماره های 1 تا دور میزی نشسته اند و هر کدام k مهره در اختیار دارند. با شروع از نفر اول بازی زیر را انجام می دهیم. نفر او مهره ی خود را به نفر دوم می دهد و از این به بعد هر نفر که از نفر قبلی یک مهره دریافت کرده باشد دو مهره به نفر بعدی خود می دهد و اگر دو مهره دریافت کرده باشد، یک مهره به نفر بعدی می دهد. در این بازی منظور از نفر بعدی، نزدیک ترین فرد در جهت عقربه های ساعت است. به محض آن که فردی تمام مهره هایش را از دست بدهد از دور میز کنار می رود. مثلاً اگرباشد، در ابتدای بازی نفر 1 و 2 از دور میز خارج می شوند.
    الف. ثابت کنید اگر و توانی از 2 باشد، بازی پایان می پذیرد.
    ب.ثابت کنید اگرباشد، بازی تنها در صورتی پایان می پذیرد کهیا توانی از 2 باشند.
    حل
    بیایید ببینیم که اگر نفر اول مهره و بقیه ی نفرات مهره داشته باشند، چه اتفاقی می افتد. برای این منظور فرض کنید تابعی باشد که مقدار آن 1 یا0 است و بدین شکل تعریف شده است:
    مقدار این تابع یک است، اگر نفر باشند و نفر اول مهره و بقیه هر کدام مهره داشته باشند و بازی تمام شدنی باشد؛ همچنین مقدار این تابع صفر است اگر بازی تمام شدنی نباشد.
    حال بیاییم چند حالت را با یکدیگر بررسی کنیم فرض کنید اسم این نفر به ترتیب باشد، در ابتدای کار یک مهره به می دهد (حالا، مهره دارد)، سپس چون یک مهره دریافت کرده، دو مهره به می دهد (حالا، مهره دارد)، بعد چون دو مهره دریافت کرده، یک مهره به می دهد (حالا، مهره دارد)، سپس چون یک مهره در یافت کرده است، دو مهره به می دهد (حالا،مهره دارد) و ... .
    با دنبال کردن استراتژی بالابه نتایج زیر می رسیم:
    1.اگر و فرد باشد، بعد از دور اول، تعداد مهره های هر فرد به ترتیب برابر است با، و چون به نفر اول این دفعه یک مهره رسیده است پس دو مهره به نفر بعدی می دهد بنابراین بعد از یک دور دیگر به نفر اول دو مهره خواهد رسید و تعداد مهره های افراد به ترتیب برابر با می شود (مطابق شکل). یا به عبارت دیگر اگر و باشد، آن گاه است (بازی تمام نشدنی است).


    2.اگر فرد و باشد، چون نفر اول در ابتدای دور دوم حذف می شود، در پایان دور دوم، نفر، دو مهره به نفر می دهد و مهره های نفرات به ترتیب برابر با می شود. پس اگر باشد،.


    3.اگر زوج باشد، بعد از دور اول، تعداد مهره های هر فرد به ترتیب برابر با خواهد بود و چون به نفر اول دو مهره رسیده باز بعد از یک دور دیگر تعداد مهره های افراد به ترتیب برابر باخواهد شد. به این ترتیب بعد از دور ام، نفرات با شماره ی زوج حذف خواهند شد و نفر خواهیم داشت که نفر اول مهره و بقیه ی افراد هر کدام، مهره خواهند داشت. به عبارت دیگر به ازای داریم: .
    حال قسمت الف مساله از ما می خواهد تعیین کنیم که در چه مواردی یک است و در چه مواردی صفر است. اگر باشد، با بار استفاده از قاعده ی سوم نتیجه می گیریم که . به طریق مشابه اگر باشد، طبق قاعده ی دو داریم ولی در بالا اثبات کردیم که این مقدار برابر با یک است پس .
    حال ثابت می کنیم که به جز موارد گفته شده در بالا به ازای، مقدار برابر صفر می باشد. فرض کنید باشد با بار استفاده از قاعده ی سوم به این نتیجه می رسیم که که اگر یا باشد طبق قاعده ی سوم می باشد.
    برای قسمت دوم به ازای، اگر زوج باشد، در دور اول تمام نفرات با شماره های زوج و نفر اول از بازی خارج می شوند و تعداد مهره های نفر سوم 4 عدد و تعداد مهره های بقیه ی افراد 2 است یعنی بازی و در قسمت قبل ثابت کردیم که بازی وقتی و فقط وقتی یک است که در نتیجه باید باشد.
    اگر فرد باشد، در دور اول نفرات با شماره های زوج و نفر اول حذف می شوند و تعداد مهره های نفر آخر برابر با 3 و تعداد مهره های بقیه ی نفرات برار با 2 می شود پس داریم و در قسمت الف دیدیم که این بازی فقط و فقط وقتی یک است که باشد یعنی باشد. پس بازی قسمت دوم، فقط و فقط به ازای یا تمام شدنی است.
    BYE 4 EVER

  6. #5
    مدیر بازنشسته
    39,161 امتیاز ، سطح 48
    39% کامل شده  امتیاز لازم برای سطع بعدی 989
    0% فعالیت
    دستاورد ها:
    SocialRecommendation First ClassCreated Album picturesVeteranTagger First Class
    نماد soroush_tayyebi
    تاريخ عضويت
    Jan 1970
    محل سکونت
    Tehran
    پست
    1,294
    گيپا
    640,650
    پس انداز
    0
    امتیاز
    39,161
    سطح
    48
    تشكرها
    2,568
    716 بار در 433 پست از اين كاربر تشكر شده


    به نظر شما این پست مفید است؟ بله | خیر

    پیش فرض استقرای قوی

    گاهی اوقات برای اثبات حکم استقرا به ازای ، لازم است که حکم استقرا را به ازای هر عدد صحیح کوچک تر از و بزرگ تر یا مساوی ( پایه استقرا می باشد). درست فرض کنیم تا بتوانیم حکم استقرا را به ازای هر مقدار صحیح ثابت کنیم. در چنین مواردی از اصل استقرای قوی کمک می گیریم؛ اصل استقرای قوی به شکل زیر است:
    اصل استقرای ریاضی قوی. اگر یک عدد طبیعی و یک جمله بر اساس پارامتر باشد، به طوری که:
    الف. برقرار باشد.
    ب. به ازای هر ، بتوان از برقراری ، برقراری را نتیجه گرفت.
    در این صورت، به ازای هر ، برقرار است.
    اصل استقرای قوی از اصل استقرای ضعیف، قوی تر است ولی هر دو، با اصل خوش ترتیبی و درنتیجه با هم معادل می باشند و با اصل قرار دادن یکی از آنها می توان درستی دیگر را ثابت کرد.

    مثال

    ثابت کنید هر عدد طبیعی بزرگ تر یا مساوی 2 را می توان به عوامل اول تجزیه کرد.
    حل
    واضح است که 2 را می توان به حاصل ضرب عوامل اول تجزیه کرد. (اگر عددی اول باشد، خود تجزیه ی به عوامل اول می باشد.)
    حال فرض کنید هر عدد طبیعی کوچک تر یا مساوی را بتوان به عوامل اول تجزیه کرد. می خواهیم ثابت کنیم عدد طبیعی را هم می توان به عوامل اول تجزیه کرد.
    اگراول باشد، که خود تجزیه ی به عوامل اول است. پس فرض کنید
    اول نباشد. در نتیجه دو عدد طبیعیوجود دارند که. بنا به فرض استقرا می توان و را به عنوان اول تجزیه کرد.

    پس ( ها و ها اولند.) یعنی به عوامل اول تجزیه شده است و حکم ثابت شد.



    مثال

    برای هر عدد صحیح غیر منفی ، عدد از عدد بر اساس قانون زیر به دست می آید:
    اگر آخرین رقم سمت راست عدد از 5 بیش تر باشد، . در غیر این صورت، رقم سمت راست را کنار می گذاریم و ارقام باقی مانده نمایشگر است (، تقسیم صحیح است). اگر شامل هیچ رقمی نباشد، کار پایان می یابد. آیا به ازای هر دلخواه، این فرآیند، پایان پذیر است؟
    حل
    بله، حکم را با استقرای قوی روی عدد، ثابت می کنیم. اگر باشد که حکم واضح است. حال فرض کنید حکم برای اعداد 1 تا برقرار باشد، ثابت می کنیم برای عدد نیز برقرار است. اگر رقم آخر عدد کوچک تر یا مساوی 5 باشد، یا با کنار گذاشتن آن رقم (یک مرحله از الگوریتم)، عدد حاصل دارای هیچ رقمی نیست که در نتیجه حکم اثبات می شود یا این که عدد به دست می آید که چون عدد است، پس طبق فرض استقرا این فرآیند پایان می یابد. ولی اگر رقم یکان عدد بزرگ تر از 5 باشد، با اجرای یک مرحله از این الگوریتم عدد به دست می آید که رقم یکان آن، برابر 1، 2، 3 یا 4 است و با اجرای یک مرحله ی دیگر از این الگوریتم عدد به دست می آید که عدد است. بنابراین باز طبق فرض استقرا، این فرآیند به پایان خواهد رسید.


    مثال

    فرض کنید که یک ماشین در اختیار داریم که می تواند این سه کار را بر روی کارت هایی که بر روی هر یک از آنها یک کلمه نوشته شده است انجام دهد:
    •دو کارت که بر روی آنها دو کلمه نوشته شده است را بگیرد و یک کارت تولید کند که بر روی آن این دو کلمه پشت سر هم نوشته شده باشد. (برای مثال اگر بر روی کارت اول رشته ی و بر روی کارت دوم رشته نوشته شده باشد، خروجی ماشین کارتی خواهد بود که بر روی آن نوشته شده است.)
    •یک کارت که بر روی آن کلمه ی نوشته شده است را دریافت کند و در خروجی کارت ایجاد کند که بر روی آن نوشته شده است. (برای مثال اگر بر روی کارت ورودی کلمه ی نوشته شده باشد، خروجی ماشین کارتی خواهد بود که بر روی آن کلمه ی نوشته شده است.)
    •یک کارت که بر روی آن کلمه ی نوشته شده است را دریافت کند و در خروجی کارتی ایجاد کند که بر روی آن نوشته شده است. (برای مثال اگر بر روی کارت ورودی هیچ کلمه ای نوشته نشده باشد، خروجی ماشین کارتی خواهد بود که بر روی آن کلمه ی نوشته شده است.)
    در ابتدا تعداد زیادی کارت که بر روی آنها هیچ کلمه ای نوشته نشده است در اختیار ما قرار گرفته است.
    الف.نشان دهید که با استفاده از این کارت ها و با این ماشین می توان کارتی را ایجاد کرد که بر روی آن کلمه ی نوشته شده باشد.
    ب‌.ثابت کنید که با استفاده از این ماشین می توان هر کارتی که بر روی آن یک کلمه نوشته شده است را تولید کرد، اگر و فقط اگر این این کلمه تنها از و تشکیل شده باشد و تعداد های آن برابر های آن باشد.
    حل
    الف. ابتدا با استفاده از یک کارت خالی و عمل دوم، کارت و بعد با استفاده از یک کارت خالی و عمل سوم، کارت و بعد با استفاده از عمل اول و کارت های و ، کارت و بعد با استفاده از عمل اول و کارت های و کارت ، کارت را تولید می کنیم.
    ب. اگر کلمه ی توسط این ماشین تولید شده باشد، با استقرای قوی روی طول کلمه ی ثابت می کنیم که کلمه ی تنها از حروف و تشکیل شده است و تعداد ها و ها در کلمه ی با یکدیگر برابر است.
    اگر طول صفر باشد که حکم واضح است. فرض کنید این حکم برای همه ی کلمات با طول کمتر از درست باشد. ثابت می کنیم برای هر کلمه ی به طول نیز درست است. اگر کلمه ی با عمل اول درست شده باشد، یعنی باشد، چون طول کلمات و کم تر از است، پس کلمات و فقط از حروف و تشکیل شده اند و تعداد حرف های در کلمه ی و برابر با تعداد حرف های در آنهاست. بنابراین کلمه ی تنها از حروف و تشکیل شده است و تعداد حرف های با تعداد حرف های در مساوی است. به طریق مشابه اگر کلمه ی با استفاده از عمل دوم (سوم) درست شده باشد، یعنی باشد. چون طول کلمه ی برابر با است، بنابراین طبق فرض استقرا کلمه ی تنها از حروف و تشکیل شده است و تعداد حروف و در کلمه ی با یکدیگر برابر است؛ در نتیجه کلمه ی تنها از حروف و تشکیل شده است و تعداد حرف های a در کلمه ی برابر تعداد حرف های آن است. پس حکم با استقرا ثابت شد.


    حال با استقرای قوی روی طول کلمه ی ، ثابت می کنیم هر کلمه ای که تنها از حروف و تشکیل شده باشد و تعداد حروف با تعداد حروف برابر باشد را می توان تولید کرد.
    اگر طول کلمه ی صفر باشد که حکم واضح است. فرض کنید که حکم برای همه ی کلمات با طول کمتر از درست باشد ثابت می کنیم برای هر کلمه ی به طول نیز حکم برقرار است. اگر حرف اول و آخر کلمه ی متفاوت باشند، یعنی به صورت یا باشد ( کلمه ای است که از حذف حرف اول و آخر کلمه ی به دست می آید). واضح است که کلمه ی تنها از حروف و ساخته شده است و تعداد حروف با تعداد حروف در آن مساوی است (زیرا در چنین است) و طول کلمه ی کم تر از است؛ پس طبق فرض [تنها کاربرانی که عضو شده اند و از طریق ایمیل عضویتشان فعال شده می تواند این لینک را ببینند. ] می توان کلمه ی را تولید کرد. حال اگر کلمه ی باشد، می توان با استفاده از کلمه ی و عمل دوم (عمل سوم) کلمه ی را تولید کرد.
    پس فرض کنید حروف اول و آخر کلمه ی یکسان باشند. بنابر تقارن فرض کنید حرف اول و آخر کلمه ی ، باشد. را مساوی تعداد های کلمه ی منهای تعداد های آن در حرف اول آن می گیریم. واضح است که و (زیرا و حرف ام است). از طرف دیگر است؛ در نتیجه لااقل یک وجود دارد که باشد. حال فرض کنید باشد که کلمه ای است که از حرف اول کلمه ی ساخته شده است و کلمه ای است که از حرف آخر کلمه ی ساخته شده است. با توجه به این که و است؛ پس تعداد حروف در کلمه ی برابر با تعداد حروف در آن است. از طرف دیگر طول کلمات و کم تر از است و تنها از حروف و تشکیل شده اند. بنابراین طبق فرض استقرا می توان کلمات و را ساخت، حال با استفاده از کلمات و و عمل اول، می توان کلمه ی را تولید کرد.


    مثال

    یک رشته، یک دنباله ی متناهی از صفر و یک است. یک مجموعه ی متناهی از رشته هاست که برای هر دو رشته ی دلخواه و از آن داریم، (منظور از رشته ای است که از کنار هم گذاشتن دو رشته ی و به دست می آید برای مثال اگر و باشد آنگاه خواهد بود.)
    ثابت کنید که رشته ای مانند وجود دارد که هر رشته ی دلخواه را می توان از کنار گذاشتن تعدادی به دست آورد.
    حل
    در صورتی که رشته ی از کنار هم گذاشتن تعدادی رشته ی تولید شود، را یک سازه می نامیم، طول رشته ی را با نشان می دهیم. برای حل مسئله ابتدا دو لم زیر را ثابت می کنیم:

    لم 1

    اگر باشد، آنگاه و یک سازه ی مشترک دارند.
    اثبات لم
    حکم را با استقرا روی ثابت می کنیم، اگر باشد، حکم واضح است.
    فرض می کنیم که حکم برای هر و که و باشد، برقرار باشد. حکم را برای و به این صورت ثابت می کنیم: بدون این که از کلیت مسأله کم شود می توان فرض کرد.
    حال اگر باشد، آنگاه، پس و سازه ی مشترک دارند. پس فرض کنید و باشد. از یک طرف رقم اول ، رقم اول رشته ی و از طرف دیگر همان می باشد. بنابراین رشته ی به شکل می باشد که و می باشد؛ در نتیجه. پس طبق فرض استقرا رشته های و دارای سازه ی مشترکی مانند هستند و چون این سازه ی مشترک هم و هم را می سازد رشته ی را نیز می سازد. بنابراین سازه ی مشترک رشته های و می باشد.



    لم2

    اگر و دو سازه ی مشترک باشند، آنگاه و سازه ی مشترک دارند.
    اثبات لم
    چون و سازه های مشترک هستند، برای هر داریم:


    را بزرگ ترین مقسوم علیه مشترک و می گیریم. فرض می کنیم:

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


    بنابراین به ازای هر داریم:


    پس یک سازه ی مشترک برای و می باشد.


    نتیجه ی لم

    اگر سازه های باشند، آنگاه ها دارای سازه ی مشترکی می باشند.
    یک عضو دلخواه از را به دلخواه انتخاب می کنیم و آن را می نامیم. برای هر بنا به فرض داریم و در نتیجه لم 1 نتیجه می دهد که و سازه ی مشترکی دارند که آن را می نامیم. حال همه ی ها را در نظر می گیریم. بنا به نتیجه ی لم 2، این رشته ها دارای یک سازه ی مشترک هستند که آن را می نامیم. چون سازه ی و سازه ی است، پس سازه ی مشترک همه ی هاست و بنابراین حکم ثابت شد.

    مثال

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


    می دانیم که این مهره همه ی خانه های جدول را تهدید می کنند. ثابت کنید است. (منظور از ، بزرگ ترین عدد صحیح کوچک تر یا مساوی است.)
    حل
    برای این مساله راه حل های متفاوتی وجود دارد که به بعضی از آنها در زیر اشاره می کنیم:
    راه حل اول:
    نخست دقت می کنیم که اگر دو خانه ی و که روی قطر اصلی قرار دارند، فاصله شان از هم فرد باشد (تعداد خانه های بین این دو خانه زوج باشد)، اگر روی این دو خانه مهره ای نباشد، خانه که روی ستون و سطر قرار دارد، توسط هیچ مهره ای تهدید نمی شود، پس با خانه ی ، یا خانه شامل مهره است. به عبارت دیگر، در هر دو خانه ای که فاصله شان فرد است، حداقل یک مهره وجود دارد. بنابراین همه ی خانه های با شماره های زوج یا همه ی خانه های با شماره های فرد باید شامل مهره باشند. (کافی است یکی از خانه هایی را که روی آن مهره ای قرار ندارد در نظر بگیرید. واضح است اگر این خانه زوج باشد، روی هر خانه ی فرد باید یک مهره باشد و همچنین اگر این خانه فرد باشد، باید روی تمام خانه های زوج یک مهره باشد.) حال دقت می کنیم که از هر سه خانه ی متوالی از خانه های فرد (یا زوج)، باید حداقل درون یکی از آنها مهره باشد. (چون مطابق شکل اگر و و خالی باشند خانه ی تهدید نشده باقی می ماند) پس حداقل روی خانه های قطر، مهره وجود داشته است که با حالت گیری روی باقی مانده بر 6 ثابت می شود که حداقل مهره های لازم می باشد.








    راه حل دوم :
    در این راه حل از استقرا استفاده می کنیم اگر حداقل مهره های لازم برای جدول
    ، باشد، برای پایه ی استقرا حکم به راحتی نشان داده می شود. حال فرض می کنیم برای هر داشته باشیم. حال جدول را در نظر بگیرید. به خانه های و و توجه کنید. برای پوشیده شدن خانه های جدول پایین یا باید در خانه ی مهره ای قرار گیرد و در غیر این صورت باید در خانه های و مهره قرار گیرد. اگر در خانه های و مهره قرار گیرد که داریم:
    در غیر این صورت اگر جدولپایین دو مهره نداشته باشد، باید در خانه ی حتماً مهره ای قرار گیرد؛ در این صورت برای تهدید شدن خانه های و و باید در تک تک خانه های و و مهره وجود داشته باشد زیرا در خانه های و مهره ای وجود ندارد. پس در این صورت داریم:



    توضیح

    مساله ی انتخاب خانه روی قطر اصلی به عنوان مکان مهره معادل آن است که عدد از اعداد انتخاب کنیم به طوری که در بین اعدادی که انتخاب نکرده ایم، تفاضل هیچ دو عددی فرد نباشد و میانگین هردو عدد انتخاب نشده، انتخاب شده باشد. با توجه به این موضوع اگر ، حداقل تعداد مهره های لازم باشد، ثابت کردیم: ولی قابل توجه است که
    BYE 4 EVER

  7. #6
    مدیر بازنشسته
    39,161 امتیاز ، سطح 48
    39% کامل شده  امتیاز لازم برای سطع بعدی 989
    0% فعالیت
    دستاورد ها:
    SocialRecommendation First ClassCreated Album picturesVeteranTagger First Class
    نماد soroush_tayyebi
    تاريخ عضويت
    Jan 1970
    محل سکونت
    Tehran
    پست
    1,294
    گيپا
    640,650
    پس انداز
    0
    امتیاز
    39,161
    سطح
    48
    تشكرها
    2,568
    716 بار در 433 پست از اين كاربر تشكر شده


    به نظر شما این پست مفید است؟ بله | خیر

    پیش فرض استقرای چند گانه



    در بعضی از مسایل استقرایی، برای اثبات گام استقرایی مساله ، به اثبات مساله احتیاج پیدا می کنیم و برای اثبات گام استقرایی مساله ، به اثبات مساله احتیاج پیدا می کنیم. به نظر می رسد که دور اتفاق می افتد و نمی توانیم هیچ کدام از مسایل را اثبات کنیم. ولی گاهی برای اثبات، به درستی و نیاز داریم و برای اثبات به و احتیاج داریم. در این گونه موارد دور اتفاق نمی افتد و می توانیم از استقرا استفاده کنیم زیرا، درستی و ، درستی را نتیجه می دهند و بعد درستی و درستی را نتیجه می دهند. سپس درستی و درستی را نتیجه می دهند و حالا درستی و ، درستی را نتیجه می دهند و ... بدین ترتیب به راحتی هر دو مساله و ، اثبات می شوند. حال به بررسی چند مثال می پردازیم.
    می دانیم دنباله که هر جمله با شروع از جمله سوم، برابر مجموع دو جمله قبلی آن است را دنباله فیبوناتچی می نامیم. اگر ، جمله ام فیبوناتچی باشد؛ می توانیم دنباله فیبوناتچی را با رابطه بازگشتی زیر نشان دهیم:


    در قسمت روابط بازگشتی به بررسی دنباله فیبوناتچی می پردازیم. در اینجا نیز یک مساله در مورد دنباله فیبوناتچی را بررسی می کنیم.

    مثال

    فرض کنید، امین جمله ی فیبوناتچی باشد. به ازای هر ثابت کنید:


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


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


    و با توجه به این که، باید ثابت کنیم:


    پس بیایید مساله ی بالا را، با کمک استقرا، ثابت کنیم. حکم به ازای بدیهی است زیرا

    .

    حال فرض کنید که مساله ی دوم به ازای برقرار باشد یعنی؛ پس داریم:


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


    و با توجه به این که، باید داشته باشیم: . این همان مساله ی قبلی است. لذا دو مساله به یکدیگر وابسته شده اند و درستی اولی به درستی دومی و درستی دومی به درستی اولی وابسته است.
    اگر قرار دهیم:




    با توجه به استدلال های بالا نتیجه می گیریم که: درستیو، درستیرا نتیجه می دهد و درستیودرستی را نتیجه می دهد. حال با توجه به مطالبی که در ابتدای این بخش گفته شد، اثبات کامل است.

    مثال

    فرض کنید، و مجموع دو جمله در میان عنصرهای سطر ام مثلث خیام باشند که به ترتیب با اولین، دومین و سومین عنصر از سمت چپ آغاز می شوند. روابط زیر را ثابت کنید.












    اثبات
    حکم را به این صورت نتیجه می گیریم که












    برای نتیجه گیری روابط بالا کافی است دقت کنیم که






    و درستی روابط (9) , (8) , (7) از این جا ناشی می شود که هر عنصر در مثلث خیام، برابر با مجموع دو عنصر بالایی آن است. با توجه به این روابط به راحتی روابط (1) تا (6) ثابت می شوند، در نتیجه حکم مساله ثابت می گردد.
    BYE 4 EVER

  8. #7
    مدیر بازنشسته
    39,161 امتیاز ، سطح 48
    39% کامل شده  امتیاز لازم برای سطع بعدی 989
    0% فعالیت
    دستاورد ها:
    SocialRecommendation First ClassCreated Album picturesVeteranTagger First Class
    نماد soroush_tayyebi
    تاريخ عضويت
    Jan 1970
    محل سکونت
    Tehran
    پست
    1,294
    گيپا
    640,650
    پس انداز
    0
    امتیاز
    39,161
    سطح
    48
    تشكرها
    2,568
    716 بار در 433 پست از اين كاربر تشكر شده


    به نظر شما این پست مفید است؟ بله | خیر

    پیش فرض استقرای قوی و چندگانه

    آگهی تبلیغات
    مقدمه

    همان‌طور که به زیبایی با [تنها کاربرانی که عضو شده اند و از طریق ایمیل عضویتشان فعال شده می تواند این لینک را ببینند. ] آشنا شدیم، کم‌کم به محدودیت‌های آن نیز باید پی‌برده‌ باشیم.از طرفی همواره نمی‌توان استقرای ضعیف را استفاده نمود زیرا گام‌های بازگشت یکی‌یکی بوده و اثبات را محدود می‌کند.
    استقرای چندپایه هم که قوی‌تر می‌باشد بازهم محدودیت در ثابت‌بودن عدد دارد.
    به وضوح می‌توان استقرایی را به کار بست که تفاوت آن با استقرای چندپایه در ثابت نبودن عدد k می‌باشد و می‌توان حتی فقط روی یک گزارة استقرا نزد بلکه اگر درستی به درستی و درستی هم به نوبة خود به وابسته باشد، در شرایطی می‌توان بازهم از اصل استقرا به شکل دیگری استفاده کرد که به معرفی آنها می‌پردازیم.
    BYE 4 EVER

+ پاسخ به مبحث

بازدید کنندگانی که از طریق جستجو کلمات ذیل به انجمنهای گیگاپارس آمده اند:

استقرا

نامساوی برنولی

اثبات نامساوی برنولینامساوي برنولياستقرا ریاضیاصل استقرای تعمیم یافتهاستقرای قویاستقرای تعمیم یافتهاستقرای قوی ریاضینمونه سوالات استقرامثال استقرای ریاضیمثال استقرا ریاضیاصل استقرانمونه سوال استقرای ریاضیحل نمونه سوالات استقراء رياضياستقرای ریاضیاثبات از طریق استقرااستغرامسائل استقراء رياضي استقرا مثال استقرادنباله لوکانمونه سوال استقرااستقراي تعميم يافتهبه استقرا ثابت کنیددر دنباله ها
SEO Blog

اطلاعات این مبحث

Users Browsing this Thread

در حال حاضر 1 کاربر در حال دیدن این مبحث می باشند، (0کاربر عضو و 1 کاربر مهمان)

تگهای این مبحث

قانون های ارسال نوشته

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts