دورهمی طرح و حل مساله ریاضی/سوالات مربوط به سیگما

طرح و حل مساله

منابع

راوی: تارا دالایی

راجع به این موضوع در ۱ جلسه صحبت شد: سه شنبه، ۲۰ شهریور ۱۴۰۳

گزارشی از مطالب کلاس

می خواهیم یک فرمول ریاضی مربوط به جمع توان های k اعداد 1 تا n را به صورت بازگشتی درآوریم. ابتدا با فرمول زیر شروع می کنیم:

$S_{k}(n)=\sum _{i=1}^{n}i^{k}$

همچنین قضیه زیر را نیز میدانیم:

$(i+1)^{k+1}=\sum _{j=0}^{k+1}{\begin{pmatrix}k+1\\j\end{pmatrix}}i^{j}$

این قضیه را می توان به صورت زیر نیز نوشت:

$(x+1)^{n}=\sum _{i=0}^{n}{\begin{pmatrix}n\\i\end{pmatrix}}x^{i}$

حال میخاهیم این قضیه را به فرمول جمع توان k اعداد 1 تا n ر برسانیم:

$\sum _{i=1}^{n}(i+1)^{k+1}=\sum _{i=1}^{n}(\sum _{j=0}^{k+1}{\begin{pmatrix}k+1\\j\end{pmatrix}}i^{j})=\sum _{j=0}^{k+1}{\begin{pmatrix}k+1\\j\end{pmatrix}}\sum _{i=1}^{n}i^{j}$

$S_{k+1}(n+1)-1=\sum _{i=0}^{k+1}{\begin{pmatrix}k+1\\j\end{pmatrix}}S_{j}(n)$

فرمول بالا را می توان به صورت زیر نوشت:

$S_{k+1}(n)+(n+1)^{k+1}-1=\sum _{j=0}^{k}{\begin{pmatrix}k+1\\j\end{pmatrix}}S_{j}(n)+S_{k+1}(n)$

یک نکته وجود دارد و آن این است که اگر P و Q دو چند جمله ای باشد و تعداد جواب های معادله P=Q از maxDegree{P, Q} بیشتر شود، آنگاه P با Q هم ارز است. یعنی دو چند جمله ای یکسان می باشند.

$(n+1)^{k+1}-1-\sum _{j=0}^{k-1}{\begin{pmatrix}k+1\\j\end{pmatrix}}S_{j}(n)=(k+1)S_{k}(n)$

$S_{k}(n)={\frac {1}{k+1}}((n+1)^{k+1}-\sum _{j=0}^{k-1}{\begin{pmatrix}k+1\\j\end{pmatrix}}S_{j}(n)-1)$

بنابراین توانستیم این فرمول را تبدیل به یک رابطه بازگشتی کنیم.

مطالب تکمیلی

حال می خواهیم چند ادعا را به کمک استقرا ثابت کنیم:

1) ادعا : برای هر k ، داریم:

$S_{k}(0)=0$

اثبات: با استقرای قوی داریم:

برای k = 0,1 این قضیه برقرار است. فرض می کنیم تا j < k این تساوی برقرار باشد و

$S_{j}(0)=0$

$S_{k}(0)={\frac {1}{k+1}}((0+1)^{k+1}-\sum _{j=0}^{k-1}{\begin{pmatrix}k+1\\j\end{pmatrix}}*0-1)=0$

2) حدس : برای هر k>= 1 :

$S_{k}(-1)=0$

اثبات : با استقرای قوی : برای k=1,2,3 بررسی شد و درست بود.

$S_{k}(-1)={\frac {1}{k+1}}((-1+1)^{k+1}-\sum _{j=0}^{k-1}{\begin{pmatrix}k+1\\j\end{pmatrix}}*S_{j}(-1)-1)={\frac {1}{k+1}}((-1+1)^{k+1}-\sum _{j=1}^{k-1}{\begin{pmatrix}k+1\\j\end{pmatrix}}*0-{\begin{pmatrix}k+1\\0\end{pmatrix}}S_{0}(-1)-1)=0$

منابع برای مطالعه بیشتر

[[۱]]

[[۲]]

[[۳]]