Combinatorial representation of the sum of the weighted equal powers of members of an arithmetical progression

Abstract


The correctness of equality which gives the combinatorial expression for the sum of the weighted equal powers of members of an arithmetical progression is found out. Such aspect provides usage of double summation of certain algebraic combinations with free and weight components of the given sum. Thus specified algebraic combinations also include binomial coefficients. Determination of required equality was made with use of comparison of real and hypothetical values.

Full Text

Исходным выражением для суммы взвешенных одинаковых степеней (СВОС) членов арифметической прогрессии будем считать равенство p ξ p ν Φ (p, ν) = bι ((ι−1)+ξ)ν ; p, ν, ι ∈ N, bι = b0 , d, ξ ∈ R. (1) ι bι (ι+d) = ι=1 ι=1 Первый член, разность, количество членов арифметической прогрессии составляют здесь соответственно ξ, 1, p. Применительно к сфере шифрования достоинство использования СВОС членов арифметической прогрессии заключается в наличии дополнительно вводимого параметра ξ, который может принимать любые значения из множества R, что создает соответственно дополнительное препятствие в раскрытие шифра, формируемого на основе данной СВОС. Ниже устанавливается справедливость равенства, позволяющего выразить сумму (1), используя свободные, вида α, и весовые, вида H, компоненты СВОС: max l ν(i) c ξ j(i) Hi (p) + Hl (p) αj(i) , Φξ (p, ν) = (2) l=1 j(i)=1 184 Комбинаторное представление суммы взвешенных . . . где l = 1, . . . , max l, max l = min(p, ν), i = l − 1; j(i) = 1, . . . , max j(i), max j(i) = ν − i; Hi (p) = bl = 0 p−l k=0 p−l bi p−i−k , i 0; Hl (p) = τ =0 bl p−l−τ , причём [1,2] max j(i−1) i αj(i) j(i) i−1 αj(i−1) Cj(i−1) , = i 1; (3) j(i−1)=j(i)+1 0: 1: 0 αj(0) = j(0) < ν, j(0) = ν. (4) Равенство (1) назовем истинным представлением рассматриваемой СВОС членов арифметической прогрессии, а равенство (2) — её гипотетическим представлением. Далее будем снабжать истинные величины индексами «и» и «l», а гипотетические величины — индексами «г» и r = t + 1. Индекс r выполняет здесь ту же роль, что и аналогичный ему индекс l в известном представлении СВОС [1, 2]. Положим сначала, что ν p, то есть max l = ν. Проводя при этом доказательство гипотетического равенства (2), будем сравнивать между собой соответствующие друг другу фрагменты из (1) и (2). Такие действия должны привести нас к благоприятным результатам выполнения указанных сравнений для случаев принятия степенями величины ξ значения j = 0 (случай с индексом 0) и совокупности значений j = 1, . . . , ν (случай с индексом 1/ν). Часть истинного комбинаторного представления СВОС [1,2], соответствующая нулевой степени величины ξ, может быть выражена как p Φξ (ν и0 ν bι (ι − 1)ν = ξ 0 p) = ι=1 l Φp−1−l0 α0 ; (5) l=1 p−1−l bl p−1−l−τ . Φp−1−l0 = τ =0 Часть же гипотетического представления СВОС членов арифметической прогрессии, также соответствующая нулевой степени ξ, имеет вид ν Φξ (ν г0 ν−t t Hr (p)αj(t) . p) = (6) r=1 j(t)=1 Зададимся следующими равенствами, в которых отразим соотношения индексов истинного и гипотетического представлений: r = l = l(j) = t + 1. Тогда, преобразуя (6), получим ν Φξ (ν г0 p) = ν−t t αj(t) . Hl (p) l=1 (7) j(t)=1 185 А. И. Н и к о н о в Согласно выражению (3), второй сомножитель, находящийся под знаком l суммы из (7), имеет тот же вид, что и соотвествующий сомножитель α0 из (5). Располагая известным комбинаторным представлением [3] p−l l Cp−k b0 , p−k Φp−l0 = k=0 нетрудно получить следующие соотношения: p−l−1 l Cp−1−k b0 , p−k Hl (p) = k=0 p−i−1 i Cp−1−k b0 , p−k Hl−1 (p) = k=0 p−1−l l Cp−1−k b0 . p−k Φp−1−l0 = k=0 В последней из данных сумм, где сравнительно с величиной Φp−l0 взята аналогичная величина со сниженным индексным значением (p − 1 − l), в качестве сомножителей биномиальных коэффициентов оставлены именно весовые коэффициенты с большими индексами. Итак, в рамках случая j = 0 имеет место равенство Hl (p) = Φp−1−l0 , а вместе с ним и равенство друг другу величин (5) и (7): Φξ (ν г0 p) = Φξ (ν и0 p). (8) Далее исследуем случай j = 1, . . . , ν с индексом 1/ν. Части истинного комбинаторного [1, 2] и гипотетического представлений суммы (1) в данном случае выражаются таким образом: ξ1 Φξ и1/ν = Φи1/ν (ν p) + Φξ2 (ν и1/ν p) = ν−j ν−1 = ξ j=1 j j Cν p l Φp−1−l0 α0 (ν ν ι=1 = Φp−1−l0 l=0 = Φp−10 ; Φξ г1/ν b0 ; (9) ι ι=1 l=1 p b0 ι − j) + ξ ν ν−t t ξ j Ht (p)αj(t) . = (10) r=1 j(t)=1 Здесь в рамках рассматриваемого случая приняты индексные соотношения r − 1 = t = l = l(j). Поскольку min r = 1, наименьшее значение l(j) должно принимать в данном случае нулевое значение. 186 Комбинаторное представление суммы взвешенных . . . Сопоставляя (9) и (10), выделяем компоненты, первая пара которых относится к истинным, а вторая пара — к гипотетическим величинам: j l ξ j Cν Φp−1−l0 α0 (ν − j), 1 ν − 1; j (11) p ξν b0 , ι j = ν; (12) ι=1 p−t−1 t Cp−1−k b0 × p−k t ξ j Ht (p)αj(t) = ξ j k=0 t × χ (−1)t+χ Ct χν−j(t) , j(t) Cν 1 j = j(t) ν − 1; (13) χ=1 p−1 t ξ ν Ht (p)αj(t) t=0,j(t)=ν = ξν b0 , p−k j = ν. (14) k=0 При выполненном таким образом выделении компонентов, относящихся к гипотетическим величинам, с учётом принятых выше индексных соотношений нами использовалось равенство вида l l αj(l) = j(l) (−1)1+χ Clχ χν−j(l) Cν , (15) χ=1 которое обобщает ранее полученное соотношение [3]. Продолжим здесь изложение общих результатов производимого анализа случая с индексом 1/ν, а к строгому доказательству (15) в рамках настоящей мы вернемся позже. Рассматривая пределы суммирования в выражениях (9), (10), можно установить, что количество попарно сравниваемых там объектов суммирования Oи1/ν (ν p), Oг1/ν (ν p) составляет как для Φξ (ν p), так и для и1/ν Φξ (ν г1/ν p) одну и ту же величину Oи1/ν (ν p) = Oг1/ν (ν p) = 0,5ν(ν − 1) + 1. При этом из величины Oг1/ν вычитается число объектов (равное ν − 1), которым, согласно выражению (4), исходно ставятся в соответствие нулевые значения; наличие или отсутствие таких компонентов никак не сказывается на результате количественного определения рассматриваемой СВОС. Итак, поскольку наблюдается попарное совпадение друг с другом выражений (11) и (13), (12) и (14) при наличии баланса объектов суммирования, относящихся к истинным и гипотетическим величинам, действительными оказываются также следующие равенства: ν−1 ν−t ξ j Ht (p) j=1 t αj(t) = Φи1/ν (ν p), j = 1, . . . , ν − 1; j(t)=1 187 А. И. Н и к о н о в p ξ 0 H0 (p)αν = Φξ2 (ν и1/ν ν p), j = ν; ι=1 Φξ (ν г1/ν p) = Φξ (ν и1/ν p). В целом же с учётом выражения (8), наконец, имеем Φξ (ν г0 p) + Φξ (ν г1/ν p) = Φξ (ν и0 p) + Φξ (ν и1/ν p). Перейдём к рассмотрению случая p ν, в рамках которого число l ограничивается сверху значением p, а число i — значением (p − 1). Здесь сохраняется прежняя справедливость равенства друг другу истинной Φξ и гипои0 тетической Φξ сумм взвешенных степеней, определяемых как модификации г0 выражений (5) и (7), где вводятся соответствующие поправки на обозначения верхних пределов суммирования, учитывающие особенность рассматриваемого случая. Таким образом, нетрудно убедиться, что Φξ (p ν) = Φξ (p ν). и0 г0 Остаются в силе также и вышеприведённые соотношения, связанные с попарными сравнениями друг с другом выражений вида (11) и (13), (12) и (14). Уточнения требует лишь количество сравниваемых объектов суммирования. Подсчёт объектов суммирования в истинной величине Φξ (p ν), анаи1/ν логичной (9), применительно к настоящему условию p ν даёт значение Oи1/ν (p ν) = 0,5(2ν − p)(p − 1) + 1, а подсчёт объектов суммирования в величине гипотетического характера Φξ (p ν), аналогичной (10), с учётом указанного условия приводит нас к г1/ν равенству, сходному с прежним: Oг1/ν (p ν) = Oи1/ν (p ν). Как и для прежнего случая ν p, из данного результата изъяты (ν − 1) объектов суммирования, которые соответствуют нулевым свободным компонентам, указываемым выражением (4). Следовательно, и в данном случае p ν сохраняется общий баланс объектов суммирования истинного и гипотетического представления СВОС членов арифметической прогрессии. Теперь, чтобы окончательно убедиться в истинности общей гипотезы (2), остаётся доказать справедливость равенства (15) для используемых диапазонов чисел l, j(l), что будет выполнено ниже с использованием метода математической индукции. Сперва рассмотрим случай ν p и в рамках базы индукции определим l 1 параметр αj(1) = αj(1) . Согласно истинному соотношению (3), c учётом исходной системы равенств (4) данный параметр может быть представлен как [1] ν j(1) 1 αj(1) = 0 Cj(0) αj(0) . j(0)=1 188 Комбинаторное представление суммы взвешенных . . . Отсюда видно, что членам конечной последовательности (j(1)) = 0, . . ., ν − 1 j(1) 1 соответствует совокупность чисел αj(1) = Cν . Согласно же заявленному — пока гипотетическому — утверждению (15) имеем для l = 1 1 j(1) (−1)1+1 Cll 1ν Cν . 1 αj(1) = χ=1 То есть для конечной последовательности (j(1)) получена та же конечная последовательность, что и при использовании истинного соотношения (3). Следовательно, для l = 1 наше гипотетическое утверждение (15) следует обоснованно считать истинным, а при max l = 1 (ν = 1 или p = 1) — ещё и окончательным. Далее будем рассматривать случай ν p, ν > 1. Предваряя осуществление индукционного шага, найдём отношение велиl+1 l чин αj(l) и αj(l) , первоначально представляемых в заявленном гипотетическом виде: l+1 αj(l+1)=j(1) (ν) l αj(1) (ν) 0 = j(l) = j(l + 1) l l+1+χ C χ χν−j(l) χ=1 (−1) l+1 ; l l+χ C χ χν−j(l) χ=1 (−1) l ν−l−1⇒l ν − 1, l+1 ν. Как видим, число (l + 1) остаётся здесь в интервале индексов определяемых l+1 l параметров вида αj(l) , αj(l) . Доказанное ранее [3] позволяет утверждать, что ψ ψ χ (−1)ψ+χ Cψ αν−j(l) = α0 (ν − j(l)), ψ ∈ {l, l + 1}. χ=1 Но тогда l+1 αj(l) (ν) l αj(l) = l α0 (ν − j(l)) . l α0 (ν − j(l)) (16) Выявление отношения истинных значений параметров из правой части (16) оказалось возможным исходя из отношения параметров гипотетического характера из левой части (16), т.е. гипотетическое отношение определилось истинными величинами. Это позволяет облегчить завершение производимого доказательства. Теперь, непосредственно выполняя шаг индукции, положим, что утверждение (15) для случая ν p истинно. Тогда с учётом (16) параметр l+1 αj(l) = l+1 l αj(l) α0 (ν − j(l)) l α0 (ν − j(l)) , l занимающий следующую за l позицию в последовательности αj(l) (v) с фиксированным значением j(l), должен полагаться истинным, а данный индукционный шаг — уже законченным. 189 А. И. Н и к о н о в Для случая p ν (max l = p) все вышеприведённые соотношения, касающегося базы индукции, получения частного (16), выполнения шага индукции, остаются в силе. Имеем также 0 ν−l−1 j(l) = j(l + 1) ⇒ l ν − 1, l+1 ν, однако более сильные ограничения, накладываемые на l, l + 1, могут быть представлены в виде p ν: l p − 1, l+1 p. Как и прежде, число (l + 1) остаётся в интервале индексов определяемых величин. На этом доказательство справедливости равенства (15), а вместе с тем и доказательство истинности общей гипотезы (2) можно считать завершённым. l В заключение укажем на одну особенность набора величин αj(l) (ν), l + j(l) = ν, которые представляют собой, с одной стороны, согласно выражеj(l) нию (15), произведения сумм компонентов (−1)l+χ Clχ χl и Cν , а с другой — размещения из ν элементов по l [4], то есть l αj(l) (ν) = Al = ν ν! , (ν − l)! l + j(l) = ν. Итак, убывающий факториал Al может быть представлен здесь именно ν как сумма компонентов, входящих в выражение (15).

About the authors

Alexander I Nikonov

Samara State Technical University

Email: nikonovai@mail.ru
244, Molodogvardeyskaya st., Samara, 443100, Russia
(Dr. Techn. Sci.), Professor, Dept. of Electronic Systems and Information Security

References

  1. А. И. Никонов, “Преобразование суммы взвешенных степеней натуральных чисел с одинаковыми показателями” // Вестн. Сам. гос. техн. ун-та. Сер. Физ.-мат. науки, 2010. № 1(20). С. 258–262.
  2. А. И. Никонов, “Об одном свойстве взвешенных сумм одинаковых степеней как матричных произведений” // Вестн. Сам. гос. техн. ун-та. Сер. Физ.-мат. науки, 2010. № 5(21). С. 313–317.
  3. А. И. Никонов, “Приведение суммы взвешенных одинаковых степеней к явному комбинаторному представлению” // Вестн. Сам. гос. техн. ун-та. Сер. Физ.-мат. науки, 2012. № 3(28). С. 163–169.
  4. А. И. Никонов, Дискретная математика. Самара: СамГТУ, 2011. 106 с.

Statistics

Views

Abstract - 11

PDF (Russian) - 1

Cited-By


PlumX

Dimensions

Refbacks

  • There are currently no refbacks.

Copyright (c) 2013 Samara State Technical University

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies