Аналитическое суммирование конечных последовательностей

[Random Drifter]

Ende
Выделено из темы «Нахождение "замкнутых" формул последовательностей»

madschumacher в сообщении #1135649 писал(а):

Mihr в сообщении #1135647 писал(а):

Универсального алгоритма для конечных сумм и рядов произвольного вида, как я понимаю, нет.

Это так странно, учитывая, что для неопределенных интегралов он существует.

Между прочим, хорошая мысль! Действительно, почему бы не попробовать свести одну задачу к другой. Пусть у нас есть бесконечный ряд $\sum\limits_{k=0}^{\infty}f(k)$, в общем случае не обязательно сходящийся. Требуется найти замкнутую формулу для суммы $\sum\limits_{k=0}^{n-1}f(k)$.
Обозначим $g(n)=\sum\limits_{k=0}^{n-1}f(k)$. Здесь $g(n)$ можно назвать $n$-й частичной суммой ряда. Почему именно $n$-й? Потому что в данную сумму входит ровно $n$ первых членов ряда. Я знаю, в большинстве случаев принято искать общую формулу вот для такой суммы: $\sum\limits_{k=0}^{n}f(k)$, в которую входит $n+1$ член, от $0$ до $n$. В некоторых случаях это действительно удобно, и о них мы поговорим позже. Но на самом деле это не принципиально: если найдена замкнутая формула для $n$ членов, нетрудно по ней построить аналогичную формулу и для $n+1$ членов. И наоборот.

Далее нужно обратить внимание на следующее: очевидно, что $g(n+1)-g(n)=f(n)$. Такое уравнение называется линейным неоднородным разностным уравнением первого порядка. Про такие уравнения известно, что в "однородном" случае (когда правая часть нулевая) они решаются легко и просто. Потому что существует метод их решения. Про неоднородные же уравнения можно сказать, что общее решение неоднородного уравнения получается как сумма общего решения однородного уравнения и какого-либо частного решения неоднородного уравнения. Однако же общих способов определения частного решения не существует (или не известно)! И это понятно: если бы они существовали, существовал бы и алгоритм по свертыванию частичных сумм в замкнутые формулы, типа того, который существует для интегралов. Тем не менее, для некоторых специальных видов функции в правой части уравнения существуют стандартные приемы решения этого уравнения. Например, всем известный телескопический ряд $f(k)=1/(k+1)/(k+2)$, который легко "раскладывается" на две "половины": $f(k)=1/(k+1)-1/(k+2)$. Здесь сразу же очевидно, что $g(n)=-1/(n+1)$. Т.е. решение сразу готово.

Кстати, глядя на разностное уравнение $g(n+1)-g(n)=f(n)$ можно подумать, что функция $g(n)$ может быть найдена с точностью до константы. Т.е. если $g(n)$ является решением уравнения, то и $g(n)+C$ также будет решением, где $C$ - некоторая константа. На самом деле, это не так! Ведь мы уже договорились, что $g(n)$ означает сумму $n$ первых членов ряда. В таком случае сумма нуля членов должна равняться нулю, т.е. должно быть верным $g(0)=0$. Кажется, что не всегда это возможно, например, не в случае $g(n)=-1/(n+1)$. На самом деле, дело в том, что решение было найдено не верно! Правильное решение выглядит так: $g(n)=1-1/(n+1)=n/(n+1)$.

Ок, если общих методов не существует, значит, остается только перебрать все возможные типы специальных функций и посмотреть, к какому из них относится наша функция. Затем применить к ней соответствующий прием и записать решение. Либо констатировать, что решения нет (в элементарных функциях), если ни к какому не относится. Наверняка, автоматизированные сервисы именно так и работают. Быть может, однако, здесь можно придумать что-то еще...

$$$$***$$$$

1) Преобразование Фурье
Найдем преобразование Фурье для обеих частей нашего разностного уравнения!
Применяя преобразование, получим $F($\omega$)=e^{i\omega}G($\omega$)-G($\omega$)$.
Здесь большими буквами обозначены фурье-образы для функций, обозначенных соответствующими маленькими буквами.
Решаем это уравнение и получаем $G($\omega$)=F($\omega$)/(e^{i\omega}-1)$.
Ну, и всё. Осталось сделать только обратное преобразование. Обратное преобразование - всегда некоторый интеграл. Если он выражается в элементарных функциях, значит, и функция $g(n)$ тоже в них выражается. Главное только при решении интеграла не получить исходный ряд. Как говорится, в расследовании главное не выйти на самого себя :)
Можно также оставить этот интеграл, как есть, считая его самого "замкнутой формой".

На самом деле, основная проблема здесь заключается в том, что для большинства функций преобразование Фурье попросту не существует. Оно существует только для нескольких специальных видов функций.

Можно ли то же самое проделать с уравнением, применяя преобразование Лапласа? Здесь я бы уже не был так уверен. Дело в том, что преобразование Лапласа применяется к функциям, равным нулю в отрицательной области. Казалось бы, это не имеет особого значения, поскольку сам интеграл преобразования берется в промежутке от нуля до бесконечности, так что какая разница? Дело в том, однако, что функция $f(x+1)$ получена сдвигом функции $f(x)$ на единицу влево. Значит, у нее появились ненулевые значения в отрицательной области. Если мы затем начнем ее интегрировать от нуля до бесконечности, не потеряем ли мы часть значений? Это ведь совсем не то же самое, что сдвинуть функцию $f(x)$ вправо. Потому что в этом случае ее значения на отрезке $[0;1]$ станут равны нулю, и в этом случае действительно уже всё равно, от какого значения ее интегрировать: от 0 или от 1.

Короче, я бы в данном случае перестраховался и искал преобразование для какого-нибудь такого уравнения: $f(x)=\eta(x)-\eta(x-1)$. Затем, если решение будет найдено, тогда функцию $g(x)$ можно было бы получить из тождества $g(x)=\eta(x-1)$.

$$$$***$$$$

2) Интегральное уравнение
Можно действовать и более прямолинейно. Представим, что в уравнении $g(n+1)-g(n)=f(n)$ функция $g(n)$ является первообразной для некоторой функции $h(n)$. В таком случае уравнение можно переписать так:
$\[f(x) = \int\limits_x^{x + 1} {h(t)dt} \]$.
Получилось интегральное уравнение относительно неизвестной функции $h(x)$ с известной функцией $f(x)$. Понятно, что если решение этого уравнения существует в элементарных функциях, то... а хотя, нет. Если $h(x)$ - элементарная функция, то ее первообразная - вовсе не обязательно. Тем не менее, ясно, что было бы полезно решить такое уравнение.
Для этого я перепишу уравнение так:
$\[f(x) = \int\limits_0^\infty {K(x,t)h(t)dt} \]$
Здесь функция $K(x,t)$ равна единице, когда $\[x \le t \le x + 1\]$, и нулю во всех остальных случаях.
Такая форма будет эквивалентной хотя бы для положительных значений $x$, а только такие, на самом деле, нас и интересуют. Можно получить и общую форму, верную и для отрицательных значений $x$. Для этого всего лишь нужно поменять нижний предел интеграла с нуля на минус бесконечность. Однако я все-таки остановлюсь на нуле, поскольку дальше этот интеграл будем рассматривать, как свертку двух функций, от которой можно взять преобразование Лапласа. А свертка для преобразования Лапласа формулируется именно в виде интеграла от 0 до бесконечности. Хотя, я не знаю, почему это именно так: на мой взгляд, если сформулировать ее от минус бесконечности до бесконечности, ошибки не произойдет - особенно если считать, что все функции равны нулю в отрицательной области (кроме, конечно, $K$). В случае с преобразованиями Фурье именно так и делают. Но да бог с ним: сформулирую, как принято, чтобы не отклоняться от правил и не наделать ошибок.

Полученное уравнение называют неоднородным уравнением Фредгольма первого рода, функция $K(x,t)$ называется ядром этого уравнения. Полученное уравнение можно решить с помощью преобразования Лапласа, если удастся свести функцию $K(x,t)$ к некоторой функции $q(x-t)$ одного аргумента, потому что в этом случае интеграл этого уравнения станет сверткой двух функций, $q(x)$ и $h(x)$. А преобразование Лапласа от свертки равно произведению лаплас-образов каждой из двух функций $q(x)$ и $h(x)$ по отдельности. Поэтому именно это я дальше и попытаюсь сделать.

Функцию $K(x,t)$ лучше всего будет представить в виде разности двух единичных ступенчатых функций – функций Хевисайда $\theta(x)$.

Во-первых, потому что нужна единая формула для $K$ для всех возможных случаев (а не так, что здесь 1, там 0, и т.д.).
Во-вторых, потому что нужна функция одного аргумента, на место которого можно будет подставить $x-t$, чтобы получилась свертка.
В-третьих, потому что преобразование Лапласа хорошо берется от ступенчатой функции.

Итак, $\[K(x,t) = \theta (x + 1 - t) - \theta (x - t) = q(x - t)\]$, где $\[q(x) = \theta (x + 1) - \theta (x)\]$.
Тогда интегральное уравнение можно переписать так: $\[f(x) = \int\limits_0^\infty {q(x - t)h(t)dt} \]$.
Дальше, как можно догадаться, берем преобразование Лапласа от обеих частей уравнения.
Обозначим:
$F(s)$ - образ функции $f(x)$
$H(s)$ - образ функции $h(x)$
$Q(s)$ - образ функции $q(x)$

При этом $\[Q(s) = {e^s}/s - 1/s = ({e^s} - 1)/s\]$.
Тогда получаем уравнение $F(s)=Q(s)H(s)=H(s)\[({e^s} - 1)/s\]$, решая которое, получаем $\[H(s) = sF(s)/({e^s} - 1)\]$.
На самом деле, этот же результат можно было получить намного короче, если вспомнить, что для случая, когда $g(x)$ является первообразной для $h(x)$, верно $H(s)=sG(s)-g(0)=sG(s)$. А получать $G(s)$ мы уже умеем - это было описано в предыдущем пункте.

Самое интересное - что теперь со всем этим делать. Оригинал для $F(s)$ нам известен - это $f(x)$. Остается получить оригинал для $\[s/({e^s} - 1)\]$, составить свертку для этих двух функций - это и будет "замкнутая форма" для $h(x)$. Проблема в том, что оригинал для $\[s/({e^s} - 1)\]$ (как и для $\[1/({e^s} - 1)\]$) не существует в элементарных функциях. Для $\[1/({e^s} - 1)\]$ это будет, скорее всего, бесконечная сумма дельта-функций Дирака с разной степенью сдвига. Для $\[s/({e^s} - 1)\]$ - что-нибудь и того хуже.
Но я предлагаю не заморачиваться слишком сильно, а сразу брать свою функцию $f(x)$ и идти с ней куда-нибудь на сервис www.wolframalpha.com. Там применить к ней преобразование Лапласа (Laplace transform). Если получилось что-то осмысленное, умножить на $\[s/({e^s} - 1)\]$ или на $\[1/({e^s} - 1)\]$, а затем применить обратное преобразование Лапласа (inverse Laplace transform). Если опять получился результат в элементарных функциях, значит, метод сработал.

$$$$***$$$$

3) Метод операторов
Уравнение $g(n+1)-g(n)=f(n)$ можно переписать в виде $\[\Delta g(n) = f(n)\]$. Здесь $\Delta$ - оператор, означающий взятие от функции ее первой конечной разности: $\[\Delta f(n) = f(n + 1) - f(n)\]$. Этот оператор можно представить в виде $\[\Delta = E - 1\]$, где $E$ - оператор сдвига (т.е. такой, что $Ef(x)=f(x+1)$), $1$ - тождественный оператор, т.е. такой, что ставит функцию в соответствие самой себе: $1f(x)=f(x)$.

Тогда наше уравнение принимает вид $(E-1)g(n)=f(n)$. Решая его, получаем:
$\[g(n) = f(n)/(E - 1) = - (1/(1 - E))f(n) = - (1 + E + {E^2} + {E^3} + ...)f(n) = - \sum\limits_{k = 0}^\infty {f(n + k)} \]$
Получился совершенно точный, но при этом абсолютно бесполезный результат.
Подробнее об элементарной теории операторов можно почитать в книжке Грэхема и Кнута "Конкретная математика" (глава 5: специальные приемы).

$$$$***$$$$

4) Производящая функция $+$ z-преобразование
Этот метод, пожалуй, единственный позволяет получить какие-то конкретные результаты на практике.
Пусть есть последовательность ${a_k}$, где $k=1,2,3,...$.
Производящей функцией такой последовательности называется функция $A(x)$ такая, что $\[A(x) = \sum\limits_{k = 0}^\infty {{a_k}{x^k}} \]$.
При этом сама последовательность ${a_k}$ может быть задана какой-нибудь функцией $f$: $a_k=f(k)$.
Метод начинается с того, что надо как-то получить замкнутую форму для функции $A(x)$. И здесь даже не надо строить иллюзий: никаких общих методов это сделать нет! Возможно, эта задача даже сложнее, чем получить замкнутую формулу для частичной суммы. За исключением некоторых случаев, например, для последовательности ${1/k!}$ получить замкнутую формулу в элементарных функциях в принципе невозможно (сейчас это будет доказано), тогда как производящей функцией этой последовательности является самая обычная экспонента.

Собственно, я даже догадываюсь, с чем связано это затруднение. Получение производящей функции по последовательности - это задача, обратная задаче разложения функции в ряд Тейлора. А обратные задачи в большинстве случаев решаются почему-то труднее прямых. Сравнить, например, интегрирование с дифференцированием. Существует общий метод получить производную ЛЮБОЙ элементарной функции. И даже иногда, если она не элементарная. Однако интеграл от элементарной функции - не всегда элементарная функция.

Кстати, не один я так считаю. Например, Иванов Б. Н. в своей книге "Дискретная математика. Алгоритмы и программы", в главе 3 пишет, что как правило, поиск производящей функции по определению прямыми методами является сложной задачей. Однако заметим, что сама последовательность может быть восстановлена по производящей функции (т.е. обратная задача решается хорошо - мое прим.).

Ничего удивительного, кстати говоря. Как только функция A(x) получена, мы сразу же можем вычислить сумму бесконечного ряда, просто подставив x=1 в A(x) (конечно, если функция A(x) существует в этой точке). Однако в общем случае вычисление бесконечных рядов - задача нетривиальная.

Метод производящей функции, однако, обладает той интересной особенностью, что нет необходимости следить за сходимостью полученного ряда, поскольку символ $x$ в разложении не означает какого-то числа, которое можно было бы подставить на его место. Это просто формальный символ. И тем не менее, метод позволяет получать какие-то содержательные результаты, верность которых затем можно проверять, например, по индукции. Однако прежде чем проверить какой-то результат, его требуется откуда-то получить. Вот это и есть такой метод.

Короче, начинаем с того, что замкнутая форма для $A(x)$ у нас откуда-то уже имеется, на этом не останавливаемся. Тогда коэффициент при $x^n$ в разложении функции $A(x)/(1-x)$ в ряд Тейлора будет равен $\[\sum\limits_{k = 0}^n {{a_k}} \]$. Вот здесь как раз возникает случай, когда суммируется $n+1$ членов ряда, от $0$ до $n$.
На доказательстве этого факта я не останавливаюсь. Можно воспользоваться методом производящего ряда, где для рекуррентной формулы получают соответствующее уравнение в производящих функциях. Получится уравнение, похожее на уравнение для фурье-образов из первого пункта, типа такого: $B(x)=xB(x)+A(x)$. Можно использовать свертку двух последовательностей, одну из которых задать, как {$1,1,1,...$}. Про свертку последовательностей можно почитать в википедии, в статье "Производящая функция последовательности". Само доказательство есть в книге Грэхема и Кнута "Конкретная математика", в главе 7 "Производящие функции". В разделе "Основные маневры" говорится, что "умножение производящей функции на $1/(1-z)$ дает производящую функцию для последовательности частичных сумм исходной посдедовательности". При этом под частичной суммой, очевидно, у них понимается сумма $n+1$ начальных членов.

Короче, вся соль теперь в том, как найти замкнутую форму для коэффициента при $x^n$ в разложении $A(x)/(1-x)$ в ряд Тейлора. В этом может помочь z-преобразование.
По определению, z-преобразование последовательности функций {f(k)}, это функция $F(z)$ такая, что $F(z)=A(1/z)$. z-преобразование существует не для всех видов функций, а только для тех, что растут не быстрее экспоненты, но не суть.

Таким образом, очевидно, что z-преобразование применяется не к одной конкретной функции, а сразу ко всей последовательности. При этом смысл этого преобразования в том, что по функции $F(z)$ можно получить произвольный член последовательности {f(k)} по формуле

$$\[f(k) = \frac{1}{{2\pi i}}\oint\limits_C {F(z){z^{k - 1}}dz} \]$$

. Интеграл берется по любому замкнутому контуру, включающему все особые точки $F(z)$. Спрашивается, зачем нужна функция $f(k)$, если она и так уже имеется по условию? Ни зачем она не нужна! Нужен член последовательности частичных сумм. А это значит, что надо найти z-преобразование вот для такой производящей функции: $A(x)/(1-x)$. А затем применить к нему обратное z-преобразование.

Как видно, поиск частичной суммы ряда опять свелся к некоторому интегралу, пусть и комплексному. Но это не так уж и страшно, как сейчас станет ясно.
Обозначим {$b_k$} последовательность частичных сумм исходной последовательности {$a_k$}. Здесь $b_k=g(k)$, где $g(k)=f(0)+...+f(n)$. Как видно, здесь придется отойти от первоначального определения функции $g(n)$, как суммы $n$ первых членов рядов, и складывать уже $n+1$ начальный член.
Производящей функцией последовательности {$b_k$} обозначим $B(x)$, где $B(x)=A(x)/(1-x)$. Ну а z-преобразование для $B(x)$ обозначим, как $G(z)=B(1/z)$.
Тогда $\[G(z) = B(1/z) = \frac{{A(1/z)}}{{1 - 1/z}} = \frac{{F(z)}}{{1 - 1/z}} = \frac{{zF(z)}}{{z - 1}}\]$,
откуда получаем

$$\[g(k) = \frac{1}{{2\pi i}}\oint\limits_C {G(z){z^{k - 1}}dz} = \frac{1}{{2\pi i}}\oint\limits_C {\frac{{zF(z)}}{{z - 1}}{z^{k - 1}}dz} = \frac{1}{{2\pi i}}\oint\limits_C {\frac{{{z^k}F(z)}}{{z - 1}}dz} \]$$

.

Рассмотрим какой-нибудь пример.

[Random Drifter]

Пример 1.
Пусть $f(k)=k$. Таким образом, нам нужно найти частичную сумму $n+1$ первых членов арифметической прогрессии. $n+1$ - это если считать от нуля. А если считать от единицы, то получится $n$ членов: $0+1+...+n=1+...+n$.
Для такой частичной суммы существует известная замкнутая формула $1+...+n=n(n+1)/2$, по легенде впервые полученная Карлом Гауссом, когда он еще учился в школе. Она-то и будет для нас ориентиром при проверке решения.

Итак, $f(k)=k$.
Тогда
$\[A(x) = \sum\limits_{k = 0}^\infty {k{x^k}} = x\sum\limits_{k = 0}^\infty {k{x^{k - 1}}} = x\sum\limits_{k = 0}^\infty {({x^k})'} = x\left( {\sum\limits_{k = 0}^\infty {{x^k}} } \right)' = x\left( {\frac{1}{{1 - x}}} \right)' = \frac{x}{{{{(1 - x)}^2}}}\]$
И поэтому $F(z)=A(1/z)=A(z)$.
Как видно, вид функции $F(z)$ совпал с видом функции $A(x)$. Можно считать, повезло в каком-то смысле.
При этом $\[G(z) = \frac{{zF(z)}}{{z - 1}} = \frac{{zA(z)}}{{z - 1}} = \frac{{{z^2}}}{{{{(z - 1)}^3}}}\]$.
И тогда $\[\sum\limits_{k = 0}^n k = g(n) = \frac{1}{{2\pi i}}\oint\limits_C {G(z){z^{n - 1}}dz} = \frac{1}{{2\pi i}}\oint\limits_C {\frac{{{z^{n + 1}}}}{{{{(z - 1)}^3}}}dz} \]$.

Теперь нужно как-то решить полученный интеграл. Я думаю, удобнее всего здесь было бы воспользоваться интегральной формулой Коши:

$$\[w({z_0}) = \frac{1}{{2\pi i}}\oint\limits_L {\frac{{w(z)}}{{z - {z_0}}}dz} \]$$

.
Правда, как раз для данного случая эта формула не подойдет, поскольку в точке $z_0$ функция $w$ не существует, и мы ее там вычислить не сможем. Поэтому надо воспользоваться более изощренной версией этой формулы:

$$\[{w^{(m)}}({z_0}) = \frac{{m!}}{{2\pi i}}\oint\limits_L {\frac{{w(z)}}{{{{(z - {z_0})}^{m + 1}}}}dz} \]$$

Здесь смысл такой, что нужно подобрать такое значение $m$, чтобы степень $(z-z_0)$ в знаменателе формулы получилась такой же, как и в нашем примере. Поскольку в нашем примере степень знаменателя равна тройке, нужно выбрать $m=2$, чтобы $m+1=3$. В таком случае, для нашего примера функция $w(z)$ будет равна $w(z)=z^{n+1}$. И нужно затем продифференцировать ее $m=2$ раза и вычислить в точке $z_0=1$. Я не знаю, насколько доступно я всё это объясняю. Тут нет ничего, кроме использования формулы Коши. Только сперва требуется выбрать из них всех наиболее подходящую (с подходящим значением для $m$). Например, если выбрать $m=0$, получится $w(z)=z^{n+1}/(z-1)^2$. А такую функцию в точке $z_0=1$ мы вычислить уже не сможем.

Короче, в нашем случае это будет означать:
$\[\sum\limits_{k = 0}^n k = g(n) = \frac{1}{{2\pi i}}\oint\limits_L {\frac{{{z^{n + 1}}}}{{{{(z - 1)}^3}}}dz} = {\left. {\left( {\frac{{({z^{n + 1}})''}}{{2!}}} \right)} \right|_{z = 1}} = \frac{{(n + 1)n{1^{n - 1}}}}{{2!}} = \frac{{(n + 1)n}}{2}\]$.
Как видно, ответ совпал. Кстати, само z-преобразование является следствием интегральной формулы Коши:
$\[\frac{{{A^{(n)}}(0)}}{{n!}} = \frac{1}{{2\pi i}}\oint\limits_C {\frac{{A(u)}}{{{u^{n + 1}}}}du} = [u = 1/z] = \frac{1}{{2\pi i}}\oint\limits_C {\frac{{F(z)}}{{{{(1/z)}^{n + 1}}}}\frac{{ - 1}}{{{z^2}}}dz} = - \frac{1}{{2\pi i}}\oint\limits_C {F(z){z^{n - 1}}dz} \]$
(Там еще надо как-то учесть смену направления обхода контура, чтобы знак «минус» пропал. Лучше посмотрите это доказательство в каком-нибудь «авторитетном источнике».)
Хотя некоторые каким-то образом выводят z-преобразование из преобразования Лапласа.

Пример 2.
Пусть $f(k)=1/k!$.
Тогда
$A(x)=e^x$,
$F(z)=A(1/z)=e^{1/z}$,
$\[G(z) = \frac{{zF(z)}}{{z - 1}} = \frac{{z{e^{1/z}}}}{{z - 1}}\]$.
И тогда:
$\[\sum\limits_{k = 0}^n {\frac{1}{{k!}}} = g(n) = \frac{1}{{2\pi i}}\oint\limits_C {G(z){z^{n - 1}}dz} = \frac{1}{{2\pi i}}\oint\limits_C {\frac{{{z^n}{e^{1/z}}}}{{z - 1}}dz} \]$.
В первую очередь надо опять попробовать применить формулу Коши. Формула Коши в данном случае нам скажет, что искомый ряд должен быть равен $e$ (т.е. числу Эйлера или основанию натурального логарифма). Уже понятно, что такой результат ошибочен: числу $e$ равен бесконечный ряд $\[\sum\limits_{k = 0}^\infty {\frac{1}{{k!}}} \]$. Но нам-то нужна частичная сумма такого ряда. Интересно, где же здесь ошибка? Вероятно, функция $w(z)=z^ne^{1/z}$ не удовлетворяет каким-то условиям этой теоремы. В любом случае, придется считать этот интеграл какими-то другими методами.

С этим интегралом я даже связываться не стану, а сразу засуну его в сервис Wolfram Alpha. Только прежде потребуется преобразовать его от интеграла по замкнутому контуру к обычному виду. Для этих целей, как правило, используется подстановка (замена переменной) $\[z = r{e^{i\varphi }}\]$. В этом случае комплексная экспонента как бы задает ту окружность радиуса $r$, по которой будет взят интеграл. Но сам интеграл при этом приобретает уже обычный "римановский" вид:
$\[\sum\limits_{k = 0}^n {\frac{1}{{k!}}} = g(n) = \frac{1}{{2\pi i}}\oint\limits_C {G(z){z^{n - 1}}dz} = \frac{1}{{2\pi i}}\oint\limits_C {\frac{{{z^n}{e^{1/z}}}}{{z - 1}}dz} = [z = r{e^{i\varphi }}] = \frac{1}{{2\pi i}}\oint\limits_C {\frac{{{e^{1/(r{e^{i\varphi }})}}}}{{r{e^{i\varphi }} - 1}}{{(r{e^{i\varphi }})}^n}d(r{e^{i\varphi }})} = \frac{{{r^n}}}{\pi }\int\limits_{ - \pi }^\pi {\frac{{{e^{1/(r{e^{i\varphi }})}}}}{{r{e^{i\varphi }} - 1}}{e^{i\varphi (n + 1)}}d\varphi } \]$.

Уже на данном этапе можно видеть, что интеграл получился просто адски сложным, и даже не стоит думать о том, чтобы решать его вручную. Однако все еще нужно выбрать радиус $r$ окружности контура обхода. Радиус должен быть достаточно большим, чтобы внутрь окружности попали все т.н. особые точки функции $G(z)$. В данном случае особыми являются точки $z=0$ и $z=1$, потому что в них функция $G(z)$ не существует (терпит разрыв). Впрочем, насчет точки $z=0$ можно не беспокоиться: она в любом случае попадет внутрь окружности, поскольку является ее центром.

Я выберу $r=2$ - этого вполне должно хватить. И теперь идем на сервис Wolfram Alpha, чтобы получить этот интеграл. Сервис мне выдал сообщение "Standard computation time exceeded..." (стандартное вычислительное время превышено). Строго говоря, это не означает, что такого интеграла не существует в элементарных функциях. Может быть, просто не хватило времени, чтобы его вычислить. Тем не менее, чаще всего такое сообщение и возникает, когда интеграла попросту нет. Видимо, в этом случае машина Тьюринга попадает в какой-то бесконечный цикл, выход из которого происходит только по времени принудительным путем. А поскольку время ограничено, мы этого момента никогда не можем дождаться. Хотя, по-хорошему, там должно быть написано что-то вроде "no result found in terms of standart matematical functions" (не найдено результатов в терминах стандартных математических функций). Хотя опять-таки, строго говоря, если результаты не найдены, это еще не значит, что их нет.

Тем не менее, в каких-то отдельных целых значениях этот интеграл вполне можно вычислить. Например, для $n=4$ получим $65/24$. И действительно, $\[\sum\limits_{k = 0}^4 {\frac{1}{{k!}}} = \frac{1}{{0!}} + \frac{1}{{1!}} + \frac{1}{{2!}} + \frac{1}{{3!}} + \frac{1}{{4!}} = 1 + 1 + \frac{1}{2} + \frac{1}{6} + \frac{1}{{24}} = \frac{{24}}{{24}} + \frac{{24}}{{24}} + \frac{{12}}{{24}} + \frac{4}{{24}} + \frac{1}{{24}} = \frac{{65}}{{24}}\]$.

В принципе, обе поставленные задачи решены:
1) доказано (вернее, "доказано"), что не существует замкнутой формулы в элементарных функциях для частичной суммы вот такого ряда: $\[\sum\limits_{k = 0}^\infty {\frac{1}{{k!}}} \]$
2) замкнутой формулой чисто теоретически можно считать сам этот интеграл, если нужно.

Плохо то, что интеграл получился комплексным. А значит, численными методами его просто так не посчитаешь. И разбить его на две части, действительную и мнимую, чтобы потом считать их по отдельности, тоже не представляется возможным (я, например, не вижу, как это можно было бы сделать). С другой стороны, если нужно что-то посчитать, почему бы тогда не просуммировать сам ряд? Это во всяком случае будет гораздо проще, чем вычислять интеграл.
Если б был какой-нибудь сервис, позволяющий получить производящую функцию последовательности, было бы вообще замечательно! Тогда весь процесс суммирования рядов можно было бы автоматизировать.

PS
Как выяснилось, Wolfram Alpha и так уже умеет суммировать ряды! Например, сумму $\[\sum\limits_{k = 0}^n {\frac{1}{{k!}}} \]$ он считает вот так (Sum[1/k!, {k, 0, n}]): $\[\sum\limits_{k = 0}^n {\frac{1}{{k!}}} = \frac{{e\Gamma (n + 1,1)}}{{\Gamma (n + 1)}}\]$.
Таким образом, данную частичную сумму этот сервис выразил через гамма-функцию Эйлера и какую-то неполную гамма-функцию (incomplete gamma function). Видимо, здесь как-то был использован тот факт, что для любых натуральных $n$ верно $\Gamma(n+1)=n!$.

[lel0lel]

Random Drifter в сообщении #1571779 писал(а):

по легенде впервые полученная Карлом Гауссом, когда он еще учился в школе.

Цитата:

According to an anecdote of uncertain reliability,[2] young Carl Friedrich Gauss in primary school reinvented this method to compute the sum of the integers from 1 through 100, by multiplying n/2 pairs of numbers in the sum by the values of each pair n + 1.[clarification needed] However, regardless of the truth of this story, Gauss was not the first to discover this formula, and some find it likely that its origin goes back to the Pythagoreans in the 5th century BC.[3] Similar rules were known in antiquity to Archimedes, Hypsicles and Diophantus;[4] in China to Zhang Qiujian; in India to Aryabhata, Brahmagupta and Bhaskara II;[5] and in medieval Europe to Alcuin,[6] Dicuil,[7] Fibonacci,[8] Sacrobosco[9] and to anonymous commentators of Talmud known as Tosafists.[10]

Wikipedia

[Random Drifter]

lel0lel, ну, я на русскую википедию ориентировался - там про это ничего не сказано :)
В любом случае, слово "reinvented" означает "переоткрыл". И поэтому этот "anecdote" никак не противоречит фактам. Быть может, в школе Гаусс еще не читал всех этих книжек и даже не думал, что станет математиком. А само изобретение этого метода независимо от кого-либо и сподвигло его встать на эту стезю. По-моему, звучит весьма правдоподобно.

Мне было бы интереснее узнать, почему формула Коши не сработала во втором примере.

[mihaild]

В выкладки и общие рассуждения не вчитывался, но из

Random Drifter в сообщении #1571759 писал(а):

Интеграл берется по любому замкнутому контуру, включающему все особые точки $F(z)$.

Random Drifter в сообщении #1571779 писал(а):

Формула Коши в данном случае нам скажет, что искомый ряд должен быть равен $e$ (т.е. числу Эйлера или основанию натурального логарифма).

Как вы формулу Коши собираетесь применять к функции с существенной особенностью?
Ну и в любом случае, формула Коши - это частный случай основной теоремы о вычетах, и наш интеграл - это сумма вычетов в нуле и единице, в единице у функции полюс первого порядка (и там вычет равен $e$), в нуле функция легко раскладывается в ряд Лорана, с коэффициентами как раз равными $-\sum\limits_{k=n}^\infty \frac{1}{k!}$.

[Random Drifter]

Ms-dos4 в сообщении #1135616 писал(а):

Rusit8800
1)Что значит только интуицией? Нет конечно. Но если вы имеете ввиду, есть ли универсальный метод нахождения суммы, то нет. (Есть разве что формулы суммирования типа Эйлера-Маклорена, но их польза в "реальных" случаях ограничивается разве что асимптотиками).

Между прочим, формула Эйлера-Маклорена не так уж и бесполезна, как может показаться. Ведь она фактически и предлагает представить ряд в виде интеграла плюс еще какой-то "довесок", как правило, тоже ряд. А это значит, что эта формула может выступить если не критерием, то хотя бы необходимым условием того, что данный ряд выразим в замкнутой форме в элементарных функциях.

Действительно, если интеграл не выразим (не представим) в элементарных функциях, то и исходный ряд - тоже. Другое дело, если интеграл выразим, это еще не значит, что и ряд - тоже. (Вот потому-то это необходимое условие, но не достаточное.) Самый простой пример - гармонический ряд. Гармонический ряд - это сумма f(1)+f(2)+f(3)+..., где f(k)=1/k. Очевидно, интеграл от 1/k легко берется - это ln(k) (натуральный логарифм). Тогда как частичная сумма гармонического ряда (т.н. гармоническое число) выражается через гамма-функцию Эйлера (и ее производную). Есть и другие способы, но тоже через "неберущийся" интеграл. Конечно, сама функция f(k) еще должна быть интегрируемой. Если это какой-нибудь факториал, ничего не выйдет. Но факториал можно заменить гамма-функцией.

Кроме того, формула Эйлера-Маклорена может оказаться полезной в тех случаях, когда функция f(k) имеет конечное число ненулевых производных. Если все производные от f(k), начиная с какого-то момента становятся равными нулю, тогда формула Эйлера-Маклорена фактически дает готовый алгоритм получения замкнутой формулы. Только для этого надо использовать вариант этой формулы с нулевым остатком и бесконечным рядом в правой части. Потому что на самом деле он не будет бесконечным, и все его члены обратятся в ноль с некоторого момента. Другое дело, где найти такую функцию, имеющую конечное число ненулевых производных...

Самое простое, что приходит на ум, это алгебраический полином. Что-нибудь вроде f(k) = 5{x^3} + {x^2} + 2x - 1. Понятно, что если я ищу \sum {f(k)}, я могу представить этот ряд в виде \sum {f(k)} = \sum {(5{x^3} + {x^2} + 2x - 1)} = 5\sum {{x^3}} + \sum {{x^2}} + 2\sum x - \sum 1. По большому счету, мне достаточно найти замкнутую форму для \sum {{x^m}}, где m - произвольное натуральное число, и я решу эту задачу в общем случае. Но эта задача и так уже была решена давным давно!

В википедии статья про числа Бернулли с этого и начинается - с того, что числа Бернулли возникли при решении этой самой задачи. А затем производящая функция последовательности чисел Бернулли уже используется для вывода формулы Эйлера-Маклорена. (Есть еще статья про формулу Фаульхабера, тоже на эту тему. Не понятно только, почему в связи с одной и той же задачей всплыло два разных имени.)
В частности, известная формула суммы первых n квадратов натуральных чисел была получена именно таким способом.

n(n+1)(2n+1)/6

Помню, я когда еще в школе учился, впервые увидел эту формулу. Ее предлагали доказать по индукции. Но мне было интереснее другое: а как вообще кто-то смог получить или "угадать" эту формулу. Как такое в принципе делается? И как он вообще догадался искать такую неочевидную формулу. Откуда он знал, что она существует?

В интернете можно встретить "геометрические" доказательства, или вернее, выводы этой формулы. Но на мой взгляд, это просто абсурд! Никто не станет доказывать эту формулу таким диким способом, если ее можно доказать по индукции. С другой стороны, и вывести ее таким путем тоже невозможно, если только заранее не знать, как она выглядит. Так что это будет не вывод, а самообман.

$$$$***$$$$

В чем заключается проблема "стандартного" метода сведения суммы к интегралу? Я имею в виду, конечно, метод производящих функций. Проблема в том, что этот "метод" на самом деле методом не является. Ведь задача получения замкнутой формы частичной суммы ряда подменяется задачей угадывания замкнутой формы производящей функции соответствующей последовательности. А если надо угадывать, это уже не метод. Это, может быть, искусство, соревнование в прозорливости, в котором многие известные математики участвовали, но не метод. Метод - это как у Декарта: не надо быть шибко умным - просто действуй по алгоритму, и получишь результат.

Я объясню немного подробнее. Допустим, надо найти частичную сумму вот такого ряда: \sum\limits_{k = 1}^\infty {f(k)}. Частичную сумму обозначим g(n) = \sum\limits_{k = 1}^n {f(k)}. Действуем стандартно: составляем производящую функцию для последовательности f(0), f(1), f(2), ...: F(x) = \sum\limits_{k = 0}^\infty {f(k){x^k}}. Для g(0), g(1), g(2), ... тоже составим производящую функцию и обозначим ее G(x) = \sum\limits_{k = 0}^\infty {g(k){x^k}}.

У производящей функции есть одно полезное свойство: ПФ для f(1), f(2), f(3), ... можно получить из ПФ для f(0), f(1), f(2), ... следующим приемом: (F(x)-f(0))/x. Это очевидно.

Далее нужно заметить, что g(n) фактически является решением разностного уравнения g(n+1)-g(n) = f(n+1). Возьмем производящие функции от обеих частей этого уравнения. Получим (G(x)-f(0))/x - G(x) = (F(x)-f(0))/x. Отсюда получаем G(x) = F(x)/(1 - x). Т.е. F и G связаны таким простым соотношением.

Теперь нужно получить с помощью производящей функции член последовательности с нужным номером. Для этого воспользуемся разложением функции F в ряд Тейлора:
\left\{ \begin{array}{l} F(x) = \sum\limits_{k = 0}^\infty {\frac{{{F^{(k)}}(0)}}{{k!}}{x^k}} \\ F(x) = \sum\limits_{k = 0}^\infty {f(k){x^k}} \end{array} \right
Отсюда с очевидностью следует формула f(k) = $\frac{{{F^{(k)}}(0)}}{{k!}}$

Но, правда, толку от этой формулы негусто, поскольку теперь надо знать зависимость {{F^{(k)}}(0)} от k. Но и на этот случай есть выход - интегральная формула Коши:
f(k) = $\frac{{{F^{(k)}}(0)}}{{k!}}$ = $\frac{1}{{2\pi i}}$\int\limits_\Gamma {F(z){z^{ - k - 1}}dz},
которая сводит данную зависимость к комплексному интегралу по некоторому контуру Г.

Здесь Г – контур, охватывающий область сходимости F(z). Причем, он должен содержать в себе все вычеты F(z). Не знаю, что это значит, но так написано в википедии. Дело в том, что контур может быть любым, если он удовлетворяет названным условиям. В том числе, может он быть и окружностью. Так вот, в тех случаях, когда он может быть окружностью (когда ее можно проложить в этой области), комплексный интеграл можно свести к действительному заменой переменной z = r{e^{i\varphi }}, где \varphi меняется, например, от -\pi до \pi. Действительно, z = r{e^{i\varphi }} - фактически, уравнение окружности на комплексной плоскости с радиусом r и аргументом \varphi. Меняя этот (действительный!) аргумент от -\pi до \pi, мы фактически проходим по всем точкам исходного аргумента z. Т.о. окончательно получаем:
f(k) = $\frac{{{F^{(k)}}(0)}}{{k!}}$ = $\frac{1}{{2\pi i}}$\int\limits_\Gamma {F(z){z^{ - k - 1}}dz} = $\frac{1}{{2\pi {r^k}}}$ \int \limits_{ - \pi }^\pi {F(r{e^{i\varphi }}){e^{ - ik\varphi }}{\kern 1pt} d\varphi }.

(Ну у меня так получилось, надеюсь, я нигде не ошибся.)

Этот интеграл затем можно скормить, например, Wolfram Alpha, и получить готовый ответ. Или не получить, если он не существует в элементарных функциях. Проблема здесь в том, что использовать Wolfram Alpha можно в том случае, если уже откуда-то известен вид функции F. А он в общем случае не известен! И наоборот, мы только что выразили f(k) через интеграл от F, тогда как f(k) нам известна по условию задачи, а вот F - нет. Не понятно, зачем вообще понадобилось городить производящие функции, если в итоге это ничего не дало.

Я напомню, что искали мы, вообще-то, не f(k), а g(k). Поэтому в интеграл нужно подставлять не F, а G. Причем, G известна, если известна F. Тогда появляется некоторый смысл. Но опять всё упирается в то, что F не известна, и не существует общего метода ее отыскать.

Кстати говоря, полученную выше формулу Коши в форме действительного интеграла можно рассматривать, как интегральное уравнение с неизвестной функцией F. Точнее говоря, это неоднородное интегральное уравнение Фредгольма первого рода с комплексной экспонентой в качестве ядра. Такие уравнения неплохо решаются, если ядро обладает свойством K(t,s) = K(t-s). В этом случае интеграл можно рассматривать, как свертку двух функций (если там еще подхимичить с пределами интегрирования). Однако для данного конкретного ядра я что-то не нашел решения. И вообще, такое чувство, что эта теория еще очень плохо разработана. Более того, интегральные уравнения могут и не иметь решения в принципе! Кажется, с этого начинается эта теория.

К слову, эта задача очень похожа на задачу найти вид функции f(x) по ее разложению в ряд Фурье, если известен вид зависимости коэффициентов a(k) и b(k). Ну т.е. понятно, что функция представима своим рядом Фурье. Но вот если требуется именно замкнутая форма для f, то из ряда Фурье просто так ее не получить. Я нигде не видел даже не то, чтобы кто-нибудь решил эту задачу, а хотя бы просто ее поставил.
Причем, формулы для коэффициентов Фурье, полученные через f, можно рассматривать, как интегральные уравнения по f.

Между прочим, в "Конкретной математике" ни слова не сказано об интегральных уравнениях, хотя казалось бы, с этого надо было начинать.

PS
Кроме "обычных" производящих функций иногда удобнее бывает использовать экспоненциальные пр. функции (ЭПФ). В этом случае исходное разностное уравнение можно свести к дифференциальному: G'-G=F. Решением его является интеграл G(x) = {e^x}\int {F(x){e^{ - x}}dx}. Ну т.е. и в этом случае функции F и G довольно просто связаны друг с другом, хотя и более сложно.

$$$$***$$$$

В английской википедии есть статья, называется indefinite sum - неопределенная сумма. На русский еще не переведена. Мне она показалась довольно полезной, поскольку в ней эта задача (получения замкнутой формы ряда) поставлена в общем случае. Причем, она как раз и решается в большинстве случаев сведением суммы к интегралу. В частности, там можно найти не только формулу Эйлера-Маклорена, но также формулу суммирования Лапласа, и много других формул. Выводятся они точно также - операторным методом.

Часто вместо производных k-го порядка в них используются конечные разности, тоже k-го порядка. Это на случай тех функций, которые имеют только конечное число ненулевых конечных разностей. Хотя мне опять ничего в голову не приходит, кроме алгебраического полинома, в качестве примера такой функции.

Вообще, что такое эта неопределенная сумма? - То же, что и неопределенный интеграл, только вместо интеграла - сумма. Когда мы смотрим на неопределенный интеграл, мы автоматически подразумеваем на его месте некоторую замкнутую форму, которая должна там стоять. Мы настолько привыкли к этому, что забываем, что функция может быть задана не только законом, но и, например, графиком. Поэтому и для интеграла будет верно тоже самое (он будет просто площадью под этим грпфиком).

Кстати говоря, замкнутая форма ряда, когда она получена, автоматически подразумевает, что в нее можно подставлять и дробные числа. Это значит, что мы получаем формулу, которая совпадает с исходным рядом только в целых точках. А поскольку в других точках ряд не существует, то в нецелых точках дополнить этот ряд можно разными способами! А это значит, что единственного решения не существует!

В частности, если g(n) является решением разностного уравнения, то g(n)+c(n) - тоже, где c(n) - любая периодическая функция с периодом 1. Однако, в силу теоремы некоего Карлсона (не того ли, что на крыше живет?), "решение, равное ее разложению в ряд Ньютона, является единственным с точностью до аддитивной константы C". Смотрите-ка, уже какая-то теория вырисовалась.

Напоследок скажу, что в той статье есть ссылка на статью Кауэрса "Algorithms for Nonlinear Higher Order Difference Equations". В которой он упоминает, конечно, алгоритм Госпера-Зильбергера. Но говорит, что алгоритм работает только для узкого класса функций. Общего же алгоритма до сих пор нет. И вообще "бессмысленно думать об алгоритмах, применимых ко всем последовательностям" (это сказано в предисловии).

[Random Drifter]

А, нет, я был не прав. Или не совсем прав. Я сейчас открыл статью Faulhaber's formula. А там пишут, что задачу \sum {{x^m}} решали еще древние греки. В частности,
1 + 2 + \ldots + n = $\frac{1}{2}{n^2}$ + $\frac{1}{2}n$ - формула, известная Пифагорейской школе, благодаря своей связи с треугольными числами.
{1^2} + {2^2} + \ldots + {n^2} = \frac{{{n^3}}}{3} + \frac{{{n^2}}}{2} + \frac{n}{6} - формула Архимеда из его работы Spirals.
{1^3} + {2^3} + \ldots + {n^3} = \frac{{{n^4}}}{4} + \frac{{{n^3}}}{2} + \frac{{{n^2}}}{4} - следствие тождества Никомаха Герасского.

И все они были получены, как я понимаю, геометрическими путями. Видимо, до этого я читал только русскую версию этой статьи, а там про это ничего сказано не было. Ради справедливости, в "Конкретной математике" ни Фаульхабер, ни одно из этих имен не упоминается. Я, конечно, не от корки до корки пролистал, но в оглавлении этого нет.

Притом, что сама задача \sum {{x^m}} там решается - в начале раздела по ЭПФ. Как можно догадаться, решается она с помощью этой самой ЭПФ.

[Random Drifter]

Между прочим, существует довольно изящный прием, позволяющий очень просто (практически в одну строчку) получить частичную сумму гармонического ряда (гармоническое число), только в нетрадиционной форме. В "Конкретной математике" мне этот прием не встретился. А в википедии имеется только сама "нетрадиционная форма", без объяснения, откуда она взялась.

Короче говоря, нужно использовать, так сказать, "конечную" производящую функцию.
Пусть у нас имеется вот такая частичная сумма гармонического ряда: 1/1+1/2+...+1/n.
Рассмотрим функцию F(x) = $\frac{x}{1}$ + $\frac{{{x^2}}}{2}$ + ... + $\frac{{{x^n}}}{n}$
Очевидно, в точке x=1 эта функция точно равна n-й частичной сумме гармонического ряда.

Возьмем производную от F(x) по x и получим F'(x) = $\frac{1}{1}$ + $\frac{{2x}}{2}$ + ... + $\frac{{n{x^{n - 1}}}}{n}$ = 1 + x + ... + {x^{n - 1}} = \frac{{{x^n} - 1}}{{x - 1}}.
Получилось ни что иное как сумма геометрической прогрессии. Остается только проинтегрировать ее назад, и получим F(x) = \int {\frac{{{x^n} - 1}}{{x - 1}}dx}.
Здесь еще требуется подобрать правильную константу интегрирования, чтобы получилось F(1)=1/1+1/2+...+1/n.
В википедии (статья "Гармоническое число") эта формула имеет следующий вид: {H_x} = \int_0^1 {\frac{{1 - {t^x}}}{{1 - t}}} dt,\;\;\;{\kern 1pt} Re(x) > - 1.
(Там нетрудно доказать, что так и должно было получиться.)

Но в принципе, это уже и есть сведение ряда к интегралу. И дальше уже можно проверять этот интеграл, берется ли он в элементарных функциях, или нет (разумеется, нет).

$$$$***$$$$

Что интересно, этим же приемом можно получить замкнутую формулу еще и для такой суммы: \sum\limits_{k = 1}^n {\frac{1}{{k!}}}. Просто так, телескопированием ее не получить. Но там уже сложнее получается, так что предлагаю каждому проделать это самостоятельно. И сумму арифметической прогрессии тоже можно получить этим же способом.

Действительно, сумма арифметической прогрессии - это у нас \sum\limits_{k = 1}^n k = 1 + 2 + 3 + ... + n.
Рассмотрим вот такую функцию: F(x) = 1 + 2x + 3{x^2} + ... + n{x^{n - 1}}, которая F(1) = \sum\limits_{k = 1}^n k.
Проинтегрируем ее и получим \int {F(x)dx} = x + {x^2} + {x^3} + ... + {x^n} + C = \frac{{{x^{n + 1}} - 1}}{{x - 1}} + C - 1.
Очевидно, опять получилась сумма геометрической прогрессии. Далее дифференцируем обратно обе части этого равенства и получаем:
F(x) = $\frac{{(n + 1){x^n}(x - 1) - ({x^{n + 1}} - 1)}}{{{{(x - 1)}^2}}}$ = $\frac{{(n + 1){x^n}}}{{x - 1}}$ - $\frac{{{x^{n + 1}} - 1}}{{{{(x - 1)}^2}}}$.
На этот раз получилась функция, которая не существует в точке x=1. А именно в ней-то она и нужна. Но не беда! Нужно просто найти предел F(x) в этой точке. Для этого используем правило Лопиталя. У меня получилось так:
\begin{array}{l} \mathop {\lim }\limits_{x \to 1} F(x) = \mathop {\lim }\limits_{x \to 1} \frac{{((n + 1){x^n}(x - 1) - ({x^{n + 1}} - 1))''}}{{({{(x - 1)}^2})''}} = \mathop {\lim }\limits_{x \to 1} \frac{{(n{x^{n + 1}} - (n + 1){x^n} + 1)''}}{{({{(x - 1)}^2})''}} = \\ = \mathop {\lim }\limits_{x \to 1} \frac{{{n^2}(n + 1){x^{n - 1}} - n(n + 1)(n - 1){x^{n - 2}}}}{2} = \frac{{{n^2}(n + 1) - n(n + 1)(n - 1)}}{2} = (n + 1)n\frac{{n - (n - 1)}}{2} = \frac{{(n + 1)n}}{2} \end{array}

Да, очевидно, получилась формула суммы арифметической прогрессии.

В данном случае для получения суммы арифметической прогрессии была использована формула суммы геометрической прогрессии. Кажется, что менее сложная задача была решена с помощью более сложной. Но на самом деле это не так! Формула суммы геометрической прогрессии доказывается легче легкого. И для этого даже не требуется применять индукцию.

Проще всего начать от формулы сокращенного умножения: {a^n} - {b^n} = (a - b)({a^{n - 1}} + {a^{n - 2}}b + ... + {b^{n - 2}}a + {b^{n - 1}}).
Эту формулу надо просто запомнить и всегда ею пользоваться. В частности, если одно из двух чисел, a или b равно единице, формула приобретает более простой вид: {x^n} - 1 = (x - 1)({x^{n - 1}} + {x^{n - 2}} + ... + x + 1).

А это уже сумма геометрической прогрессии. Доказывается она обычным телескопированием:
\begin{array}{l} (x - 1)({x^{n - 1}} + {x^{n - 2}} + ... + x + 1) = \\ = x({x^{n - 1}} + {x^{n - 2}} + ... + x + 1) - ({x^{n - 1}} + {x^{n - 2}} + ... + x + 1) = \\ = {x^n} + {x^{n - 1}} + ... + x - ({x^{n - 1}} + {x^{n - 2}} + ... + x + 1) = {x^n} - 1 \end{array}
Формула сокращенного умножения доказывается аналогичным образом.

$$$$***$$$$

Если нам уже известно, что \sum\limits_{k = 1}^n k = \frac{{n(n + 1)}}{2}, эта формула позволяет получить замкнутую формулу для неопределенной суммы \sum x. Осуществляется это очень простым приемом: \sum x = \frac{{(x - 1)((x - 1) + 1)}}{2} = \frac{{x(x - 1)}}{2}. Здесь n просто заменили на x-1.

Сделаем проверочку:
\Delta \frac{{x(x - 1)}}{2} = \frac{{(x + 1)(x + 1 - 1)}}{2} - \frac{{x(x - 1)}}{2} = \frac{{x(x + 1)}}{2} - \frac{{x(x - 1)}}{2} = x\frac{{x + 1 - x + 1}}{2} = x.
Да, всё верно.
Очевидно, что в общем случае неопределенную сумму было бы удобно представить в виде \sum {f(x)} = \sum\limits_{k = const}^{x - 1} {f(k)}.
Докажем, что эта формула действительно верна.
Действительно, \Delta \left( {\sum\limits_{k = const}^{x - 1} {f(k)} } \right) = \sum\limits_{k = const}^{x + 1 - 1} {f(k)} - \sum\limits_{k = const}^{x - 1} {f(k)} = f(x).

$$$$***$$$$

Напоследок я собрал несколько обсуждений этой же темы. Вдруг кому-нибудь пригодится.

Вычислить сумму 1/(1*2) + 1/(2*3) + 1/(3*4) + ...+1/(99*100)
Как вычислить сумму ряда с помощью интеграла?
Перейти от суммы к интегралу
Переход от ряда к интегралу.
Сумма ряда

[Random Drifter]

Ende
Выделено из темы «Вычислить сумму 1/(1*2) + 1/(2*3) + 1/(3*4) + ...+1/(99*100)»

AndreyXYZ в сообщении #169994 писал(а):

Вы лучше сверните такой ряд:

$$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{k}$$

Легко!
Рассмотрим функцию F(x) = $\frac{x}{1}$ + $\frac{{{x^2}}}{2}$ + ... + $\frac{{{x^k}}}{k}$

Возьмем производную от F(x) по x и получим F'(x) = $\frac{1}{1}$ + $\frac{{2x}}{2}$ + ... + $\frac{{k{x^{k - 1}}}}{k}$ = 1 + x + ... + {x^{k - 1}} = \frac{{{x^k} - 1}}{{x - 1}}.
Получилась сумма геометрической прогрессии. Остается только проинтегрировать ее назад, и получим F(x) = \int {\frac{{{x^k} - 1}}{{x - 1}}dx}.
Дальше нужно подставить x=1 в F(x).

[Combat Zone]

Всего-то 17 лет прошло, да и ладно. Вы сперва сделайте то, что предлагаете. Проинтегрируйте, подставьте. А так да, легко.

[Random Drifter]

Combat Zone в сообщении #1694131 писал(а):

Всего-то 17 лет прошло, да и ладно. Вы сперва сделайте то, что предлагаете. Проинтегрируйте, подставьте. А так да, легко.

Предоставлю эту рутинную работу вам! А то вам совсем ничего не останется. Кстати, вы сами-то где были эти 17 лет? - На большом Каретном?

[Combat Zone]

Random Drifter в сообщении #1694135 писал(а):

Предоставлю эту рутинную работу вам!

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

[Ende]

Combat Zone в сообщении #1694138 писал(а):

Вы дали дурной совет в учебном разделе. Так что пусть админы вами занимаются.

Вынесено из учебного раздела. Впрочем, любой нынешний ответ вряд ли повредил бы учебному процессу, имевшему место в 2008 году.

[Combat Zone]

Random Drifter в сообщении #1694201 писал(а):

Который не понятно где был эти 17 лет.

Там же, где и вы. Странные претензии от человека с той же датой регистрации.

Random Drifter в сообщении #1694201 писал(а):

и которому сказать нечего.

Мне есть что сказать. Я это и говорю. Попробуйте осуществить вашу процедуру. Вычислите интеграл. Подставьте единицу. Если вы не ошибетесь, выйдет в аккурат
${1}+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{k}$.
То есть $k$-е гармоническое число $H_k$. Эта сумма, а не интегральное представление, является определением $k$-го гармонического числа. То есть что вы предлагаете. Вы предлагаете, чтобы вычислить $H_k$, записать его в виде интеграла. А потом посчитать интеграл. Но когда вы посчитаете интеграл, получится в точности $H_k$. Это все.

[Random Drifter]

Combat Zone, странные претензии - это у вас. 17 лет эта тема вас не интересовала. Когда же я что-то написал в нее, вам не понравилось, что я сделал это спустя 17 лет. Как будто я вообще был обязан уложиться в установленный кем-то (вами?) срок.

Ну что же вы не сделали этого раньше меня, если эта тема вам так интересна? А если она не интересна, что вы тут забыли? Я написал для AndreyXYZ. А если он не придет, пусть тогда другие прочтут, кому интересно. В этом смысл форума. Вы пришли и начали что-то требовать. Даже не требовать, а... я даже не знаю, что. Просто вам не понравился мой пост. К счастью, я не обязан нравиться кому-либо. Всё что я "должен", это следовать правилам. Тем более, если вам не нравятся мои посты, это еще не повод их стирать. Странно, что приходится объяснять такие вещи.

Цитата:

Попробуйте осуществить вашу процедуру. Вычислите интеграл. Подставьте единицу.

Мне очень жаль, что вы не умеете интегрировать. Но вы же не считаете в самом деле, что я обязан что-либо вам объяснять? Я сделаю это, просто чтобы уже закрыть эту тему. Умному человеку хватило бы и того приема, который я написал, и которого в книжке вы не найдете. Я по крайней мере не знаю названия этой книжки. Ее еще нужно хорошо поискать.

Я конечно благодарностей особых не ждал, но и обвинений х.з. в чем - тоже. (На самом деле, можно было просто нормально попросить, чтобы я это объяснил, если вам действительно это интересно.)

Итак, неопределенный интеграл \int {\frac{{{x^k} - 1}}{{x - 1}}dx} - это сумма Q(x)+C, где Q(x) - т.н. первообразная, C - произвольная константа (не зависящая от x). Слово "первообразная" означает, что производная от этой функции равна подынтегральному выражению: Q'(x) = $\frac{{{x^k} - 1}}{{x - 1}}$. Таким образом, можно записать \int {\frac{{{x^k} - 1}}{{x - 1}}dx} = Q(x) + C. Дальше у нас F(x) = \int {\frac{{{x^k} - 1}}{{x - 1}}dx}. Однако по условию задачи F(x=0)=0. Значит, можно записать F(0)=Q(0)+C=0, откуда получаем Q(0)=-C.

Затем используем формулу Ньютна-Лейбница: \int\limits_a^b {\frac{{{t^k} - 1}}{{t - 1}}dt} = Q(b) - Q(a).
Зададим:
a=0,
b=x.

Тогда получим \int\limits_0^x {\frac{{{t^k} - 1}}{{t - 1}}dt} = Q(x) - Q(0) = Q(x) + ( - Q(0)) = Q(x) + C = \int {\frac{{{x^k} - 1}}{{x - 1}}dx}.
Теперь я имею право записать: F(x) = \int\limits_0^x {\frac{{{t^k} - 1}}{{t - 1}}dt}.

Остается подставить сюда x=1, и получится F(1) = \int\limits_0^1 {\frac{{{t^k} - 1}}{{t - 1}}dt}.
Вот это и есть замкнутая формула для гармонического числа.