با استقرای ریاضی ثابت کنید که $n!=n(n-1)!$.

Question

من دانشجوی کارشناسی رشتهٔ رایانه هستم. در درس «طراحی الگوریتم» که در ترم یک به ما داده‌اند پرسش زیر داده شده‌است.

پرسش: رابطهٔ بازگشتی فاکتوریل را نوشته و با استقرا ریاضی ثابت کنید.

تلاش من: من نوشتم؛ رابطهٔ فاکتوریل بازگشتی $n! =n(n-1)!$ است. شرط اول استقرا که جای گذاری عدد یک در $p(n)$ بود رو انجام دادم و عدد یک رو توی فاکتوریل بازگشتی جایگذاری کردم. سپس $k$ رو هم جایگزین $n$های فاکتوریل بازگشتی کردم. ولی مشکل من تو مرحله آخرشه یعنی $k+1$... . بعدش نوشتم:

\begin{align} & k= k(k+1)!\\ & k!+k \end{align}

نمیدونم کدوم صحیح هست.

Comments

@Artemis مرجع با اسم درس و مقطع فرق دارد. مرجع یعنی کتاب، مقاله یا هر گونه اثر نشریافته و قابل دسترس برای «رجوع کردن»! اینکه رشته و مقطع‌تان چیست را می‌توانید در قسمت «دربارهٔ من» در صفحهٔ شناسه‌تان بیفزائید. اینکه در درس فلان این پرسش را به شما داده‌اند را نیز می‌توانید در متن پرسش اشاره کنید. به ویرایشی که بر روی پست‌تان انجام دادم نگاه کنید.

---

@Artemis منظور شما را دقیق متوجه نشدم اگر نظرتون در تنظیم حکم استقرا است یعنی $P(k+1)$ بنویسید
$(n+1)!=(n+1)n!$

Answer 1

به نام خدا

$$n!=n(n-1)!$$

ابتدا برای $P(1)$ عبارت را بررسی می‌کنیم:

$$1!=1(1-1)! \Rightarrow 1!=1(0!) \Rightarrow 1=1$$

پس $P(1)$ درست است.$\checkmark$

سپس فرض کنید که $P(k)$ برقرار باشد؛ یعنی:

$$k!=k(k-1)!$$

و بعد ثابت کنید که $P(k)$، درستی $P(k+1)$ را نتیجه می‌دهد. $n$ را با $k+1$ جایگزین کنید تا عبارت زیر به‌دست آید:

$$(k+1)!=(k+1)k!$$

سپس مقدار $k!$ یعنی $k(k-1)!$ را به‌جای $k!$ در عبارت بالا جایگزین کنید:

$$(k+1)!=(k+1)k(k-1)!$$

اگر درستی این تساوی را اثبات کنیم، استقرا به‌پایان می‌رسد. برای این کار ابتدا طرفین را بر $(k-1)!$ تقسیم کنید:

$$(k+1)!=(k+1)k(k-1)! \Longrightarrow \frac{(k+1)!}{(k-1)!}=(k+1)k$$

و پس از باز کردن پرانتز سمت راست تساوی و فاکتوریل‌ها، به تساوی زیر می‌رسیم:

$$\frac{(k+1)!}{(k-1)!}=(k+1)k \Longrightarrow \frac{(k+1)(k)(k-1)(k-2) \cdot \cdot \cdot 2 \cdot 1}{(k-1)(k-2)(k-3)(k-4) \cdot \cdot \cdot 2 \cdot 1} =k^2+k$$

حالا در تساوی بالا در سمت چپ، تمام پرانتزها باهم ساده می‌شوند و در سمت چپ، فقط $(k+1)k$ باقی می‌ماند:

$$(k+1)k=k^2+k \rightarrow k^2+k=k^2+k$$

پس گزارۀ کلی $n!=n(n-1)!$، بنابر استقرا درست است. $\blacksquare$