استقرای ریاضی

اصل استقرا که پیش‌تر به آن اشاره کردیم، گزاره‌ای دربارهٔ اعداد صحیح مثبت است. صورت آن چنین است:

اصل استقرا. فرض کنید $P (n)$ گزاره‌ای دربارهٔ عدد صحیح مثبت $n$ باشد. فرض کنید که:

(الف) گزارهٔ $P (1)$ درست است؛

(ب) اگر گزارهٔ $P (k)$ برای عدد صحیح داده‌شدهٔ $k$ درست باشد، آنگاه گزارهٔ $P (k + 1)$ نیز درست است.

آنگاه گزارهٔ $P (n)$ برای همهٔ $n$ درست است.

اگر کمی در این باره بیندیشیم، خواهیم دید که کاملاً با شهود ما سازگار است. مدل‌های گوناگونی وجود دارند که به ما در تجسم این اصل کمک می‌کنند. در یکی از این مدل‌ها، دستگاهی از دومینوهای ایستاده را در نظر می‌گیریم که طوری ردیف شده‌اند که اگر هر یک به سمت بعدی واژگون شود، آن را نیز به سمت دومینوی پس از خود واژگون خواهد کرد. این قرینهٔ فرض (ب) است. قرینهٔ (الف) صرفاً این است که می‌توانیم اولین دومینو را واژگون کنیم. اما سپس دومین دومینو را واژگون خواهد کرد، که به سومی برخورد می‌کند، و همین‌طور تا آخر. با نوشتن گام‌های کافی از این دست، می‌توانیم به هر دومینوی مشخصی، یا گزارهٔ $P (n)$ برای هر $n$ دلخواه برسیم. با این حال، اکنون دیده‌ایم که فرض‌های (الف) و (ب) جوهرهٔ این فرایند هستند و می‌توانیم صرفاً با نشان دادن اعتبار آن‌ها، از همهٔ این نوشتن‌ها بپرهیزیم.

به عنوان مثال، اثباتی به روش استقرا برای فرمولی از مجموع یک دنبالهٔ حسابی آشنا ارائه می‌دهیم:

1 + 2 + \dots + n = \frac{n (n + 1)}{2} .

آنگاه $P (n)$ گزاره‌ای است مبنی بر اینکه مجموع $n$ عدد صحیح اول برابر با $\frac{n (n + 1)}{2}$ است. بنابراین $P (1)$ می‌گوید که مجموع عدد صحیح اول، یعنی ۱، برابر با $\frac{1 (1 + 1)}{2} = 1$ است. پس فرض (الف) برآورده می‌شود. اکنون فرض (ب) با «اگر $P (k)$ درست باشد» آغاز می‌شود. این بدان معناست که باید فرض کنیم $P (k)$ درست است و ببینیم آیا درستی $P (k + 1)$ نتیجهٔ این فرض است. پس با این فرض آغاز می‌کنیم

P (k) : 1 + 2 + \dots + k = \frac{k (k + 1)}{2} .

آنگاه باید مجموع زیر را در نظر بگیریم

1 + 2 + \dots + k + (k + 1) = (1 + 2 + \dots + k) + (k + 1) .

اما، بنا بر آنچه فرض کرده‌ایم،

1 + 2 + \dots + k = \frac{k (k + 1)}{2} = (k + 1) \cdot \frac{k}{2} .

بنابراین

1 + 2 + \dots + k + (k + 1) = (k + 1) (\frac{k}{2} + 1) = (k + 1) (\frac{k + 2}{2}),

یا

1 + 2 + \dots + (k + 1) = \frac{(k + 1) ((k + 1) + 1)}{2},

که همان $P (k + 1)$ است. پس (الف) و (ب) برآورده می‌شوند، و $P (n)$ به روش استقرا برای همهٔ $n$ برقرار است.

تمرین‌ها

تمرین ۱.

ثابت کنید که $1^{2} + 2^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6} .$

تمرین ۲.

ثابت کنید که

تمرین ۳.

ثابت کنید که

تمرین ۴.

نشان دهید که فرض (ب) برای $P (n) : n = n + 2,$ برآورده می‌شود، در حالی که آشکارا نادرست است.

تمرین ۵.

مثالی از یک $P (n)$ ارائه دهید که برای $n > 1$ نادرست باشد اما فرض (الف) برای آن برقرار باشد.

تمرین ۶.

ثابت کنید که $1 + 3 + 5 + \dots + (2 n - 1) = n^{2}, n = 1, 2, 3, \dots .$

تمرین ۷.

ثابت کنید که
$(1 - \frac{1}{4}) (1 - \frac{1}{9}) (1 - \frac{1}{16}) \dots (1 - n^{- 2}) = \frac{n + 1}{2 n}$

برای $n = 2, 3, 4, \dots .$