یک روش برای محاسبهی مجموعِ توانها
میخواهیم مجموعهایی از جنس زیر را (برای عدد طبیعی $k$) بررسی کنیم:
\[S(n) = 1^k + 2^k + 3^k + \cdots + n^k\]یک اصل راهنما: حلِ نسخههای سادهترِ مسئله
جورج پولیا، در توصیفِ هنرِ حلِ مسئله، توصیهای بسیار ساده اما کلیدی دارد:
اگر مسئلهای سخت است،
سعی کن نسخهای سادهتر از آن را حل کنی.
ایده این نیست که از مسئله فرار کنیم؛ بلکه این است که ساختار پنهان آن را در یک محیطِ سادهتر ببینیم. در مسئلهی ما، سادهترین نسخه کدام است؟
سادهترین حالت: توانِ یک
اگر $k = 1$ باشد، مجموعِ ما به شکل زیر درمیآید:
\[1^1 + 2^1 + 3^1 + \cdots + n^1 = 1 + 2 + 3 + \cdots + n.\]این مجموع را تقریباً همه میشناسند. بیایید این مجموع را $A$ بنامیم:
\[A = 1 + 2 + 3 + \cdots + n.\]حرکتِ کلیدی این است که همان مجموع را یک بار دیگر، اما با چیدمانی متفاوت بنویسیم:
\[A = n + (n-1) + (n-2) + \cdots + 1.\]هیچ جملهی جدیدی اضافه نشده، هیچ جملهای حذف نشده؛ فقط ترتیب عوض شده است. حالا این دو نسخه را زیرِ هم میگذاریم و جملههای همردیف را با هم جمع میکنیم:
\[\begin{aligned} A &= 1 \ \ \ + 2 \ \ \ + 3 \ \ \ + \cdots + n \\ A &= n + (n-1) + (n-2) + \cdots + 1 \end{aligned}\]آنچه فوراً دیده میشود این است که:
- $1 + n = n+1$
- $2 + (n-1) = n+1$
- $3 + (n-2) = n+1$
و این الگو تا آخر ادامه دارد. یعنی هر جفتِ زیرِ هم، صرفنظر از جایگاهش، به یک عدد ثابت میرسد. از اینجا به بعد، محاسبه تقریباً خودبهخود انجام میشود. چون:
- تعدادِ این جفتها برابر $n$ است،
- و مقدارِ هر جفت برابر $n+1$.
پس وقتی دو نسخهی $A$ را جمع میکنیم:
\[2A = n(n+1).\]و بنابراین:
\[A = \frac{n(n+1)}{2}.\]گام بعد: بررسی توانِ دو
حالا طبیعی است که یک پله بالاتر برویم و مجموعِ توانِ دو را بررسی کنیم:
\[1^2 + 2^2 + 3^2 + \cdots + n^2.\]سؤال این است: آیا میتوانیم دقیقاً همان ایدهی قبلی را اینجا هم بهکار ببریم؟
بیایید امتحان کنیم.
تلاش اول: همان بازنویسیِ قبلی
فرض کنیم:
\[A = 1^2 + 2^2 + 3^2 + \cdots + n^2.\]مثل قبل، همان مجموع را از آخر به اول مینویسیم:
\[A = n^2 + (n-1)^2 + (n-2)^2 + \cdots + 1^2.\]حالا دو نسخه را زیرِ هم میگذاریم:
\[\begin{aligned} A &= 1^2 \ \ \ + 2^2 \ \ \ + 3^2 \ \ \ + \cdots + n^2 \\ A &= n^2 + (n-1)^2 + (n-2)^2 + \cdots + 1^2 \end{aligned}\]و مثل قبل، جملههای همردیف را با هم جمع میکنیم. در این حالت، جمعِ جملههای همطراز دیگر ثابت نیست:
- $1^2 + n^2 = 1 + n^2$
- $2^2 + (n-1)^2 = 4 + (n-1)^2$
- $3^2 + (n-2)^2 = 9 + (n-2)^2$
و بهطور کلی: \(i^2 + (n+1-i)^2\) که واضح است برای $i$های مختلف، مقدارهای متفاوتی میدهد. پس برخلاف حالتِ توانِ یک با یک عدد ثابتِ تکرارشونده روبهرو نیستیم. در نتیجه جمعکردنِ دو نسخهی $A$ راه بهجایی نمیبرد.
یک ایدهی دیگر: تفاضلِ جملههای متوالی (Telescoping)
قبل از اینکه سراغ توانِ دو برویم، یک ایدهی خیلی مفید را معرفی کنیم که بعدها برای توانهای بالاتر هم به کار میآید.
ایده این است:
بهجای اینکه خودِ مجموع را مستقیم حساب کنیم،
چیزی را پیدا کنیم که جمعِ تفاضلهای متوالیاش آن مجموع را بسازد.
این کار معمولاً با یک «تابعِ کمکی» انجام میشود.
حل مجموع قبلی با ایدهی جدید
اگر هدف ما مجموعِ توانِ یک باشد، یعنی:
\[1 + 2 + \cdots + n,\]طبیعی است که دنبال تابعی بگردیم که اختلافِ دو جملهی پشتِ سرِ همِ آن، یک عبارتِ خطی (چند جملهای درجهی ۱ بر حسب $n$) بدهد.
سادهترین گزینه:
\[G(n) = n^2.\]چون اختلافِ مربعها عبارتِ خطی تولید میکند.
تعریف کمیتِ تفاضلی
تعریف میکنیم:
\[F(n) = n^2 - (n-1)^2.\]این مقدار را باز میکنیم:
\[F(n) = n^2 - (n^2 - 2n + 1) = 2n - 1.\]پس:
\[2n - 1 = n^2 - (n-1)^2.\]جمع کردنِ تفاضلها: تلسکوپی شدن
حالا این رابطه را برای $n=1$ تا $n$ جمع میکنیم:
\[\sum_{k=1}^n (2k-1) = \sum_{k=1}^n \bigl(k^2-(k-1)^2\bigr).\]سمت راست «تلسکوپی» میشود، چون جملهها همدیگر را حذف میکنند:
\[(1^2-0^2) + (2^2-1^2) + (3^2-2^2) + \cdots + (n^2-(n-1)^2) = n^2.\]پس به نتیجهی ساده میرسیم:
\[\sum_{k=1}^n (2k-1) = n^2.\]استخراج مجموعِ 1 تا $n$ از این رابطه
سمت چپ را بازنویسی میکنیم:
\[\sum_{k=1}^n (2k-1) = 2\sum_{k=1}^n k - \sum_{k=1}^n 1 = 2(1+2+\cdots+n) - n.\]اگر مثل قبل بگذاریم:
\[A = 1+2+\cdots+n,\]آنگاه داریم:
\[2A - n = n^2.\]پس:
\[2A = n^2 + n = n(n+1), \qquad A = \frac{n(n+1)}{2}.\]همان ایده برای توانِ دو: این بار با مکعبها
حالا میخواهیم همین ایدهی تلسکوپی را برای محاسبهی
\[1^2 + 2^2 + \cdots + n^2\]بهکار ببریم.
اگر در توانِ یک از مربعها استفاده کردیم، اینجا طبیعی است یک پله بالاتر برویم و بگذاریم:
\[G(n) = n^3.\]و مثل قبل تعریف کنیم:
\[F(n) = G(n) - G(n-1) = n^3 - (n-1)^3.\]تلسکوپی شدنِ جمعِ Fها
جمعِ $F(1)$ تا $F(n)$ را در نظر بگیرید:
\[F(1) + F(2) + \cdots + F(n) = \sum_{k=1}^n \bigl(G(k)-G(k-1)\bigr).\]اگر آن را جملهبهجمله بنویسیم:
\[\begin{aligned} &\bigl(G(1)-G(0)\bigr) + \bigl(G(2)-G(1)\bigr) + \bigl(G(3)-G(2)\bigr) + \cdots + \bigl(G(n)-G(n-1)\bigr) \end{aligned}\]میبینیم که همهی جملههای میانی حذف میشوند و فقط ابتدا و انتها باقی میماند:
\[F(1)+F(2)+\cdots+F(n) = G(n)-G(0).\]و چون $G(0)=0^3=0$ داریم:
\[\sum_{k=1}^n F(k) = n^3.\]باز کردنِ $F(n)$: ظهورِ توانِ دو
حالا $F(n)$ را باز میکنیم:
\[F(n) = n^3 - (n-1)^3 = n^3 - \bigl(n^3 - 3n^2 + 3n - 1\bigr) = 3n^2 - 3n + 1.\]پس برای هر $n$:
\[3n^2 - 3n + 1 = n^3 - (n-1)^3.\]جمع کردن از ۱ تا $n$
دو طرف را از $1$ تا $n$ جمع میکنیم:
\[\sum_{k=1}^n (3k^2 - 3k + 1) = \sum_{k=1}^n \bigl(k^3-(k-1)^3\bigr) = n^3.\]سمت چپ را تفکیک میکنیم:
\[3\sum_{k=1}^n k^2 \;-\; 3\sum_{k=1}^n k \;+\; \sum_{k=1}^n 1 \;=\; n^3.\]یعنی:
\[3\sum_{k=1}^n k^2 \;-\; 3\sum_{k=1}^n k \;+\; n \;=\; n^3.\]جدا کردنِ مجموعِ مربعات
از قبل میدانیم:
\[\sum_{k=1}^n k = \frac{n(n+1)}{2}.\]پس آن را جایگذاری میکنیم:
\[3\sum_{k=1}^n k^2 - 3\cdot\frac{n(n+1)}{2} + n = n^3.\]پس:
\[3\sum_{k=1}^n k^2 = n^3 + \frac{3n(n+1)}{2} - n.\]یکدستسازی میکنیم:
\[n^3 - n = n(n^2-1)=n(n-1)(n+1),\]و همچنین:
\[\frac{3n(n+1)}{2} - n = \frac{3n(n+1)-2n}{2}=\frac{n(3n+1)}{2}.\]پس:
\[3\sum_{k=1}^n k^2 = n^3 - n + \frac{3n(n+1)}{2} = \frac{2n^3-2n + 3n(n+1)}{2}.\]صورت را ساده میکنیم:
\[2n^3-2n + 3n(n+1) = 2n^3-2n + 3n^2 + 3n = 2n^3 + 3n^2 + n = n(2n^2+3n+1) = n(2n+1)(n+1).\]پس داریم:
\[3\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{2}.\]و در نهایت:
\[\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}.\]یک گام دیگر: مجموعِ توانِ سه
همین ایدهی تلسکوپی را میتوان یک بار دیگر هم بهکار برد؛ این بار برای مجموعِ مکعبها.
بهشرط آنکه مجموعِ توانهای پایینتر (توانِ یک و دو) را از قبل بدانیم.
طبیعی است که این بار انتخاب کنیم:
\[G(n) = n^4,\]و مانند قبل تعریف کنیم:
\[F(n) = G(n) - G(n-1) = n^4 - (n-1)^4.\]با باز کردن این تفاضل داریم:
\[F(n) = 4n^3 - 6n^2 + 4n - 1.\]اگر $F(1)$ تا $F(n)$ را جمع کنیم، مثل قبل جمع تلسکوپی میشود و بهسادگی داریم:
\[\sum_{k=1}^n F(k) = n^4.\]اما از طرف دیگر:
\[\sum_{k=1}^n F(k) = 4\sum_{k=1}^n k^3 - 6\sum_{k=1}^n k^2 + 4\sum_{k=1}^n k - \sum_{k=1}^n 1.\]پس رابطهی زیر برقرار است:
\[4\sum_{k=1}^n k^3 - 6\sum_{k=1}^n k^2 + 4\sum_{k=1}^n k - n = n^4.\]از آنجا که مجموعهای توانِ یک و دو را میدانیم، این معادله بهطور یکتا مجموعِ مکعبها را تعیین میکند. با سادهسازی، به فرمولِ نهاییِ مشهور میرسیم:
\[\sum_{k=1}^n k^3 = \left(\frac{n(n+1)}{2}\right)^2.\]الگوی کلی روش
الگوی این روش حالا روشن است.
برای محاسبهی مجموعِ توانِ $k$:
- تابعی از توانِ بالاتر ($n^{k+1}$) انتخاب میکنیم،
- تفاضلِ متوالی آن را حساب میکنیم،
- که به ترکیبی از توانهای $\le k$ میرسد،
- و با جمعِ تلسکوپی و دانستنِ مجموعِ توانهای پایینتر،
مجموعِ مورد نظر بهدست میآید.
به این ترتیب، هر گام روی شانههای گامهای قبلی میایستد.
یک اشارهی کوتاه به تصویر بزرگتر
اگر این روند را ادامه دهیم، الگو تکرار میشود:
- برای توانِ $1$ از مربعها استفاده کردیم،
- برای توانِ $2$ از مکعبها،
- برای توانِ $3$ از توانِ چهار،
- و بهطور کلی، برای توانِ $k$ از $n^{k+1}$.
در هر مرحله، تفاضلِ \(n^{k+1} - (n-1)^{k+1}\) به ترکیبی خطی از توانهای \(1,\; n,\; n^2,\; \dots,\; n^k\) میانجامد و اگر مجموعِ توانهای پایینتر را بدانیم، مجموعِ توانِ $k$ بهطور یکتا تعیین میشود.
پیگیریِ سیستماتیکِ همین ایده، در نهایت به چندجملهایهایی میرسد که به نام چندجملهایهای برنولی شناخته میشوند؛ اما ریشهی همهی آنها دقیقاً همین مشاهدهی سادهی تلسکوپی است.
در یک برگهی دیگر در ادامهی این برگه روشهای دیگری را برای محاسبهی این مجموع میآوریم.