Дискретная производная или Коротко о том, как суммировать ряды

2019-09-27 в 17:21, admin, рубрики: дискретная производная, математика, сумма ряда

Вступление

Бывало когда-нибудь такое, что вы хотите просуммировать какой-то бесконечный ряд, но не можете подобрать частичную сумму ряда? Вы все ещё не пользовались дискретной производной? Тогда мы идём к вам!

Определение

Дискретной производной последовательности $a_n$ назовем такую последовательность $Delta a_n$ , что для любых натуральных $n>1$ выполняется:

$Delta a_n=a_n - a_{n-1}$

Рассмотрим примеры:

$a_n=1\ Delta a_n=a_n - a_{n-1}=1 - 1=0$
$a_n=n\ Delta a_n=a_n - a_{n-1}=n - (n - 1)=1$
$a_n=n^2\ a_n=n^2 - (n - 1)^2=n^2 - (n^2 - 2n + 1)=2n-1$
$a_n=n^3\ Delta{a_n}=n^3 - (n - 1)^3=3n^2 - 3n + 1$
$a_n=k^n\ Delta{a_n}=k^n - k^{n-1}=k^{n-1}(k-1)$

Ну, суть вы поняли. Чем-то напоминает производную функции, правда? Мы поняли как вычислять дискретный производные «простейших» последовательностей. Кхм, но что делать с суммой, разностью, произведением и частным последовательностей? У «обычной» производной есть некоторые правила дифференцирования. Давайте-ка придумаем для дискретной!

Сначала рассмотрим сумму. Логично, что сумма последовательностей это тоже какая-то последовательность. Попробуем найти производную по определению:

$Delta{(a_n + b_n)}=a_n + b_n - (a_{n - 1} + b_{n - 1})=\=a_n - a_{n - 1} + b_n - b_{n - 1}=Delta{a_n} + Delta{b_n}$

Феноменально! Мы получили, что производная суммы последовательностей есть сумма производных этих последовательностей!~~спасибо, кэп~~
Попробуем доказать тоже самое с разностью

$Delta{(a_n - b_n)}=a_n - b_n - (a_{n - 1} - b_{n - 1})=\=a_n - a_{n - 1} -( b_n - b_{n - 1})=Delta{a_n} - Delta{b_n}$

А мы переходим к произведению!
Аналогично, найдем по определению:

$Delta{(a_nb_n)}=a_nb_n - a_{n-1}b_{n-1}=\=a_nb_n-a_{n}b_{n-1} + a_nb_{n-1} - a_{n-1}b_{n-1}=\=a_n(b_n - b_{n-1}) + b_{n-1}(a_n - a_{n-1})=\=a_nDelta{b_n} + b_{n-1}Delta{a_n}$

Круто, правда? Рассмотрим частное:

$Delta(frac{a_n}{b_n})=frac{a_n}{b_n} - frac{a_{n - 1}}{b_{n-1}}=frac{a_nb_{n-1}-a_{n-1}b_n}{b_nb_{n-1}}=\=frac{a_nb_{n-1}-a_nb_n+a_nb_n-a_{n-1}b_n}{b_nb_{n-1}}=\=frac{b_nDelta{a_n}-a_nDelta{b_n}}{b_nb_{n-1}}$

Cool...
Но это все производная. Может, есть и дискретная первообразная? Оказывается, есть!

Еще определения

Дискретной первообразной последовательности $a_n$ называют такую последовательность $A_n$ что для любых натуральных $n>1$ выполняется:

$a_n=Delta A_n$

$a_n=1\ Delta A_n=a_n iff A_n=n$
$a_n=n\ n=frac{2n-1}{2}+frac{1}{2}=frac{Delta n^2 + Delta n}{2}=frac{Delta (n^2 + n)}{2}\ Delta A_n=a_n iff A_n=frac{n^2+n}{2}$

С этим понятно. Го придумаем аналог Ньютона-Лейбница!

$sum_{i=1}^{n}a_i=a_1 + a_2+a_3+...+a_n=\=A_1 - A_0 + A_2 - A_1 +... +A_n - A_{n-1}=\=A_{n} - A_0$

Да ладно! Вот это ~~прикол~~ совпадение! А теперь то же самое покрасивее:

$sum_{i=1}^n a_=sum_{i=1}^n Delta A_i=A_ibigg|_{1}^{n}$

И обобщим на множество натуральных чисел от $a$ до $b$ :

$sum_{i=a}^{b}f(i)=F_ibigg|_a^b$

Применение

Кто помнит ту самую формулу для суммы ряда квадратов натуральных чисел от $1$ до $n$ ? А вот и я не помню. Давайте-ка ее выведем!
Но для начала надо найти первообразную для последовательности $a_i=i^2$ :

$i^2=(3i^2-3i+1)frac{1}{3} + i - frac{1}{3}=(3i^2-3i+1)frac{1}{3} + i - frac{1}{3}=\=frac{1}{3}Delta i^3 + frac{1}{2}Delta(i^2 + i) - frac{1}{3}Delta i=\=Deltafrac{2i^3 + 3i^2+3i-2i}{6}=Deltafrac{2i^3+3i^2+i}{6}$

А теперь, собственно, сама сумма:

$sum_{i=1}^{n}i^2=frac{2i^3+3i^2+i}{6}bigg|_0^n=frac{2n^3+3n^2+n}{6}$

Как насчет суммы кубов?
Сначала вычислим

$Delta i^4=i^4 - (i-1)^4=i^4-(i^4 - 4 i^3 + 6i^2-4i+1)=4i^3 - 6i^2 +4i-1$

Первообразная для $i^3$ :

$i^3=frac{1}{4}(4i^3-6i^2+4i-1)+frac{3}{2}i^2-i+frac{1}{4}=\=frac{Delta i^4}{4}+frac{3}{2}Delta{frac{2i^3+3i^2+i}{6}}-Delta{frac{i^2+i}{2}}+frac{Delta{i}}{4}=\=Delta{frac{i^4+2i^3+3i^2+i-2i^2-2i+i}{4}}=Delta{frac{i^4+2i^3+i^2}{4}}=\=Delta{bigg(frac{i(i+1)}{2}bigg)^2}\ sum_{i=1}^{n}i^3=bigg(frac{i(i+1)}{2}bigg)^2bigg|_0^n=bigg(frac{n(n+1)}{2}bigg)^2$

Кхм, казалось бы, ничего сложного…

Для продвинутых

Не всегда так просто найти интеграл, правда? Что мы делаем в трудных случаях? Правильно, интегрируем по частям. Быть может, есть аналог? Не буду вас томить, он есть, и сейчас мы его выведем.

Допустим, надо вычислить сумму ряда

$p=const\sum_{i=1}^{n}ip^{i}=?$

Что делать? Вряд ли вы сможете так просто подобрать дискрентную первообразную к последовательности. Давайте смотреть.
Мы уже знаем, что:

$Delta{(f(n)g(n))}=f(n)Delta{g(n)} + g(n-1)Delta f(n)$

Тогда

$sum_{i=a}^{b}Delta (f(i)g(i))=sum_{i=a}^b f(i)Delta g(i) + sum_{i=a}^{b}g(i-1)Delta f(i)iff \ iffsum_{i=a}^b f(i)Delta g(i)=sum_{i=a}^{b}Delta (f(i)g(i)) -sum_{i=a}^{b}g(i-1)Delta f(i)$

А теперь один нетривиальный шаг:

$sum_{i=a}^{b}Delta (f(i)g(i))=f(a)g(a)-f(a-1)g(a-1)+f(a+1)g(a+1) - f(a)g(a)+\ + ... + f(b)g(b)-f(b-1)g(b-1)=f(b)g(b)-f(a-1)g(a-1)$

Подставим в полученное до этого равенство:

$sum_{i=a}^b f(i)Delta g(i)=f(b)g(b)-f(a-1)g(a-1) -sum_{i=a}^{b}g(i-1)Delta f(i)$

Финита ля комедия.

Найдем ту самую сумму:

$sum_{i=1}^n{ip^{i}}=S_n\ p^i=Delta{frac{p^{i+1}}{p-1}}\ S_n=sum_{i=1}^n iDelta{frac{p^{i+1}}{p-1}} \$

Кому-то может показаться, будто формула стала еще более громоздкой, и мы только усложнили себе работу. Но это не так. Пусть $f(i)=i, g(i)=frac{p^{i+1}}{p-1}$ , тогда:

$sum_{i=1}^n f(i)Delta g(i)=f(n)g(n)-f(0)g(0) -sum_{i=1}^{n}g(i-1)Delta f(i)=\=nfrac{p^{n+1}}{p-1} - 0 -sum_{i=1}^{n}frac{p^{i}}{p-1}=nfrac{p^{n+1}}{p-1}-bigg(frac{1}{p-1}sum_{i=1}^{n}p^ibigg)=\=nfrac{p^{n+1}}{p-1}-bigg(frac{1}{p-1}sum_{i=1}^{n}Delta{frac{p^{i+1}}{p-1}}bigg)=\=nfrac{p^{n+1}}{p-1}-bigg(frac{p^{n+1}-p}{(p-1)^2}bigg)=frac{np^{n+2}-(n+1)p^{n+1}+p}{(p-1)^2}$

Прикольная задачка

Предлагаю попрактиковаться с этим на примере задачки с отбора в Tinkoff Generation на курсы по Machine Learning. Вот сама задачка:

Вы устали решать задачки с отборов на курсы Tinkoff Generation и решили устроить перерыв, посмотрев несколько серий нового сериала, о котором все говорят.

Вы начинаете смотреть все серии, начиная с первой. Каждая серия длится один час. После просмотра очередной серии, вы с постоянной вероятностью ppp начинаете смотреть следующую, иначе ваш перерыв заканчивается, и вы возвращаетесь к работе.

Голод, сон и прочие нужды вас не останавливают, а в сериале бесконечное количество серий; в теории, ваш перерыв может длиться бесконечно.

Сколько в среднем будет длиться ваш перерыв?

Строго говоря, здесь нам нужно найти математическое ожидание. Давайте разбираться.

Решение

Вероятность того, что перерыв будет длиться 1 час, равна:

$P(1)=1 - p$

2 часа

$P(2)=p(1-p)\...$

n часов:

$P(n)=p^{n-1}(1-p)$

Тогда математическое ожидание равно:

$E[X]=limlimits_{n to infty}{sum_{i=1}^ni*P(i)}=limlimits_{n to infty}{sum_{i=1}^ni*(1-p)p^{i-1}}=\=(1-p)limlimits_{n to infty}{sum_{i=1}^ni*p^{i-1}}$

Знакомо, правда?
Мы уже находили, что

$sum_{i=1}^nip^{i}=frac{np^{n+2}-(n+1)p^n+1}{(p-1)^2}$

тогда совсем очевиден нужный нам ряд:

$sum_{i=1}^nip^{i-1}=frac{1}{p}sum_{i=1}^nip^{i}=frac{np^{n+1}-(n+1)p^n+1}{(p-1)^2}$

И задача сводится к нахождению предела последовательности

$limlimits_{ntoinfty}frac{np^{n+1}-(n+1)p^n+1}{(p-1)^2}$

где $p<1$ , так как $p$ — вероятность события.
Докажем теперь, что

$limlimits_{ntoinfty}np^{n+1}=0, space limlimits_{ntoinfty}p^n(n+1)=0$

$f(x)=p^{x+1}x, space x in !R\ p=frac{1}{q}, space 0< p< 1 iff q>1\ limlimits_{xtoinfty}{f(x)}=limlimits_{xtoinfty}{p^{x+1}x}=limlimits_{xtoinfty}{frac{x}{q^{x+1}}}=\=limlimits_{xtoinfty}{frac{x'}{(q^{x+1})'}}=limlimits_{xtoinfty}{frac{1}{q^{x+1}ln q}}=0\ limlimits_{xtoinfty}f(x)=0 implieslimlimits_{ntoinfty}f(n) iff limlimits_{ntoinfty}np^{n+1}=0$
$f(x)=p^{x}(x+1), space x in !R\ p=frac{1}{q}, space 0< p< 1 iff q>1\ limlimits_{xtoinfty}{f(x)}=limlimits_{xtoinfty}{p^{x}(x+1)}=limlimits_{xtoinfty}{frac{x+1}{q^{x}}}=\=limlimits_{xtoinfty}{frac{(x+1)'}{(q^{x})'}}=limlimits_{xtoinfty}{frac{1}{q^{x}ln q}}=0\ limlimits_{xtoinfty}f(x)=0 implieslimlimits_{ntoinfty}f(n) iff limlimits_{ntoinfty}(n+1)p^{n}=0$