مبانی ترکیبیات. هفتهٔ هفتم. استقراء ریاضی (۲)

استقراء قوی، استقراء قهقرایی، استقراء روی اعداد صحیح

ملاحظاتی دربارهٔ تعریف بازگشتی دنباله‌ها و آرایه‌ها

تعریف بازگشتی آرایه‌ها

حسابان متناهی (ویدئوی اول)

حسابان متناهی (ویدئوی دوم)

تعریف بازگشتی دنباله‌ها

خاصیت یا اصل خوش‌ترتیبی

تمرین‌های هفتهٔ هفتم

۱. رابطه زیر را با استقرا ثابت کنید.
\[\big(1+x\big)\big(1+x^2\big)\dots\big(1+x^{2^n}\big)=1+x+\dots+x^{2^{n+1}}-1\]

۲. ثابت کنید اگر \(2\cos\varphi=x+\frac{1}{x}\)، آنگاه به‌ازای هر عدد صحیح مثبت \(n\)، \(2\cos n\varphi=x^n+\frac{1}{n}\).

۳. دنبالهٔ \(\big\{x_n\big\}_{n\geq0}\) از اعداد صحیح، با شرط اولیه \(x_0=2\) و رابطه بازگشتی
\[x_n=x_{n-1}^2-x_{n-1}+1\] که به‌ازای \(n\geq1\) برقرار است، تعریف شده است. ثابت کنید به‌ازای هر دو مقدار متمایز \(m\) و \(n\)، مقادیر \(x_m\) و \(x_n\) نسبت به‌هم اول هستند.

۴. دنبالهٔ کنوث، با رابطه بازگشتی زیر تعریف می‌شود:
\[\left\{\begin{aligned}&k_0=1\\[7pt]&k_{n+1}=1+\min\big(2k_{\lfloor\frac{n}{2}\rfloor},3k_{\lfloor\frac{n}{3}\rfloor}\big);\quad n\geq0\end{aligned}\right.\]ثابت کنید به ازای هر \(n\geq0\)، \(k_n\geq n\).

۵. ثابت کنید برای تمام اعداد صحیح \(n\geq0\)، \(10|(n^5-n)\).