Инструменты сайта


§

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

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

При $ 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) $.
algebra2/course/miscellania.txt · Последние изменения: 2020/05/19 12:17 — au