УказательРазделыОбозначенияАвторО проекте


§

Здесь пока находится «свалка»: материалы, необходимые для других разделов, но для которых их «родные» разделы еще не созданы.


Некоторые суммы

Суммы степеней целых чисел

При n \in \mathbb N и k\in \{0,1,2,\dots \} обозначим

\displaystyle S_k(n)= 1^k+2^k+\dots+n^k= \sum_{j=1}^n j^k

и \displaystyle C_n^kбиномиальный коэффициент.

Т

Теорема. Имеет место рекурсивная формула1):

(k+1)S_k+C_{k+1}^2 S_{k-1}+C_{k+1}^3 S_{k-2}+\dots+C_{k+1}^k S_1+ S_0=(n+1)^{k+1}-1 \ ,

позволяющая выразить S_{k} через S_{k-1},S_{k-2},\dots,S_1,S_0.

Явное выражение для S_k(n) получается с использованием определителя.

Т

Теорема. Имеют место равенства:

S_k(n)=\frac{1}{(k+1)!} \left| \begin{array}{llllll} (n+1)^{k+1} & C_{k+1}^{k-1} & C_{k+1}^{k-2} & \dots & C_{k+1}^{1} & 1 \\ (n+1)^{k} & C_{k}^{k-1} & C_{k}^{k-2} & \dots & C_{k}^{1} & 1 \\ (n+1)^{k-1} & 0 & C_{k-1}^{k-2} & \dots & C_{k-1}^{1} & 1 \\ \vdots & & & \ddots & & \vdots \\ (n+1)^{2} & 0 & 0 & \dots & C_{2}^{1} & 1 \\ (n+1) & 0 & 0 & \dots & 0 & 1 \end{array} \right|_{(k+1)\times (k+1)}
=\frac{1}{(k+1)!} \left| \begin{array}{clllll} n^{k}(n+k+1) & C_{k+1}^{k-1} & C_{k+1}^{k-2} & \dots & C_{k+1}^{1} & 1 \\ n^{k} & C_{k}^{k-1} & C_{k}^{k-2} & \dots & C_{k}^{1} & 1 \\ n^{k-1} & 0 & C_{k-1}^{k-2} & \dots & C_{k-1}^{1} & 1 \\ \vdots & & & \ddots & & \vdots \\ n^{2} & 0 & 0 & \dots & C_{2}^{1} & 1 \\ n & 0 & 0 & \dots & 0 & 1 \end{array} \right|_{(k+1)\times (k+1)} \, .

=>

Выражение для S_k(n) будет полиномом от n_{} степени k+1 со старшим коэффициентом равным 1/(k+1). Коэффициенты этого полинома

S_k(n) = \frac{1}{k+1} \sum_{j=0}^k C_{k+1}^{k+1-j} B_j (n+1)^{k+1-j}

связаны с числами Бернулли \{ B_j \}_{j=0}^{\infty} — коэффициентами разложения функции x/(e^x-1) в ряд Тейлора.

B_0=1,\ B_1=-\frac{1}{2},\ B_2=\frac{1}{6},\ B_3=0,\ B_4=-\frac{1}{30}, B_5=0,\ B_6=\frac{1}{42}, B_7=0,\ B_8= -\frac{1}{30},\dots

Подробнее ЗДЕСЬ.

П

Пример.

S_0=\underbrace{1+1+\dots+1}_n=n \ .
S_1= 1+2+\dots+n = \frac{n(n+1)}{2}=C_{n+1}^2 \ .
S_2= 1^2+2^2+\dots+n^2 =\frac{n(n+1)(2n+1)}{6} \ .
S_3= 1^3+2^3+\dots+n^3 = \frac{n^2(n+1)^2}{4}= S_1^2 \ .
S_4=\frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}=S_2\frac{6S_1-1}{5} \ .

Т

Теорема. Имеет место равенство:

1^k+3^k+5^k+\dots+(2n-1)^k=\sum_{j=1}^n (2j-1)^k=S_k(2n)-2^k S_k(n) \ .

П

Пример.

1+3+5+\dots+(2n-1)=\sum_{j=1}^n (2j-1)=n^2 \ .
1^2+3^2+5^2+\dots+(2n-1)^2=\sum_{j=1}^n (2j-1)^2=\frac{n(4n^2-1)}3 \ .
1^3+3^3+5^3+\dots+(2n-1)^3=\sum_{j=1}^n (2j-1)^3=n^2(2n^2-1) \ .

Т

Теорема. Из множества чисел \{1,2,\dots,n\} составляем всевозможные наборы, состоящие из k_{} чисел: (a_1,a_2,\dots,a_k) (в наборе допускаются одинаковые числа). Имеет место равенство

\sum \min (a_1,\dots,a_k) = S_k(n) \ ;

здесь сумма распространяется на все n^k наборов.

Источники .

Пойа Д. Математическое открытие. М.Наука.1970

Проскуряков И.В. Сборник задач по линейной алгебре. М.Наука. 1974; задача N 604.

Хонсбергер Р. Математические изюминки. М.Наука. 1992, cc.29-30

Теорема Дорна

Т

Теорема. Если A_{}положительно определенная матрица порядка n_{} (не обязательно симметричная) и B \in \mathbb R^nвектор-столбец, то существует вектор-столбец X_{} \in \mathbb R^n, удовлетворяющий условиям

X^{\top} A X+ B^{\top} X = 0,\ AX+B \ge 0, \ X\ge 0 \ .

Источник.

Dorn W.S. Self-dual quadratic programs. Quart. Appl. Math. 9, 1961, pp. 51-54.

Теорема Пика

Т

Теорема [Пик]. Площадь многоугольника, вершины которого находятся в целочисленных точках (и не имеющего самопересечений) выражается в виде

Q+\frac{P}{2}-1 \ ,

где Q_{}количество целочисленных точек внутри многоугольника, а P_{} количество целочисленных точек на его границе.

Разложение Уиттекера

Т

Теорема [Уиттекер]. Пусть степенной ряд

a_0+a_1x+a_2x^2+\dots

сходится в круге |x|< r и уравнение

0=a_0+a_1x+a_2x^2+\dots

имеет простой корень \lambda, такой что | \lambda |< r и | \lambda | меньше модулей остальных корней уравнения. Тогда этот корень можно представить в виде сходящегося ряда

\lambda=-\frac{a_0}{a_1}- \frac{a_0^2a_2}{a_1\left|\begin{array}{ll} a_1 & a_2 \\ a_0 & a_1 \end{array} \right|} - \frac{a_0^3\left|\begin{array}{ll} a_2 & a_3 \\ a_1 & a_2 \end{array} \right|}{\left|\begin{array}{ll} a_1 & a_2 \\ a_0 & a_1 \end{array} \right| \cdot \left|\begin{array}{lll} a_1 & a_2 & a_3 \\ a_0 & a_1 & a_2 \\ 0 & a_0 & a_1 \end{array} \right| } - \frac{a_0^4\left|\begin{array}{lll} a_2 & a_3 & a_4 \\ a_1 & a_2 & a_3 \\ a_0 & a_1 & a_2 \end{array} \right|}{\left|\begin{array}{lll} a_1 & a_2 & a_3 \\ a_0 & a_1 & a_2 \\ 0 & a_0 & a_1 \end{array} \right| \cdot \left|\begin{array}{llll} a_1 & a_2 & a_3 & a_4 \\ a_0 & a_1 & a_2 & a_3 \\ 0 & a_0 & a_1 & a_2 \\ 0 & 0 & a_0 & a_1 \end{array} \right| }- \dots- \frac{a_0^kD_{2,k-1}}{D_{1,k-1}D_{1k}} - \dots

Здесь

D_{1k}=\left|\begin{array}{llll} a_1 & a_2 & \dots & a_k \\ a_0 & a_1 & \dots & a_{k-1} \\ \vdots & & & \vdots \\ a_{2-k} & a_{3-k} & \dots & a_1 \end{array} \right|_{k\times k},\ D_{2k}=\left|\begin{array}{llll} a_2 & a_3 & \dots & a_{k+1} \\ a_1 & a_2 & \dots & a_{k} \\ \vdots & & & \vdots \\ a_{3-k} & a_{4-k} & \dots & a_2 \end{array} \right|_{k\times k}

и полагаем a_j=0 при j<0.

Численный эксперимент показал, что сходимость крайне медленная: для корня \lambda \approx -1.19258 уравнения -5-3\,x+x^2=0 приближение 9-ю слагаемыми формулы Уиттекера \approx -3.57355.

Источник.

Островский А.М. Решение уравнений и систем уравнений. М. ИЛ, 1963, cc. 193-196
1) Для уменьшения громоздкости, в выражениях для S_{k} не указывается аргумент (n).

2017/03/12 12:45 редактировал au