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

سوالات مربوط به سیگما

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

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

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

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

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

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

$(i+1{)}^{k+1}=\sum _{j=0}^{k+1}\left(\begin{array}{c}k+1\\ j\end{array}\right)i^j$

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

$(x+1{)}^n=\sum _{i=0}^n\left(\begin{array}{c}n\\ i\end{array}\right)x^i$

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

$\sum _{i=1}^n(i+1{)}^{k+1}=\sum _{i=1}^n(\sum _{j=0}^{k+1}\left(\begin{array}{c}k+1\\ j\end{array}\right)i^j)=\sum _{j=0}^{k+1}\left(\begin{array}{c}k+1\\ j\end{array}\right)\sum _{i=1}^n{i}^j$

$S_{k+1}(n+1)-1=\sum _{i=0}^{k+1}\left(\begin{array}{c}k+1\\ j\end{array}\right)S_j(n)$

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

$S_{k+1}(n)+(n+1{)}^{k+1}-1=\sum _{j=0}^k\left(\begin{array}{c}k+1\\ j\end{array}\right)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}\left(\begin{array}{c}k+1\\ j\end{array}\right)S_j(n)=(k+1)S_k(n)$

$S_k(n)=\frac{1}{k+1}((n+1{)}^{k+1}-\sum _{j=0}^{k-1}\left(\begin{array}{c}k+1\\ j\end{array}\right)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}\left(\begin{array}{c}k+1\\ j\end{array}\right)*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}\left(\begin{array}{c}k+1\\ j\end{array}\right)*S_j(-1)-1)=\frac{1}{k+1}((-1+1{)}^{k+1}-\sum _{j=1}^{k-1}\left(\begin{array}{c}k+1\\ j\end{array}\right)*0-\left(\begin{array}{c}k+1\\ 0\end{array}\right)S_0(-1)-1)=0$

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

[[۱]]

[[۲]]

[[۳]]