Problem B. 5353. (December 2023)

B. 5353. Prove the following equality for every positive integer \(\displaystyle n>1\):

\(\displaystyle \sum\limits_{i=1}^n\, \sum\limits_{j=1}^n|i-j|=\frac{n(n^2-1)}{3}.\)

Submitted by Mihály Bencze, Brassó

(4 pont)

Deadline expired on January 10, 2024.

Sorry, the solution is available only in Hungarian. Google translation

1. megoldás. Az állítást \(\displaystyle n\)-re vonatkozó teljes indukcióval igazoljuk \(\displaystyle n=1\)-től kezdődően. Az indukció kezdő lépése világos: \(\displaystyle n=1\) esetén mindkét oldalon 0 áll. Tegyük most fel, hogy valamely \(\displaystyle n\geq 1\)-re már igazoltuk az állítást, és lássuk be, hogy \(\displaystyle (n+1)\)-re is teljesül.

Tekintsük a bal oldalon az új tagokat: \(\displaystyle i=j=n+1\)-re 0-t kapunk, \(\displaystyle i<j=n+1\) melletti új tagok összege \(\displaystyle 1+2+\dots+n=\frac{n(n+1)}{2}\), a szimmetria miatt \(\displaystyle j<i=n+1\)-re szintén \(\displaystyle \frac{n(n+1)}{2}\) az új tagok összege. Tehát az új tagok összege \(\displaystyle n(n+1)\). Az indukciós feltevést használva tehát a bal oldalon az összes tag összege

\(\displaystyle \frac{n(n^2-1)}{3}+n(n+1)=\frac{n(n+1)(n-1+3)}{3}=\frac{(n+1)((n+1)^2-1)}{3},\)

így az indukciós lépést igazoltuk. Ezzel a feladat állítását bizonyítottuk.

2. megoldás. Számoljuk meg kétféleképpen, hány olyan \(\displaystyle (i,k,j)\) egészekből álló számhármas van, melyre \(\displaystyle 1\leq i\leq k<j\leq n\). Rögzített \(\displaystyle 1\leq i<j\leq n\) esetén a megfelelő \(\displaystyle k\) értékek száma \(\displaystyle j-i=|i-j|\), így a válasz \(\displaystyle \sum\limits_{1\leq i<j\leq n}|i-j|\).

Ez éppen a feladat állításában az egyenlőség bal oldalán szereplő kifejezés értékének a fele, az \(\displaystyle i\) és \(\displaystyle j\) közötti szimmetriát, valamint azt használva, hogy az \(\displaystyle i=j\) esetén kapott tagok értéke 0.

Másrészről, pontosan akkor lesz \(\displaystyle 1\leq i\leq k<j\leq n\), ha \(\displaystyle 1\leq i<k+1<j+1\leq n+1\), vagyis, ha \(\displaystyle i,k+1,j+1\) az 1 és \(\displaystyle n+1\) közötti egész számok közül választott három hosszú szigorúan növő sorozat. Ezek száma \(\displaystyle \binom{n+1}{3}=\frac{n(n^2-1)}{6}\), ami pedig a bizonyítandó állítás jobb oldalán álló kifejezés fele. Ezzel a feladat állítását igazoltuk.

Statistics:

122 students sent a solution.
4 points:	106 students.
3 points:	4 students.
2 points:	3 students.
1 point:	1 student.
0 point:	1 student.
Not shown because of missing birth date or parental permission:	4 solutions.

Problems in Mathematics of KöMaL, December 2023