چرا برای هر عدد طبیعی $k$، حاصلضرب هر $k$ عدد صحیح متوالی بر $!k$ بخشپذیر است؟

Question

گزارهٔ زیر را اثبات کنید.

برای هر عدد طبیعی $k$، حاصلضرب هر $k$ عدد صحیح متوالی بر $k !$ بخشپذیر است، در نتیجه فرمولِ ترکیب انتخاب $k$ شی از بین $n$ شی، یک عدد صحیح به ما می‌دهد.

$$\binom{n}{k}=\frac{n!}{k!(n-k)!}$$

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

Comments

@ailin گفتنَ «گزارهٔ حاصلضرب هر $k$ عدد متوالی بر $k!$ بخشپذیر است، ترکیب انتخاب $k$ شی از $n$ شی را نتیجه می‌دهد» جمله‌ای نادرست است! چرا؟ چون قسمت اول یک گزاره است ولی قسمت دوم یک عدد است، یعنی چه که یک گزاره یک عدد را نتیجه می‌دهد؟ برای اینکه منظورم را بهتر متوجه شوید یک مثال می‌زنیم. گزارهٔ «$a$ بر ۲ بخشپذیر است»، گزارهٔ «$a$ عددی زوج است» را نتیجه می‌دهد. ولی نمی‌توان گفت گزارهٔ «$a$ بر ۲ بخشپذیر است» جملهٔ «عدد ۶» را نتیجه می‌دهد، عدد ۶ چه؟ آیا منظور این است که «$a$ عدد ۶ است»؟ باید یک گزاره بنویسید نه یک چیز ناقص. یک مثال ساده‌تر «هوا ابری است» نتیجه می‌دهد «احتمال دارد هوا بارانی شود»، ولی تا حالا شنیدید کسی بگوید «هوا ابری است پس آب»، چجوری این جمله را معنا می‌کنید؟ هوا ابری است پس آب! نوشتن درست مهم است، اگر درست چیزی را بیان کنید و بنویسید، خود به خود خیلی از راه حل پرسش را هم متوجه می‌شود مثلا متوجه می‌شوید که فرض چیست و حکم چیست.
احتمال می‌دهم که قسمت دوم پرسش‌تان این بوده‌است که «عددِ صحیح بودنِ حاصل انتخاب $k$ از $n$ را نتیجه می‌دهد».

---

@ailin به ویرایشی که بر روی پرسش‌تان انجام دادم نگاه کنید. بعلاوه «اثباتش را دارم» آیا در کتاب یا مرجعی است؟ اگر بلی آن را ذکر کنید مانند صفحهٔ فلان کتاب فلان نوشتهٔ فلان. و اینکه «نمی‌فهمم» به تنهایی خیلی روشن نیست، می‌توانید دقیقا بگوئید کجای آن اثبات را نمی‌فهمید تا دوستان کمک‌تان کنند.

Answer 1

کافی ثابت کنیم تعداد عامل اول p در حاصل ضرب k عدد طبیعی متوالی کمتر از تعداد عامل اول p در $k!$ نیست.

می دانیم تعداد عامل اول p در $k!$ برابر است با

$$\sum _{i=1}[ \frac{k}{p^i}] $$

در نتیجه تعداد عامل اول p در

$$(n+1)(n+2).....(n+k)$$

برابر است با

$$\sum _{i=1}[ \frac{n+k}{p^i}] - \sum _{i=1}[ \frac{n}{p^i}] $$

حال به سادگی می توان نشان داد که

$$[ \frac{n+k}{p^i}]\geq [ \frac{n}{p^i}] + [ \frac{k}{p^i}] $$

Answer 2

ابتدا ثابت میکنیم $\binom{n}{k}$ به ازای هر $n$ طبیعی و هر $k$ صحیح در بازه $[0,n]$ صحیح است . سه حالت رخ میدهد :

1. $k=0$
2. $0\lt k\lt n$
3. $k=n$

برای حالات اول و سوم به وضوح خواهیم داشت $\binom{n}{k}=1$ که صحیح است. پس کافیست حالت دوم را اثبات کنیم که برای این کار از استقرای ریاضی و اتحاد پاسکال کمک میگیریم. اتحاد پاسکال میگوید :

$\binom{n-1}{k}+\binom{n-1}{k-1}=\binom{n}{k}$

اثبات این اتحاد به کمک تعریف ترکیب و گرفتن مخرج مشترک امکان پذیر است و مستقل از صحیح بودن ترکیب ها می باشد بنابراین استفاده از آن در اثبات خللی ایجاد نمی کند. به این ترتیب اگر همه ترکیب های $\binom{n-1}{k}$ صحیح باشند نتیجه میگیریم همه ترکیب های $\binom{n}{k}$ نیز صحیح خواهند بود زیرا یا برابر 1 است یا حاصل جمع دو عدد صحیح. بدیهیست که حکم به ازای n=1 صدق می کند پس به ازای همه n های صحیح بزرگتر از 1 هم صدق می کند.

حال که اثبات حکم اول را به پایان رساندیم اثبات میکنیم ضرب هر $k$ عدد طبیعی بر $k!$ بخش پذیر است. عدد

$A=(n+1)(n+2)\cdots(n+k)$

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

$\binom{n+k}{n} \in \mathbb{Z} \Rightarrow \frac{(n+k)!}{n!\cdot k!} = \frac{(n+k)(n+k-1)\cdots(2)(1)}{(n)(n-1)\cdots(2)(1)\cdot k!}=(n+k)(n+k-1)\cdots(n+1)=A \Rightarrow A \in \mathbb{Z}$

و حکم دوم برای $n$ های طبیعی ثابت میشود. اگر یکی از این $k$ عدد برابر 0 باشد حاصل 0 خواهد بود که با تقسیم بر $k!$ عددی صحیح به دست می آید. همچنین اگر همه اعداد منفی باشند درستی حکم تغییری نمیکند پس حاصل ضرب هر $k$ عدد صحیح متوالی بر $k!$ بخش پذیر است.

Comments

@moh_amin احتمالا پرسش مسیر برعکس را خواسته‌است یعنی به جای اینکه از صحیح بودنِ $\binom{n}{k}$ استفاده کنید و سپس بگوئید حاصلضرب $k$ عدد پشت‌سرهم صحیح می‌شود، دومی را ثابت کنید و سپس اولی را از آن نتیجه بگیرید.

---

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

---

@moh_amin موردی ندارد و اتفاقا به پاسخ شما امتیاز مثبت هم دادم. اگر دوستان دیگر پاسخ از سمت دیگر را نگذاشتند، سر فرصت خودم می‌گذارم.

Answer 3

برای اینکه ببینید هیچ تلاشی بدون حاصل نمی‌ماند، بیایید ببینیم من زمانی که این پرسش را خواندم چه فکری کردم.

روش نخست:

عدد $k$ را یک عدد طبیعی دلخواه بردارید. $k$ عدد طبیعی پشتِ‌سرهم بردارید و عدد نخست را $a$ نمایش دهید. پس عددهایمان برابر خواهند بود با $\lbrace a, a+1, a+2, \dots, a+k-1\rbrace$ (دقت کنید که اگر تا $a+k$ ادامه دهید آنگاه $k+1$ عدد دارید!).

اگر $k\geq 2$ باشد آنگاه ثابت می‌کنیم که دست‌کم یکی از این عددها بر ۲ بخش‌پذیر است. برای این کار بیایید $a$ را به شکل پیمانه‌ای بر حسب ۲ بنویسیم. $a$ در تقسیم بر ۲ یا باقیماندهٔ ۰ دارد یا باقیماندهٔ ۱، پس به یکی از دو شکلِ $2d$ یا $2d+1$ نوشته می‌شود. در حالت یکُم عددهایمان بر حسب ۲ به شکل زیر درمی‌آیند.

$$2d, 2d+1, 2(d+1), 2(d+1)+1, \dots, 2(d+[\frac{k-1}{2}])+(k-1-2[\frac{k-1}{2}])$$

در حالت دوم عددهایمان به شکل زیر درمی‌آیند.

$$2d+1, 2(d+1), 2(d+1)+1, 2(d+2), \dots, 2(d+[\frac{k}{2}])+(k-2[\frac{k}{2}])$$

همانطور که می‌بینید، در هر دو حالت، دستِ‌کم $[\frac{k}{2}]$ عدد که مضرب ۲ باشند در این $k$ عددِ پشتِ‌سرهم وجود دارد. همین روند برای هر عدد دیگر تا خودِ $k$ درست است. بعلاوه توجه کنید که اگر $k\geq 4$ آنگاه حداقل ۲ عدد زوج که یکی‌شان مضرب ۴ است وجود دارد، یعنی اینکه فقط یک عدد زوج که مضرب ۴ است در بین عددهایمان نیست و واقعا می‌توانیم یکی را به عنوان مضرب ۴ و یک عدد متفاوت را به عنوان مضرب ۲ برداریم. پس در بینِ $k$ عددِ پشتِ‌سرهم همیشه این امکان هست که دقیقا برای هر $i$ که $1\leq i\leq k$، یکی از آنها را برداریم که مضربش است. پس بیایید عددهایمان را با $a_i$ نمایش دهیم که یعنی عددی که به عنوان مضربِ $i$ برداشته‌ایم. چون $a_i$ مضرب $i$ است، پس باید عدد طبیعی‌ای مانند $d_i$ وجود داشته‌باشد که $a_i=i\times d_i$. اکنون داریم:

\begin{align} \prod_{n=a}^{a+k-1}n &= \prod_{i=1}^k a_i\\ &= \prod_{i=1}^k id_i\\ &= (\prod_{i=1}^k i)(\prod_{i=1}^k d_i)\\ &= k!(\prod_{i=1}^k d_i) \end{align}

چون $(\prod_{i=1}^k d_i)$ عددی طبیعی است پس $k!$ حاصلضرب عددهایمان را می‌شمارد و در نتیجه تقسیم حاصلضربِ $k$ عدد پشتِ‌سرهم بر $k!$ بخشپذیر است.

بیایید یک نمونه برداریم. ۶ عدد پشتِ‌سرهم با شروع از ۵ را در نظر بگیرید. این عددها ۵، ۶، ۷، ۸، ۹ و ۱۰ هستند. یک گزینش ممکن عبارت است از

$$a_1=7, a_2=10, a_3=9, a_4=8, a_5=5, a_6=6$$

اما این پاسخ کامل نیست. همان‌گونه که آقای @amir7788 در دیدگاهی در زیر نوشتند این نوع گزینش همواره ممکن نیست. علت اینکه این راه‌حل در مورد مثال ایشان، ۶ عدد پشت‌سرهم با شروع از ۴۰، کار نکرد در واقع این است که در یک خط از اثبات‌مان در حال پرش (gap، به پست https://math.irancircle.com/23271 نگاه کنید) هستیم. این خط در واقع جایی است که با صحبت از مضرب‌های ۲ و ۴ نتیجهٔ کلی گرفتیم.

درست است که اثبات کامل ارائه ندادیم ولی یک گام به جلو پیش رفتیم. اگر روی این اثبات کار کنید و بخواهید آن را کامل کنید، در نهایت به چیزی می‌رسید که آقای @amir7788 به صورت کوتاه و مفید در پاسخی در زیر قرار دادند. پس به جای تکمیل این اثبات، برایتان اثبات دیگری قرار می‌دهم.

روش دوم:

بیایید از استقرای ریاضی استفاده کنیم. روشی که می‌خواهیم بنویسیم شبیه به استفادهٔ دو حلقهٔ for در داخل هم در برنامه‌نویسی است. گزارهٔ $p(a,k)$ (دارای دو اندیس طبیعی است) را این تعریف کنید که «حاصلضرب $k$ عدد پشت‌سرهم با شروع از $a$ بر $k!$ بخشپذیر است».

• توجه کنید که برای $k=1$ گزارهٔ $p(k,a)$ برای هر $a$ دلخواهی برقرار است زیرا یعنی «عدد $a$ بر ۱ بخشپذیر است» که بدیهی است.

• فرض کنید گزارهٔ $p(a,k)$ برای $k$های کوچکتر یا مساویِ $n-1$ برقرار است. اکنون می‌خواهیم $p(a,n)$ را نتیجه بگیریم.

• توجه کنید که برای $a=1$ گزارهٔ $p(a,n)$ برقرار است زیرا یعنی «عدد $n!$ بر $n!$ بخشپذیر است» که بدیهی است.

• فرض کنید که برای $a$های کوچکتر یا مساویِ $m-1$ برقرار است. اکنون می‌خواهیم $p(m,n)$ را نتیجه بگیریم.

• توجه کنید که

\begin{align} \prod_{i=m}^{m+n-1}i &= m(m+1)(m+2)\dots (m+n-2)(m+n-1)\\ &= m(m+1)(m+2)\dots (m+n-2)\Big((n)+(m-1)\Big)\\ &= n\Big(m(m+1)(m+2)\dots (m+n-2)\Big)+(m-1)\Big(m(m+1)(m+2)\dots (m+n-2)\Big)\\ &= n\prod_{i=m}^{m+n-2}i+\prod_{i=m-1}^{m+n-2}i \end{align}

اما با توجه به فرض استقرای درونی داریم که $\prod_{i=m-1}^{m+n-2}i$ که ضربِ $n$ عدد پشت‌سرهم با شروع از $m-1$ است بنا به گزارهٔ $p(m-1,n)$ بر $n!$ بخشپذیر است و بنا به فرض استقرای بیرونی، $\prod_{i=m}^{m+n-2}i$ که ضربِ $n-1$ عدد پشت‌سرهم با شروع از $m$ است به خاطر گزارهٔ $p(m,n-1)$ بر $(n-1)!$ بخشپذیر است. که با کنار هم گذاشتن این دو و برابری‌ای که به دست آوردیم بخشپذیر بودنِ $\prod_{i=m}^{m+n-1}i$ بر $n!$ را نتیجه می‌دهد. و این استقرای درونی را ثابت می‌کند که اثبات استقرای درونی (حکم) استقرای بیرونی را ثابت می‌کند. پس گزارهٔ $p(a,k)$ برای هر $k$ و $a$ طبیعی‌ای برقرار است.

شاید بپرسید ایدهٔ روش دوم از کجا می‌آید، به اینکه چگونه با استقرای ریاضی و کمک گرفتن از رابطهٔ بازگشتیِ $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$ ثابت می‌کردید که $\binom{n}{k}$ عددی صحیح است فکر کنید.

Comments

@AmirHosein.  با فرض اینکه 6 تا عدد 15, 16, 17, 18, 19  و 20 باشه aها چگونه معرفی می کنید؟

---

@amir7788 از دیدگاه و مثال خوبی که زدید بسیار سپاسگزارم. درست است، در این نمونه‌ای که آوردید انتخاب به روشی که گفتم ممکن نیست و مجبور هستیم که برای ۲ و ۵ یا ۳ و ۵ یک عدد را برداریم. بنابراین این اثبات کامل نیست.