Kolejna suma. Podwójna. Maksimum indeksów pod sumą.

[Zaratustra]

Obliczyć \(\displaystyle{ \sum_{i=1}^M\sum_{k=1}^N\max\{i,k\}}\). Sugerowana odpowiedź: \(\displaystyle{ \frac{(N-1)N(N+1)}{6}+\frac{N\cdot M\cdot(M+1)}{2}}\) (tak - bawię się starym Pawłowskim : P)

1. podejście:
Najgorsze, że mam zły wynik, ale nie widzę, gdzie popełniłem błąd - wskazałby coś, w którym momencie "napisałem nieprawdę"? :C
\(\displaystyle{ \sum_{i=1}^M\sum_{k=1}^N\max\{i,k\} = \sum_{i=1}^M\left(\max\{i,1\}+\max\{i,2\}+\cdots+\max\{i,N\}\right)}\)
Rozpatruję kolejno:
\(\displaystyle{ i=1}\): \(\displaystyle{ \max\{i,1\}+\max\{i,2\}+\cdots+\max\{i,N\}=1+2+\cdots+N=1\cdot 1 + (N-1)\frac{(2+N)}{2}}\).

\(\displaystyle{ i=2}\): \(\displaystyle{ \max\{i,1\}+\max\{i,2\}+\cdots+\max\{i,N\}=2+2+3\cdots+N=2\cdot 2+(N-2)\frac{(3+N)}{2}}\).

\(\displaystyle{ i=3}\): \(\displaystyle{ \max\{i,1\}+\cdots+\max\{i,N\}=3+3+3+4+\cdots+N=3\cdot3 +(N-3)\cdot\frac{(4+N)}{2}}\).
\(\displaystyle{ \;\vdots}\)
\(\displaystyle{ i=N}\): \(\displaystyle{ \max\{i,1\}+\max\{i,2\}+\cdots+\max\{i,N\}=N+N+\cdots+N=N\cdot N +(N-N)\cdot\ldots}\)(\(\displaystyle{ N}\)-razy)

Wnioskuję, że dla \(\displaystyle{ i\leq N}\) jest \(\displaystyle{ \sum_{i=1}^M\sum_{k=1}^N\max\{i,k\} = \sum_{i=1}^M\left(i^2+(N-i)\frac{(i+1+N)}{2}\right)}\)

ALE sprawdziłem, że dla \(\displaystyle{ i>N}\) wzór się psuje. Jenak
\(\displaystyle{ \sum_{i=1}^M\sum_{k=1}^N\max\{i,k\}=\sum_{k=1}^N\sum_{i=1}^M\max\{k,i\}}\) - wzór powinien być symetryczny względem \(\displaystyle{ N,M}\) Na razie zakładam, że \(\displaystyle{ M\leq N}\), \(\displaystyle{ i=1,2,\ldots,M}\).

\(\displaystyle{ \sum_{i=1}^M\left(i^2+(N-i)\frac{(i+1+N)}{2}\right)=\sum_{i=1}^Mi^2 + \sum_{i=1}^M\left(\frac{Ni+N+N^2-i^2-i-Ni}{2}\right)=}\)
\(\displaystyle{ =\sum_{i=1}^Mi^2-\sum_{i=1}^M\frac{i^2}{2}+\sum_{i=1}^M\frac{N(N+1)}{2}=\sum_{i=1}^M\frac{i^2}{2}+\frac{M\cdot N(N+1)}{2}=}\)
\(\displaystyle{ =\frac{M(M+1)(2M+1)}{6}+\frac{M\cdot N(N+1)}{2}}\)

Wzór jest oczywiście zły. Dla \(\displaystyle{ N=3}\), \(\displaystyle{ M=2}\) suma z tezy jest równa \(\displaystyle{ 13}\) a mój wzór nie daje nawet liczby naturalnej... Jasne - nie doszedłem do właściwego wzoru, ale gdzie dokładnie się mylę? Już drugi raz to liczę

2. podejście:
Spróbowałem też takiej tożsamości \(\displaystyle{ \max\{i,k\}=\frac{|i-k|+i+k}{2}}\), poupraszczałem -
zacząłem walczyć ze składnikiem \(\displaystyle{ \sum _{i=0}^M\sum _{k=0}^N\frac{\left|i-k\right|}{2}}\) ale to chyba nie jest droga.

3. podejście:

\(\displaystyle{ \sum_{i=1}^M\sum_{k=1}^N\max\{i,k\}=\sum_{i< k \\ 1\leq k\leq N}k+\sum_{k\leq i \\ 1\leq i\leq M}i}\) - staram się to albo sprowadzić do jakieś prostej postaci alb myślałem, czy tych wyrażeń po prawej stronie nie da się przekształcić na podwójne sumy i np. jakaś tożsamość (np. ostatnio pytałem o tożsamość \(\displaystyle{ \sum_{j=1}^{n} \sum_{i=1}^{j}i= \sum_{j=1}^{n}(n-j+1)j}\) z tego samego zestawu) - i by "wyszło" - ale to już na oślep zgaduję, podstawiam, przekształcam :C

Jak to "należy" zrobić? Będę bardzo wdzięczny, jeśli komuś będzie się chciało przebrnąć

[Premislav]

Elegancko można to zrobić w oparciu o jakąś interpretację geometryczną, ale z takich rzeczy to ja jestem do bani.

Można tak:
jeśli \(\displaystyle{ M\ge N}\), to
\(\displaystyle{ \sum_{i=1}^M\sum_{k=1}^N\max\{i,k\}= \sum_{i=1}^{N-1} \sum_{k=1}^{i}\max\left\{ i, k\right\}+ \sum_{i=1}^{N-1} \sum_{k=i+1}^{N}\max\left\{ i, k\right\}+ \sum_{i=N}^{M} \sum_{k=1}^{N}\max\left\{ i, k\right\}\\=\sum_{i=1}^{N-1} \sum_{k=1}^{i}i+ \sum_{i=1}^{N-1} \sum_{k=i+1}^{N}k+ \sum_{i=N}^{M} \sum_{k=1}^{N}i\\=\sum_{i=1}^{N-1} i^2+ \sum_{i=1}^{N-1} \frac{N(N+1)-i(i+1)}{2} + N\sum_{i=N}^{M} i\\= \frac{(N+1)N(N-1)}{2}+ \frac{N\left( M(M+1)-N(N-1)\right) }{2}+ \sum_{i=2}^{N-1}{i\choose 2}}\)
i pozostaje skonstatować, że
\(\displaystyle{ \sum_{i=2}^{N-1}{i\choose 2}={N\choose 3}}\)
Ten wzór ma prostą interpretację kombinatoryczną: wybieramy trzy elementy ze zbioru \(\displaystyle{ N}\)-elementowego. Z jednej strony możemy to zrobić na \(\displaystyle{ {N\choose 3}}\) sposobów, z drugiej strony ustawmy te elementy w rzędzie i rozpatrzmy ostatni element, który wybierzemy: skoro mamy wybrać \(\displaystyle{ 3}\) elementy, to numer ostatniego wybranego elementu będzie postaci \(\displaystyle{ i+1}\) dla \(\displaystyle{ i\in\left\{ 2,3,\ldots N-1\right\}}\). Zatem musimy też wybrać dwa spośród i poprzedzających elementów, co możemy uczynić na \(\displaystyle{ {i \choose 2}}\) sposobów.

Ostatecznie więc szukana suma jest równa
\(\displaystyle{ \frac{(N+1)N(N-1)}{2}+ \frac{N\left( M(M+1)-N(N-1)\right) }{2}+ \frac{N(N-1)(N-2)}{6} \\=\frac{(N-1)N(N+1)}{6}+\frac{N\cdot M\cdot(M+1)}{2}}\)
tak jak chcieliśmy.

Natomiast gdy \(\displaystyle{ M<N}\), to sobie wystarczy pozmieniać symbole/zmienić kolejność sumowania, bo ta suma powinna być symetryczna.

[a4karo]

A może tak? Oznaczmy szukaną sumę przez S(N,M) zróbmy obrazek (zakładamy, że \(\displaystyle{ N\geq M}\))

1.jpg (29.12 KiB) Przejrzano 55 razy

Mamy
\(\displaystyle{ \yellow{S(N,M)}+\red{S(N,M)}-\green{S(M,M)}+\blue{\sum}=S(N,N)}\)

Widać, że \(\displaystyle{ S(N,M)=S(M,N)}\)
Jeżeli od każdego elementu w niebieskiej sumie odejmiemy \(\displaystyle{ M}\), to dostaniemy \(\displaystyle{ S(N-M,N-M)}\).
Zatem \(\displaystyle{ {\blue \sum}= M(N-M)^2 + S(N-M,N-M)}\)

Zatem
\(\displaystyle{ S(N,M)=S(N,N)+S(M,M)-S(N-M,N-M)-M(N-M)^2}\).

Pozostaje wyliczenie \(\displaystyle{ S(k,k)=\sum_{i=1}^k i(2i-1)=2\sum_{i=1}^ki^2-\sum_{i=1}^ki}\) , a to już jest proste

[Premislav]

Jednakowoż to rozważanie przypadków mi się nie podoba, a z drugiej strony geometrycznie nic nie wymyślę, ponieważ jestem pozbawiony wyobraźni geometrycznej. Może coś takiego alternatywnie:
mamy
\(\displaystyle{ \sum_{i=1}^M\sum_{k=1}^N\max\{i,k\}+\sum_{i=1}^M\sum_{k=1}^N\min\{i,k\}\\=\sum_{i=1}^M\sum_{k=1}^N(i+k)= \frac{NM(M+1)}{2}+ \frac{MN(N+1)}{2}}\)
a ponadto
\(\displaystyle{ \sum_{i=1}^M\sum_{k=1}^N\min\{i,k\}=\sum_{i=1}^M\sum_{k=1}^N\left( \int_{0}^{+\infty} 1{\hskip -2.5 pt}\hbox{l}_{[0,i)}(x)1{\hskip -2.5 pt}\hbox{l}_{[0,k)}(x)\,\dd x\right)\\= \int_{0}^{\infty}\left( \sum_{i=1}^{M} \sum_{k=1}^{N}1{\hskip -2.5 pt}\hbox{l}_{[0,i)}(x) 1{\hskip -2.5 pt}\hbox{l}_{[0,k)}(x) \right)\,\dd x\\= \int_{0}^{\infty}\left( \sum_{i=1}^{M}1{\hskip -2.5 pt}\hbox{l}_{[0,i)}(x) \right)\left( \sum_{k=1}^{N} 1{\hskip -2.5 pt}\hbox{l}_{[0,k)}(x) \right) \,\dd x\\= \int_{0}^{\infty}\left( \sum_{i=1}^{M}(M-i+1)1{\hskip -2.5 pt}\hbox{l}_{[i-1,i)}(x) \right)\left( \sum_{k=1}^{N}(N-k+1) 1{\hskip -2.5 pt}\hbox{l}_{[k-1,k)}(x) \right) \,\dd x\\= \int_{0}^{\infty}\left( \sum_{i=1}^{M} \sum_{k=1}^{N} (M-i+1)1{\hskip -2.5 pt}\hbox{l}_{[i-1,i)}(x)(N-k+1) 1{\hskip -2.5 pt}\hbox{l}_{[k-1,k)}(x) \right)\,\dd x}\)
Teraz zauważmy, że ten iloczyn indykatorów jest niezerowy wtedy i tylko wtedy, gdy \(\displaystyle{ i=k}\), stąd możemy ostatnią całkę zapisać w postaci:
\(\displaystyle{ \int_{0}^{\infty} \left(\sum_{i=1}^{\min\left\{M,N\right\}}(M-i+1)(N-i+1)1{\hskip -2,5pt}\hbox{l}_{[i-1, i)}(x)\right) \,\dd x\\= \sum_{i=1}^{\min\left\{ M,N\right\} }(M-i+1)(N-i+1)\\= \sum_{i=1}^{\min\left\{ M,N\right\} }i^2+ \sum_{i=1}^{\min\left\{ M,N\right\} }(M+1)(N+1)-(M+N+2) \sum_{i=1}^{\min\left\{ M,N\right\} }i}\)

-- 30 cze 2019, o 20:23 --

Wow, no sposób a4karo pozamiatał. : o

[a4karo]

A może tak? Oznaczmy szukaną sumę przez S(N,M) zróbmy obrazek (zakładamy, że \(\displaystyle{ N\geq M}\))

1.jpg (29.12 KiB) Przejrzano 54 razy

Mamy
\(\displaystyle{ \yellow{S(N,M)}+\red{S(N,M)}-\green{S(M,M)}+\blue{\sum}=S(N,N)}\)

Widać, że \(\displaystyle{ S(N,M)=S(M,N)}\)
Jeżeli od każdego elementu w niebieskiej sumie odejmiemy \(\displaystyle{ M}\), to dostaniemy \(\displaystyle{ S(N-M,N-M)}\).
Zatem \(\displaystyle{ {\blue \sum}= M(N-M)^2 + S(N-M,N-M)}\)

Zatem
\(\displaystyle{ {\red 2}S(N,M)=S(N,N)+S(M,M)-S(N-M,N-M)-M(N-M)^2}\).

Pozostaje wyliczenie \(\displaystyle{ S(k,k)=\sum_{i=1}^k i(2i-1)=2\sum_{i=1}^ki^2-\sum_{i=1}^ki}\) , a to już jest proste

Dwójki zabrakło we wzorku. Sorry