How to prove this identity nicely? The Next CEO of Stack OverflowProve this $sum_1le i<jle nleft((x_j-x_i)-(x_j-x_i)^2right)lefracn^2-112$Simplifying a summation - stuck after change of summation indexHow do I prove that $sum limits_i=1^np_ileft(x_i-barxright)^2 = frac12 sum limits_i, j=1^n p_ip_jleft(x_i-x_jright)^2$?how to solve this multivariate quadratic equation?Prove this identity: $sin^4x = dfrac18(3 - 4cos2x + cos4x)$.Using an identity to simplify the sumHow to solve an equation with $x^4$?How could $r$ have two values?How to prove this by inductionProve or disprove that $int_0^pilog^2(cos x)mathrm dxstackrel?=2int_0^pi/2log^2(cos x)mathrm dx$Euler's Number Identity
Man transported from Alternate World into ours by a Neutrino Detector
Is a distribution that is normal, but highly skewed, considered Gaussian?
how one can write a nice vector parser, something that does pgfvecparseA=B-C; D=E x F;
Is it professional to write unrelated content in an almost-empty email?
(How) Could a medieval fantasy world survive a magic-induced "nuclear winter"?
What difference does it make using sed with/without whitespaces?
What does "shotgun unity" refer to here in this sentence?
Defamation due to breach of confidentiality
In the "Harry Potter and the Order of the Phoenix" video game, what potion is used to sabotage Umbridge's speakers?
Aggressive Under-Indexing and no data for missing index
The Ultimate Number Sequence Puzzle
What is the process for purifying your home if you believe it may have been previously used for pagan worship?
Why do we say 'Un seul M' and not 'Une seule M' even though M is a "consonne"
If Nick Fury and Coulson already knew about aliens (Kree and Skrull) why did they wait until Thor's appearance to start making weapons?
Can you teleport closer to a creature you are Frightened of?
Why don't programming languages automatically manage the synchronous/asynchronous problem?
How do you define an element with an ID attribute using LWC?
How to use ReplaceAll on an expression that contains a rule
Help! I cannot understand this game’s notations!
Where do students learn to solve polynomial equations these days?
Is there a way to save my career from absolute disaster?
Is dried pee considered dirt?
What would be the main consequences for a country leaving the WTO?
Cannot shrink btrfs filesystem although there is still data and metadata space left : ERROR: unable to resize '/home': No space left on device
How to prove this identity nicely?
The Next CEO of Stack OverflowProve this $sum_1le i<jle nleft((x_j-x_i)-(x_j-x_i)^2right)lefracn^2-112$Simplifying a summation - stuck after change of summation indexHow do I prove that $sum limits_i=1^np_ileft(x_i-barxright)^2 = frac12 sum limits_i, j=1^n p_ip_jleft(x_i-x_jright)^2$?how to solve this multivariate quadratic equation?Prove this identity: $sin^4x = dfrac18(3 - 4cos2x + cos4x)$.Using an identity to simplify the sumHow to solve an equation with $x^4$?How could $r$ have two values?How to prove this by inductionProve or disprove that $int_0^pilog^2(cos x)mathrm dxstackrel?=2int_0^pi/2log^2(cos x)mathrm dx$Euler's Number Identity
$begingroup$
Show that$$sum_1le i<jle nleft((x_j-x_i)-(x_j-x_i)^2right)=left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_i\=-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2+frac14nsum_i=1^n(n-2i+1)^2.$$
I wonder how this identity comes up with the first and second recipes? Can anyone explain this in detail? I got this identity when I was reading the problem here. Thanks.
algebra-precalculus parsevals-identity
edited Mar 25 at 2:35
Saad
20.3k92352
asked Mar 20 at 14:18
function sugfunction sug
3151439
$endgroup$
add a comment |
$begingroup$
Show that$$sum_1le i<jle nleft((x_j-x_i)-(x_j-x_i)^2right)=left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_i\=-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2+frac14nsum_i=1^n(n-2i+1)^2.$$
I wonder how this identity comes up with the first and second recipes? Can anyone explain this in detail? I got this identity when I was reading the problem here. Thanks.
algebra-precalculus parsevals-identity
edited Mar 25 at 2:35
Saad
20.3k92352
asked Mar 20 at 14:18
function sugfunction sug
3151439
$endgroup$
$begingroup$
Now I bounty because I can't find this the last identity
$endgroup$
– function sug
Mar 25 at 1:07
add a comment |
$begingroup$
Show that$$sum_1le i<jle nleft((x_j-x_i)-(x_j-x_i)^2right)=left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_i\=-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2+frac14nsum_i=1^n(n-2i+1)^2.$$
I wonder how this identity comes up with the first and second recipes? Can anyone explain this in detail? I got this identity when I was reading the problem here. Thanks.
algebra-precalculus parsevals-identity
edited Mar 25 at 2:35
Saad
20.3k92352
asked Mar 20 at 14:18
function sugfunction sug
3151439
$endgroup$
Show that$$sum_1le i<jle nleft((x_j-x_i)-(x_j-x_i)^2right)=left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_i\=-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2+frac14nsum_i=1^n(n-2i+1)^2.$$
I wonder how this identity comes up with the first and second recipes? Can anyone explain this in detail? I got this identity when I was reading the problem here. Thanks.
algebra-precalculus parsevals-identity
algebra-precalculus parsevals-identity
edited Mar 25 at 2:35
Saad
20.3k92352
asked Mar 20 at 14:18
function sugfunction sug
3151439
edited Mar 25 at 2:35
Saad
20.3k92352
asked Mar 20 at 14:18
function sugfunction sug
3151439
edited Mar 25 at 2:35
Saad
20.3k92352
edited Mar 25 at 2:35
Saad
20.3k92352
edited Mar 25 at 2:35
Saad
20.3k92352
20.3k92352
asked Mar 20 at 14:18
function sugfunction sug
3151439
asked Mar 20 at 14:18
function sugfunction sug
3151439
asked Mar 20 at 14:18
function sugfunction sug
3151439
3151439
$begingroup$
Now I bounty because I can't find this the last identity
$endgroup$
– function sug
Mar 25 at 1:07
add a comment |
$begingroup$
Now I bounty because I can't find this the last identity
$endgroup$
– function sug
Mar 25 at 1:07
$begingroup$
Now I bounty because I can't find this the last identity
$endgroup$
– function sug
Mar 25 at 1:07
$begingroup$
Now I bounty because I can't find this the last identity
$endgroup$
– function sug
Mar 25 at 1:07
add a comment |
5 Answers
5
active
oldest
votes
$begingroup$
Taking a low tech approach, let our original summation be
$ s_n := u_n - t_n $ where
$$ u_n := sum_1le i<jle n (x_j-x_i), quad
t_n := sum_1le i<jle n (x_j-x_i)^2. tag1$$
Also, let
$$ v_n := sum_1le ine jle n x_i x_j =
left(sum_1le kle n x_k right)^2 - sum_1le kle nx_k^2. tag2$$
Now, $;u_n = sum_ile kle n c_k,n x_k $ where
$$ c_k,n := (sum_1le ile k 1) - (sum_kle jle n 1) = k-(n-k+1) = 2k-n-1 tag3$$
which counts how many times $ k $ appears as $ j $
minus the times it appears as $ i $ in equation $(1).$
Thus, $$ u_n = sum_1le kle n (2k-n-1) x_k =
-sum_1le kle n (n-2k+1) x_k . tag4$$
Now, we get $ t_n = sum_1le i<jle n (x_j^2 + x_i^2 - 2x_jx_i) $ by expanding the square in equation $(1)$ and
similarly to how we got equation $(3)$, we now get
$$ t_n !=! sum_k=1^n (k!+!(n!-!k!+!1)) x_k^2 +! sum_1le ine jle n x_ix_j !=! (n!+!1)!sum_k=1^n x_k^2!+! v_n. tag5$$
Combining this with equation $(2)$ we get
$$ t_n = nsum_1le kle n x_k^2 - sum_1le kle nx_k^2. tag6$$ Combining this with equation $(4)$ we get
$$ s_n = left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1) x_i, tag7$$
which is the first identity requested.
Continuing, let $ y_i = y_i,n := x_i -frac1nsum_j=1^n x_j. $ There is a famous formula in statistics
$$ t_n = n sum_1le ile n Big(x_i-frac1nsum_j=1^n x_jBig)^2 = n sum_1le ile n y_i^2. tag8$$
Notice that $$ sum_i=1^n (n-2i+1) = 0. tag9$$
Combining this with equation $(4)$ we get
$$ u_n = -sum_1le ile n (n-2i+1) y_i. tag10$$
Combining this with equation $(8)$ we get
$$ s_n = -n sum_i=1^n y_i^2 -sum_1le ile n (n-2i+1) y_i. tag11$$
Continuing, let $ z_i = z_i,n := y_i,n +fracn-2i+12n. $
Now
$$ z_i^2 = y_i^2 + y_ifracn-2i+1n + frac(n-2i+1)^24n^2. tag12$$
Summing this over $ i $ and multipling by $ n $ gives us
$$ n sum_i=1^n z_i^2 !=!
n sum_i=1^n y_i^2 + sum_i=1^n y_i(n!-!2i!+!1)
!+!
frac14nsum_i=1^n (n!-!2i!+!1)^2. tag13$$
Finally, combining equations $(11)$ and $(13)$ we get
$$ s_n = - n sum_i=1^n z_i^2 +
frac14nsum_i=1^n (n-2i+1)^2. tag14$$
which is the second identity since
$ z_i = x_i -frac1nsum_j=1^n x_j +fracn-2i+12n.$
P.S.
The identities and proofs are simplified if we use a
non-standard indexing for the $ x_i. $ So suppose we have an indexed set of $ n $ numbers
$ x_-n+1, x_-n+3, dots, x_n-3, x_n-1. $
For $ n=0 $ we have just $x_0. $ For $ n=1 $ we have the
set $ x_-1, x_1 $ and so on. It is understood that we will
sum from $ -n+1 $ to $ n-1 $ in steps of $2$. So define our new
$$ u_n :=! sum_-n+1le i<jle n-1 (x_j!-!x_i), ;
t_n := !sum_-n+1le i<jle n-1 (x_j!-!x_i)^2. tag15$$
The first identity is now
$$ s_n = u_n - t_n = Big(sum_i i x_iBig) +
Big(sum_i x_iBig)^2 - nBig(sum_i x_i^2Big).
tag16$$
The second identity is now
$$ s_n = -n sum_i Big(x_i-frac1nsum_j x_j-fraci2nBig)^2 + fracn^2-112.
tag17$$
answered Mar 28 at 1:14
SomosSomos
14.7k11337
$endgroup$
add a comment |
$begingroup$
This was a pain,
but here it is.
$beginarray\
s(n)
&=sum_1le i<jle nleft((x_j-x_i)-(x_j-x_i)^2right)\
&=sum_i=1^n sum_j=i+1^n((x_j-x_i)-(x_j-x_i)^2)\
&=sum_i=1^n sum_j=i+1^n(x_j-x_i)-sum_i=1^n sum_j=i+1^n(x_j-x_i)^2\
&=s_1(n)-s_2(n)\
s_1(n)
&=sum_i=1^n sum_j=i+1^n(x_j-x_i)\
&=sum_i=1^n sum_j=i^n(x_j-x_i)\
&=sum_i=1^n sum_j=i^nx_j-sum_i=1^n sum_j=i^nx_i\
&=sum_j=1^n sum_i=1^jx_j-sum_i=1^n (n-i+1)x_i\
&=sum_j=1^n x_jsum_i=1^j1-sum_i=1^n (n-i+1)x_i\
&=sum_j=1^n jx_j-sum_i=1^n (n-i+1)x_i\
&=sum_i=1^n ix_i-sum_i=1^n (n-i+1)x_i\
&=sum_i=1^n (i-n+i-1)x_i\
&=sum_i=1^n (2i-n-1)x_i\
s_2(n)
&=sum_i=1^n sum_j=i+1^n(x_j-x_i)^2\
&=sum_i=1^n sum_j=i^n(x_j-x_i)^2\
&=sum_i=1^n sum_j=i^n(x_j^2-2x_jx_i+x_i^2)\
&=sum_i=1^n sum_j=i^nx_j^2-2sum_i=1^n sum_j=i^nx_jx_i+sum_i=1^n sum_j=i^nx_i^2\
&=s_3(n)-2s_4(n)+s_5(n)\
s_3(n)
&=sum_i=1^n sum_j=i^nx_j^2\
&=sum_j=1^n sum_i=1^jx_j^2\
&=sum_j=1^n jx_j^2\
s_4(n)
&=sum_i=1^n sum_j=i^nx_jx_i\
&=sum_i=1^n x_isum_j=i^nx_j\
&=sum_i=1^n x_i(sum_j=1^nx_j-sum_j=1^i-1x_j)\
&=sum_i=1^n x_isum_j=1^nx_j-sum_i=1^n sum_j=1^i-1x_ix_j\
&=(sum_i=1^n x_i)^2-sum_j=1^n-1 sum_i=j+1^nx_ix_j\
&=(sum_i=1^n x_i)^2-sum_j=1^n-1 x_jsum_i=j+1^nx_i\
&=(sum_i=1^n x_i)^2-sum_j=1^n x_jsum_i=j+1^nx_i\
&=(sum_i=1^n x_i)^2-sum_j=1^n x_j(sum_i=j^nx_i-x_j)\
&=(sum_i=1^n x_i)^2-sum_j=1^n x_jsum_i=j^nx_i+sum_j=1^n x_j^2\
&=(sum_i=1^n x_i)^2-sum_i=1^n x_isum_j=i^nx_j+sum_j=1^n x_j^2\
&=(sum_i=1^n x_i)^2-s_4(n)+sum_j=1^n x_j^2\
textso\
s_4(n)
&=frac12((sum_i=1^n x_i)^2+sum_i=1^n x_i^2)\
s_5(n)
&=sum_i=1^n sum_j=i^nx_i^2\
&=sum_i=1^n (n-i+1)x_i^2\
textso\
s_2(n)
&=s_3(n)-2s_4(n)+s_5(n)\
&=sum_j=1^n jx_j^2-((sum_i=1^n x_i)^2+sum_i=1^n x_i^2)+sum_i=1^n (n-i+1)x_i^2\
&=-((sum_i=1^n x_i)^2+sum_i=1^n x_i^2)+sum_i=1^n (n+1)x_i^2\
&=-(sum_i=1^n x_i)^2+nsum_i=1^n x_i^2\
textso\
s(n)
&=s_1(n)-s_2(n)\
&=sum_i=1^n (2i-n-1)x_i-(nsum_i=1^n x_i^2-(sum_i=1^n x_i)^2)\
&=(sum_i=1^n x_i)^2-nsum_i=1^n x_i^2+sum_i=1^n (2i-n-1)x_i\
endarray
$
Whew!
answered Mar 21 at 3:52
marty cohenmarty cohen
74.9k549130
$endgroup$
$begingroup$
Nice! can you post the second $=?$
$endgroup$
– function sug
Mar 21 at 8:22
$begingroup$
Sorry. I'm all burnt out on this.
$endgroup$
– marty cohen
Mar 21 at 9:47
add a comment |
$begingroup$
We take an algebraic approach and consider the expressions as quadratic polynomials in $n$ variables $x_1,x_2,ldots,x_n$. We show equality by comparing the coefficients of corresponding terms.
It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.
We introduce $f_1,f_2,f_3$ as
beginalign*
f_1(x_1,ldots,x_n)&=sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
f_2(x_1,ldots,x_n)&=left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_i\
f_3(x_1,ldots,x_n)&=-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2+frac14nsum_i=1^n(n-2i+1)^2
endalign*
We start with the square terms.
We obtain for $1leq kleq n$:
beginalign*
colorblue[x_k^2]f_1(x_1,ldots,x_n)&=[x_k^2]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&=-[x_k^2]sum_1leq i<jleq nleft(x_j-x_iright)^2\
&=-[x_k^2]sum_1leq i<kleft(x_k-x_iright)^2-[x_k^2]sum_k<jleq nleft(x_j-x_kright)^2\
&=-(k-1)-(n-k)\
&,,colorblue=1-n\
colorblue[x_k^2]f_2(x_1,ldots,x_n)&=[x_k^2]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&=[x_k^2]sum_i=1^nx_i^2-n[x_k^2]sum_i=1^nx_i^2\
&,,colorblue=1-n\
colorblue[x_k^2]f_3(x_1,ldots,x_n)&=[x_k^2]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_k^2]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&=-n[x_k^2]sum_i=1^nleft(x_i^2-2x_icdotfrac1nsum_j=1^nx_j+left(frac1nsum_j=1^nx_jright)^2right)\
&=-n[x_k^2]sum_i=1^nx_i^2+2[x_k^2]sum_i=1^nx_isum_j=1^nx_j-frac1n[x_k^2]sum_i=1^nleft(sum_j=1^nx_jright)^2\
&=-n+2-1\
&,,colorblue=1-n
endalign*
Now we check the mixed quadratic terms.
We obtain for $1leq k<lleq n$:
beginalign*
colorblue[x_kx_l]f_1(x_1,ldots,x_n)&=[x_kx_l]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&=-[x_kx_l]sum_1leq i<jleq nleft(x_j-x_iright)^2\
&=2[x_kx_l]sum_1leq i<jleq nx_ix_j\
&,,colorblue=2\
colorblue[x_kx_l]f_2(x_1,ldots,x_n)&=[x_kx_l]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&=[x_kx_l]left(sum_i=1^nx_iright)^2\
&=[x_kx_l]left(sum_i=1^nx_i^2+2sum_1leq i<jleq nx_ix_jright)\
&,,colorblue=2\
colorblue[x_kx_l]f_3(x_1,ldots,x_n)&=[x_k^2]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_kx_l]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&=[x_kx_l]sum_i=1^nleft(2x_isum_j=1^nx_jright)\
&,,colorblue=2
endalign*
... the linear terms ...
We obtain for $ 1leq kleq n$:
beginalign*
colorblue[x_k]f_1(x_1,ldots,x_n)&=[x_k]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&=[x_k]sum_1leq i<jleq nleft(x_j-x_iright)\
&=[x_k]sum_1leq i<kleft(x_k-x_iright)+[x_k]sum_k<jleq nleft(x_j-x_kright)\
&=(k-1)-(n-k)\
&,,colorblue=2k-n-1\
colorblue[x_k]f_2(x_1,ldots,x_n)&=[x_k]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&=[x_k]left(-sum_i=1^n(n-2i+1)x_iright)\
&,,colorblue=2k-n-1\
colorblue[x_k]f_3(x_1,ldots,x_n)&=[x_k]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_k]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&=-n[x_k]sum_i=1^nleft(2x_icdotfracn-2i+12nright)\
&qquadqquadqquad-n[x_k]sum_i=1^nleft(-2cdotfrac1nsum_j=1^nx_jcdotfracn-2i+12nright)\
&=-[x_k]sum_i=1^nx_i(n-2i+1)+[x_k]sum_i=1^nfrac1nsum_j=1^nx_j(n-2i+1)\
&=-(n-2k+1)+sum_i=1^nfrac1n(n-2i+1)\
&=-(n-2k+1)+(n+1-n-1)\
&,,colorblue=2k-n-1
endalign*
and finally the constant term .
We obtain
beginalign*
colorblue[x_0]f_1(x_1,ldots,x_n)&=[x_0]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&,,colorblue=0\
colorblue[x_0]f_2(x_1,ldots,x_n)&=[x_0]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&,,colorblue=0\
colorblue[x_0]f_3(x_1,ldots,x_n)&=[x_0]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_0]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&qquadqquadqquad+frac14nsum_i=1^n(n-2i+1)^2\
&=-n[x_0]sum_i=1^nleft(fracn-2i+12nright)^2+frac14nsum_i=1^n(n-2i+1)^2\
&,,colorblue=0
endalign*
We observe the coefficients of terms with equal powers are equal.
Conclusion:
We obtain by collecting the results from above
beginalign*
colorbluef_1(x_1,ldots,x_n)&colorblue=f_2(x_1,ldots,x_n)=f_3(x_1,ldots,x_n)\
&,,colorblue=(1-n)sum_i=1^nx_i^2+2sum_1leq i<jleq nx_ix_j+sum_i=1^n(2i-n-1)x_i
endalign*
answered Mar 25 at 14:48
Markus ScheuerMarkus Scheuer
63.5k460151
$endgroup$
add a comment |
$begingroup$
$defpeqmathrelphantom=$For the first identity, because$$
sum_i < j (x_j - x_i) = sum_k = 1^n x_k left( sum_l < k 1 + sum_l > k (-1) right) = sum_k = 1^n (2k - n - 1) x_k,
$$begingather*
sum_i < j (x_j - x_i)^2 = sum_k = 1^n x_k^2 left( sum_l < k 1 + sum_l > k 1 right) - 2 sum_i < j x_i x_j\
= (n - 1) sum_k = 1^n x_k^2 - left( left( sum_k = 1^n x_k right)^2 - sum_k = 1^n x_k^2 right) = n sum_k = 1^n x_k^2 - left( sum_k = 1^n x_k right)^2,
endgather*
then$$
sum_i < j ((x_j - x_i) - (x_j - x_i)^2) = left( sum_k = 1^n x_k right)^2 - n sum_k = 1^n x_k^2 - sum_k = 1^n (n - 2k + 1) x_k.
$$
For the second identity, denoting $barx = dfrac1n sumlimits_k = 1^n x_k$,beginalign*
&peq -n sum_k = 1^n left( x_k - barx + frac12n (n - 2k + 1) right)^2 + frac14n sum_k = 1^n (n - 2k + 1)^2\
&= -sum_k = 1^n left( n(x_k - barx)^2 + (n - 2k + 1)(x_k - barx) + frac14n (n - 2k + 1)^2 right) + frac14n sum_k = 1^n (n - 2k + 1)^2\
&= -sum_k = 1^n left( n(x_k - barx)^2 + (n - 2k + 1)(x_k - barx) right)\
&= -n sum_k = 1^n (x_k - barx)^2 - sum_k = 1^n (n - 2k + 1) x_k + barx sum_k = 1^n (n - 2k + 1)\
&= -n left( sum_k = 1^n x_k^2 - nbarx^2 right) - sum_k = 1^n (n - 2k + 1) x_k + 0\
&= left( sum_k = 1^n x_k right)^2 - n sum_k = 1^n x_k^2 - sum_k = 1^n (n - 2k + 1) x_k.
endalign*
answered Mar 25 at 2:33
SaadSaad
20.3k92352
$endgroup$
$begingroup$
Nice. A lot easier than mine.
$endgroup$
– marty cohen
Mar 27 at 6:53
add a comment |
$begingroup$
An alternative to @martycohen's approach, using derivatives. I think that if I didn't have to write out details about the Kronecker delta, this might be shorter than Marty's, but I can't promist that.
Both sides are evidently quadratics in the $x_i$ variables, with no constant terms. That is to say, they have the form
$$
H = (sum_ij c_ij x_i x_j ) + sum_i e_i x_i
$$
If we differentiate such a thing with respect to $x_k$, we get
$$
fracpartial Hpartial x_k = (sum_i c_ik x_i + sum_j c_kj x_j) + e_k,
$$
and if we set all the $x_i$ to zero, we get just $e_k$. Similarly, if we differentiate twice, we can find $c_kp$. By comparing these for the two sides, we'll see the two quadratics are equal.
The derivative of $x_i$ with respect to $x_k$ is $delta_ik = begincases 1 & i = k\ 0 & i ne k endcases$, and $sum_i x_i delta_ik = x_k$, which we'll use frequently in various forms. Also note that
$$
tagsum-j
sum_i =1^n sum_j = i+1^n delta_jk = k-1,
$$
because the inner sum is either $0$ or $1$; it's $1$ whenever $k > i$. This occurs, in the outer sum, for $i = 1, 2, ldots, k-1$, i.e., $k-1$ times. Similarly,
$$
tagsum-i
sum_i =1^n sum_j = i+1^n delta_ik = n-k.
$$
Finally,
$$
tagsum-pk
sum_i =1^n sum_j = i+1^n delta_ikdelta_jp =
sum_j = k+1^n delta_jp
= delta_k < p,
$$
by which I mean the sum is $1$ if $k < p$, and $0$ otherwise.
Returning to the main equation, and calling the left and right-hand expressions $L$ and $R$, we'll check first to see that the linear-term coefficient of $x_k$ is identical in both.
The derivative of the LHS with respect to $x_k$ is
beginalign
fracpartial Lpartial x_k &= sum_i=1^n sum_j = i+1^n fracpartial left((x_j-x_i)-(x_j-x_i)^2right) partial x_k\
& = sum_i=1^n sum_j = i+1^n left((delta_jk-delta_ik)-2(x_j-x_i)(delta_jk-delta_ik)right)
endalign
Evaluated when all the $x_i$ are zero, we get
beginalign
fracpartial Lpartial x_k(0,0,ldots, 0)
& = sum_i=1^n sum_j = i+1^n (delta_jk-delta_ik)\
& = sum_i=1^n sum_j = i+1^n delta_jk-sum_i=1^n sum_j = i+1^ndelta_ik\
& = (k-1) - (n-k) & textby sum-i and sum-j above \
&= -n + 2k - 1.
endalign
The derivative of the right-hand side is
beginalign
fracpartial Rpartial x_k
&= fracpartial biggl[ big(sum_i=1^nx_ibig)^2-nsum_i=1^nx_i^2 - sum_i=1^n(n-2i+1)x_ibiggr]partial x_k\
&= 2big(sum_i=1^nx_ibig) sum_i=1^n delta_ik -n fracpartial sum_i=1^nx_i^2partial x_k - fracpartial sum_i=1^n(n-2i+1)x_ipartial x_k \
&= 2big(sum_i=1^nx_ibig)
-n biggl[ sum_i=1^n2x_i delta_ik biggr]
- sum_i=1^n (n-2i+1)delta_ik \
&= 2big(sum_i=1^nx_ibig)
-2n x_k
- (n-2k+1) \
endalign
When $x_1 = x_2 = ldots = x_n = 0$, we again get a value of $-(n-2k + 1) = -n + 2k - 1$. So the linear terms on the two sides are equal.
Now let's look at the second derivatives. We have
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = sum_i=1^n sum_j = i+1^n left(-2(delta_jp-delta_ip)(delta_jk-delta_ik)right)\
& = -2 sum_i=1^n sum_j = i+1^n
delta_jpdelta_jk - delta_jpdelta_ik-delta_ipdelta_jk + delta_ipdelta_ik
endalign
First consider the case $k = p$:
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = -2 sum_i=1^n sum_j = i+1^n
delta_jkdelta_jk - delta_jkdelta_ik-delta_ikdelta_jk + delta_ikdelta_ik\
& = -2 sum_i=1^n sum_j = i+1^n
delta_jk - 2delta_jkdelta_ik + delta_ik\
& = -2biggl[ (k-1) + (n-k) - 2sum_i=1^n sum_j = i+1^n
delta_jkdelta_ik biggr] & textby sum-i and sum-j\
endalign
The remaining product $delta_jkdelta_ik$ is $1$ only if $i$ and $j$ are equal, but since $j$ starts at $i+1$, this never happens. Hence
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = 2 - 2n
endalign
in the case where $k = p$.
Now look at $k ne p$. We have
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = -2 sum_i=1^n sum_j = i+1^n delta_jpdelta_jk +
2 sum_i=1^n sum_j = i+1^n delta_jpdelta_ik +
2 sum_i=1^n sum_j = i+1^n delta_ipdelta_jk - 2 sum_i=1^n sum_j = i+1^n delta_ipdelta_ik
endalign
By sum-kp, the two middle terms are $delta_k < p$ and $delta_p<k$, so exactly one of them is $1$, and we can replace their sum with a $1$ (which gets multiplied by the $2$ in front!). So we have
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = 2
-2 sum_i=1^n sum_j = i+1^ndelta_jpdelta_jk - 2 sum_i=1^n sum_j = i+1^n delta_ipdelta_ik \
endalign
Furthermore, because $k$ and $p$ are distinct, $j$ cannot equal both of them, so the first sun is zero; similarly for the second. We end up with
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = 2
endalign
On the right-hand side, we have
beginalign
fracpartial Rpartial x_k
&= 2big(sum_i=1^nx_ibig)
-2n x_k
- (n-2k+1) \
endalign
we get
beginalign
fracpartial^2 Rpartial x_k partial x_p
&= 2big(sum_i=1^n
delta_ipbig)
-2n delta_kp \
&= 2 -2n delta_kp \
endalign
which agrees exactly with the result for the left-hand side. We're done!
answered Mar 22 at 21:42
John HughesJohn Hughes
65.1k24292
$endgroup$
add a comment |
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3155506%2fhow-to-prove-this-identity-nicely%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Taking a low tech approach, let our original summation be
$ s_n := u_n - t_n $ where
$$ u_n := sum_1le i<jle n (x_j-x_i), quad
t_n := sum_1le i<jle n (x_j-x_i)^2. tag1$$
Also, let
$$ v_n := sum_1le ine jle n x_i x_j =
left(sum_1le kle n x_k right)^2 - sum_1le kle nx_k^2. tag2$$
Now, $;u_n = sum_ile kle n c_k,n x_k $ where
$$ c_k,n := (sum_1le ile k 1) - (sum_kle jle n 1) = k-(n-k+1) = 2k-n-1 tag3$$
which counts how many times $ k $ appears as $ j $
minus the times it appears as $ i $ in equation $(1).$
Thus, $$ u_n = sum_1le kle n (2k-n-1) x_k =
-sum_1le kle n (n-2k+1) x_k . tag4$$
Now, we get $ t_n = sum_1le i<jle n (x_j^2 + x_i^2 - 2x_jx_i) $ by expanding the square in equation $(1)$ and
similarly to how we got equation $(3)$, we now get
$$ t_n !=! sum_k=1^n (k!+!(n!-!k!+!1)) x_k^2 +! sum_1le ine jle n x_ix_j !=! (n!+!1)!sum_k=1^n x_k^2!+! v_n. tag5$$
Combining this with equation $(2)$ we get
$$ t_n = nsum_1le kle n x_k^2 - sum_1le kle nx_k^2. tag6$$ Combining this with equation $(4)$ we get
$$ s_n = left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1) x_i, tag7$$
which is the first identity requested.
Continuing, let $ y_i = y_i,n := x_i -frac1nsum_j=1^n x_j. $ There is a famous formula in statistics
$$ t_n = n sum_1le ile n Big(x_i-frac1nsum_j=1^n x_jBig)^2 = n sum_1le ile n y_i^2. tag8$$
Notice that $$ sum_i=1^n (n-2i+1) = 0. tag9$$
Combining this with equation $(4)$ we get
$$ u_n = -sum_1le ile n (n-2i+1) y_i. tag10$$
Combining this with equation $(8)$ we get
$$ s_n = -n sum_i=1^n y_i^2 -sum_1le ile n (n-2i+1) y_i. tag11$$
Continuing, let $ z_i = z_i,n := y_i,n +fracn-2i+12n. $
Now
$$ z_i^2 = y_i^2 + y_ifracn-2i+1n + frac(n-2i+1)^24n^2. tag12$$
Summing this over $ i $ and multipling by $ n $ gives us
$$ n sum_i=1^n z_i^2 !=!
n sum_i=1^n y_i^2 + sum_i=1^n y_i(n!-!2i!+!1)
!+!
frac14nsum_i=1^n (n!-!2i!+!1)^2. tag13$$
Finally, combining equations $(11)$ and $(13)$ we get
$$ s_n = - n sum_i=1^n z_i^2 +
frac14nsum_i=1^n (n-2i+1)^2. tag14$$
which is the second identity since
$ z_i = x_i -frac1nsum_j=1^n x_j +fracn-2i+12n.$
P.S.
The identities and proofs are simplified if we use a
non-standard indexing for the $ x_i. $ So suppose we have an indexed set of $ n $ numbers
$ x_-n+1, x_-n+3, dots, x_n-3, x_n-1. $
For $ n=0 $ we have just $x_0. $ For $ n=1 $ we have the
set $ x_-1, x_1 $ and so on. It is understood that we will
sum from $ -n+1 $ to $ n-1 $ in steps of $2$. So define our new
$$ u_n :=! sum_-n+1le i<jle n-1 (x_j!-!x_i), ;
t_n := !sum_-n+1le i<jle n-1 (x_j!-!x_i)^2. tag15$$
The first identity is now
$$ s_n = u_n - t_n = Big(sum_i i x_iBig) +
Big(sum_i x_iBig)^2 - nBig(sum_i x_i^2Big).
tag16$$
The second identity is now
$$ s_n = -n sum_i Big(x_i-frac1nsum_j x_j-fraci2nBig)^2 + fracn^2-112.
tag17$$
answered Mar 28 at 1:14
SomosSomos
14.7k11337
$endgroup$
add a comment |
$begingroup$
Taking a low tech approach, let our original summation be
$ s_n := u_n - t_n $ where
$$ u_n := sum_1le i<jle n (x_j-x_i), quad
t_n := sum_1le i<jle n (x_j-x_i)^2. tag1$$
Also, let
$$ v_n := sum_1le ine jle n x_i x_j =
left(sum_1le kle n x_k right)^2 - sum_1le kle nx_k^2. tag2$$
Now, $;u_n = sum_ile kle n c_k,n x_k $ where
$$ c_k,n := (sum_1le ile k 1) - (sum_kle jle n 1) = k-(n-k+1) = 2k-n-1 tag3$$
which counts how many times $ k $ appears as $ j $
minus the times it appears as $ i $ in equation $(1).$
Thus, $$ u_n = sum_1le kle n (2k-n-1) x_k =
-sum_1le kle n (n-2k+1) x_k . tag4$$
Now, we get $ t_n = sum_1le i<jle n (x_j^2 + x_i^2 - 2x_jx_i) $ by expanding the square in equation $(1)$ and
similarly to how we got equation $(3)$, we now get
$$ t_n !=! sum_k=1^n (k!+!(n!-!k!+!1)) x_k^2 +! sum_1le ine jle n x_ix_j !=! (n!+!1)!sum_k=1^n x_k^2!+! v_n. tag5$$
Combining this with equation $(2)$ we get
$$ t_n = nsum_1le kle n x_k^2 - sum_1le kle nx_k^2. tag6$$ Combining this with equation $(4)$ we get
$$ s_n = left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1) x_i, tag7$$
which is the first identity requested.
Continuing, let $ y_i = y_i,n := x_i -frac1nsum_j=1^n x_j. $ There is a famous formula in statistics
$$ t_n = n sum_1le ile n Big(x_i-frac1nsum_j=1^n x_jBig)^2 = n sum_1le ile n y_i^2. tag8$$
Notice that $$ sum_i=1^n (n-2i+1) = 0. tag9$$
Combining this with equation $(4)$ we get
$$ u_n = -sum_1le ile n (n-2i+1) y_i. tag10$$
Combining this with equation $(8)$ we get
$$ s_n = -n sum_i=1^n y_i^2 -sum_1le ile n (n-2i+1) y_i. tag11$$
Continuing, let $ z_i = z_i,n := y_i,n +fracn-2i+12n. $
Now
$$ z_i^2 = y_i^2 + y_ifracn-2i+1n + frac(n-2i+1)^24n^2. tag12$$
Summing this over $ i $ and multipling by $ n $ gives us
$$ n sum_i=1^n z_i^2 !=!
n sum_i=1^n y_i^2 + sum_i=1^n y_i(n!-!2i!+!1)
!+!
frac14nsum_i=1^n (n!-!2i!+!1)^2. tag13$$
Finally, combining equations $(11)$ and $(13)$ we get
$$ s_n = - n sum_i=1^n z_i^2 +
frac14nsum_i=1^n (n-2i+1)^2. tag14$$
which is the second identity since
$ z_i = x_i -frac1nsum_j=1^n x_j +fracn-2i+12n.$
P.S.
The identities and proofs are simplified if we use a
non-standard indexing for the $ x_i. $ So suppose we have an indexed set of $ n $ numbers
$ x_-n+1, x_-n+3, dots, x_n-3, x_n-1. $
For $ n=0 $ we have just $x_0. $ For $ n=1 $ we have the
set $ x_-1, x_1 $ and so on. It is understood that we will
sum from $ -n+1 $ to $ n-1 $ in steps of $2$. So define our new
$$ u_n :=! sum_-n+1le i<jle n-1 (x_j!-!x_i), ;
t_n := !sum_-n+1le i<jle n-1 (x_j!-!x_i)^2. tag15$$
The first identity is now
$$ s_n = u_n - t_n = Big(sum_i i x_iBig) +
Big(sum_i x_iBig)^2 - nBig(sum_i x_i^2Big).
tag16$$
The second identity is now
$$ s_n = -n sum_i Big(x_i-frac1nsum_j x_j-fraci2nBig)^2 + fracn^2-112.
tag17$$
answered Mar 28 at 1:14
SomosSomos
14.7k11337
$endgroup$
add a comment |
$begingroup$
Taking a low tech approach, let our original summation be
$ s_n := u_n - t_n $ where
$$ u_n := sum_1le i<jle n (x_j-x_i), quad
t_n := sum_1le i<jle n (x_j-x_i)^2. tag1$$
Also, let
$$ v_n := sum_1le ine jle n x_i x_j =
left(sum_1le kle n x_k right)^2 - sum_1le kle nx_k^2. tag2$$
Now, $;u_n = sum_ile kle n c_k,n x_k $ where
$$ c_k,n := (sum_1le ile k 1) - (sum_kle jle n 1) = k-(n-k+1) = 2k-n-1 tag3$$
which counts how many times $ k $ appears as $ j $
minus the times it appears as $ i $ in equation $(1).$
Thus, $$ u_n = sum_1le kle n (2k-n-1) x_k =
-sum_1le kle n (n-2k+1) x_k . tag4$$
Now, we get $ t_n = sum_1le i<jle n (x_j^2 + x_i^2 - 2x_jx_i) $ by expanding the square in equation $(1)$ and
similarly to how we got equation $(3)$, we now get
$$ t_n !=! sum_k=1^n (k!+!(n!-!k!+!1)) x_k^2 +! sum_1le ine jle n x_ix_j !=! (n!+!1)!sum_k=1^n x_k^2!+! v_n. tag5$$
Combining this with equation $(2)$ we get
$$ t_n = nsum_1le kle n x_k^2 - sum_1le kle nx_k^2. tag6$$ Combining this with equation $(4)$ we get
$$ s_n = left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1) x_i, tag7$$
which is the first identity requested.
Continuing, let $ y_i = y_i,n := x_i -frac1nsum_j=1^n x_j. $ There is a famous formula in statistics
$$ t_n = n sum_1le ile n Big(x_i-frac1nsum_j=1^n x_jBig)^2 = n sum_1le ile n y_i^2. tag8$$
Notice that $$ sum_i=1^n (n-2i+1) = 0. tag9$$
Combining this with equation $(4)$ we get
$$ u_n = -sum_1le ile n (n-2i+1) y_i. tag10$$
Combining this with equation $(8)$ we get
$$ s_n = -n sum_i=1^n y_i^2 -sum_1le ile n (n-2i+1) y_i. tag11$$
Continuing, let $ z_i = z_i,n := y_i,n +fracn-2i+12n. $
Now
$$ z_i^2 = y_i^2 + y_ifracn-2i+1n + frac(n-2i+1)^24n^2. tag12$$
Summing this over $ i $ and multipling by $ n $ gives us
$$ n sum_i=1^n z_i^2 !=!
n sum_i=1^n y_i^2 + sum_i=1^n y_i(n!-!2i!+!1)
!+!
frac14nsum_i=1^n (n!-!2i!+!1)^2. tag13$$
Finally, combining equations $(11)$ and $(13)$ we get
$$ s_n = - n sum_i=1^n z_i^2 +
frac14nsum_i=1^n (n-2i+1)^2. tag14$$
which is the second identity since
$ z_i = x_i -frac1nsum_j=1^n x_j +fracn-2i+12n.$
P.S.
The identities and proofs are simplified if we use a
non-standard indexing for the $ x_i. $ So suppose we have an indexed set of $ n $ numbers
$ x_-n+1, x_-n+3, dots, x_n-3, x_n-1. $
For $ n=0 $ we have just $x_0. $ For $ n=1 $ we have the
set $ x_-1, x_1 $ and so on. It is understood that we will
sum from $ -n+1 $ to $ n-1 $ in steps of $2$. So define our new
$$ u_n :=! sum_-n+1le i<jle n-1 (x_j!-!x_i), ;
t_n := !sum_-n+1le i<jle n-1 (x_j!-!x_i)^2. tag15$$
The first identity is now
$$ s_n = u_n - t_n = Big(sum_i i x_iBig) +
Big(sum_i x_iBig)^2 - nBig(sum_i x_i^2Big).
tag16$$
The second identity is now
$$ s_n = -n sum_i Big(x_i-frac1nsum_j x_j-fraci2nBig)^2 + fracn^2-112.
tag17$$
answered Mar 28 at 1:14
SomosSomos
14.7k11337
$endgroup$
Taking a low tech approach, let our original summation be
$ s_n := u_n - t_n $ where
$$ u_n := sum_1le i<jle n (x_j-x_i), quad
t_n := sum_1le i<jle n (x_j-x_i)^2. tag1$$
Also, let
$$ v_n := sum_1le ine jle n x_i x_j =
left(sum_1le kle n x_k right)^2 - sum_1le kle nx_k^2. tag2$$
Now, $;u_n = sum_ile kle n c_k,n x_k $ where
$$ c_k,n := (sum_1le ile k 1) - (sum_kle jle n 1) = k-(n-k+1) = 2k-n-1 tag3$$
which counts how many times $ k $ appears as $ j $
minus the times it appears as $ i $ in equation $(1).$
Thus, $$ u_n = sum_1le kle n (2k-n-1) x_k =
-sum_1le kle n (n-2k+1) x_k . tag4$$
Now, we get $ t_n = sum_1le i<jle n (x_j^2 + x_i^2 - 2x_jx_i) $ by expanding the square in equation $(1)$ and
similarly to how we got equation $(3)$, we now get
$$ t_n !=! sum_k=1^n (k!+!(n!-!k!+!1)) x_k^2 +! sum_1le ine jle n x_ix_j !=! (n!+!1)!sum_k=1^n x_k^2!+! v_n. tag5$$
Combining this with equation $(2)$ we get
$$ t_n = nsum_1le kle n x_k^2 - sum_1le kle nx_k^2. tag6$$ Combining this with equation $(4)$ we get
$$ s_n = left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1) x_i, tag7$$
which is the first identity requested.
Continuing, let $ y_i = y_i,n := x_i -frac1nsum_j=1^n x_j. $ There is a famous formula in statistics
$$ t_n = n sum_1le ile n Big(x_i-frac1nsum_j=1^n x_jBig)^2 = n sum_1le ile n y_i^2. tag8$$
Notice that $$ sum_i=1^n (n-2i+1) = 0. tag9$$
Combining this with equation $(4)$ we get
$$ u_n = -sum_1le ile n (n-2i+1) y_i. tag10$$
Combining this with equation $(8)$ we get
$$ s_n = -n sum_i=1^n y_i^2 -sum_1le ile n (n-2i+1) y_i. tag11$$
Continuing, let $ z_i = z_i,n := y_i,n +fracn-2i+12n. $
Now
$$ z_i^2 = y_i^2 + y_ifracn-2i+1n + frac(n-2i+1)^24n^2. tag12$$
Summing this over $ i $ and multipling by $ n $ gives us
$$ n sum_i=1^n z_i^2 !=!
n sum_i=1^n y_i^2 + sum_i=1^n y_i(n!-!2i!+!1)
!+!
frac14nsum_i=1^n (n!-!2i!+!1)^2. tag13$$
Finally, combining equations $(11)$ and $(13)$ we get
$$ s_n = - n sum_i=1^n z_i^2 +
frac14nsum_i=1^n (n-2i+1)^2. tag14$$
which is the second identity since
$ z_i = x_i -frac1nsum_j=1^n x_j +fracn-2i+12n.$
P.S.
The identities and proofs are simplified if we use a
non-standard indexing for the $ x_i. $ So suppose we have an indexed set of $ n $ numbers
$ x_-n+1, x_-n+3, dots, x_n-3, x_n-1. $
For $ n=0 $ we have just $x_0. $ For $ n=1 $ we have the
set $ x_-1, x_1 $ and so on. It is understood that we will
sum from $ -n+1 $ to $ n-1 $ in steps of $2$. So define our new
$$ u_n :=! sum_-n+1le i<jle n-1 (x_j!-!x_i), ;
t_n := !sum_-n+1le i<jle n-1 (x_j!-!x_i)^2. tag15$$
The first identity is now
$$ s_n = u_n - t_n = Big(sum_i i x_iBig) +
Big(sum_i x_iBig)^2 - nBig(sum_i x_i^2Big).
tag16$$
The second identity is now
$$ s_n = -n sum_i Big(x_i-frac1nsum_j x_j-fraci2nBig)^2 + fracn^2-112.
tag17$$
answered Mar 28 at 1:14
SomosSomos
14.7k11337
edited Mar 28 at 2:24
answered Mar 28 at 1:14
SomosSomos
14.7k11337
answered Mar 28 at 1:14
SomosSomos
14.7k11337
answered Mar 28 at 1:14
SomosSomos
14.7k11337
14.7k11337
add a comment |
add a comment |
$begingroup$
This was a pain,
but here it is.
$beginarray\
s(n)
&=sum_1le i<jle nleft((x_j-x_i)-(x_j-x_i)^2right)\
&=sum_i=1^n sum_j=i+1^n((x_j-x_i)-(x_j-x_i)^2)\
&=sum_i=1^n sum_j=i+1^n(x_j-x_i)-sum_i=1^n sum_j=i+1^n(x_j-x_i)^2\
&=s_1(n)-s_2(n)\
s_1(n)
&=sum_i=1^n sum_j=i+1^n(x_j-x_i)\
&=sum_i=1^n sum_j=i^n(x_j-x_i)\
&=sum_i=1^n sum_j=i^nx_j-sum_i=1^n sum_j=i^nx_i\
&=sum_j=1^n sum_i=1^jx_j-sum_i=1^n (n-i+1)x_i\
&=sum_j=1^n x_jsum_i=1^j1-sum_i=1^n (n-i+1)x_i\
&=sum_j=1^n jx_j-sum_i=1^n (n-i+1)x_i\
&=sum_i=1^n ix_i-sum_i=1^n (n-i+1)x_i\
&=sum_i=1^n (i-n+i-1)x_i\
&=sum_i=1^n (2i-n-1)x_i\
s_2(n)
&=sum_i=1^n sum_j=i+1^n(x_j-x_i)^2\
&=sum_i=1^n sum_j=i^n(x_j-x_i)^2\
&=sum_i=1^n sum_j=i^n(x_j^2-2x_jx_i+x_i^2)\
&=sum_i=1^n sum_j=i^nx_j^2-2sum_i=1^n sum_j=i^nx_jx_i+sum_i=1^n sum_j=i^nx_i^2\
&=s_3(n)-2s_4(n)+s_5(n)\
s_3(n)
&=sum_i=1^n sum_j=i^nx_j^2\
&=sum_j=1^n sum_i=1^jx_j^2\
&=sum_j=1^n jx_j^2\
s_4(n)
&=sum_i=1^n sum_j=i^nx_jx_i\
&=sum_i=1^n x_isum_j=i^nx_j\
&=sum_i=1^n x_i(sum_j=1^nx_j-sum_j=1^i-1x_j)\
&=sum_i=1^n x_isum_j=1^nx_j-sum_i=1^n sum_j=1^i-1x_ix_j\
&=(sum_i=1^n x_i)^2-sum_j=1^n-1 sum_i=j+1^nx_ix_j\
&=(sum_i=1^n x_i)^2-sum_j=1^n-1 x_jsum_i=j+1^nx_i\
&=(sum_i=1^n x_i)^2-sum_j=1^n x_jsum_i=j+1^nx_i\
&=(sum_i=1^n x_i)^2-sum_j=1^n x_j(sum_i=j^nx_i-x_j)\
&=(sum_i=1^n x_i)^2-sum_j=1^n x_jsum_i=j^nx_i+sum_j=1^n x_j^2\
&=(sum_i=1^n x_i)^2-sum_i=1^n x_isum_j=i^nx_j+sum_j=1^n x_j^2\
&=(sum_i=1^n x_i)^2-s_4(n)+sum_j=1^n x_j^2\
textso\
s_4(n)
&=frac12((sum_i=1^n x_i)^2+sum_i=1^n x_i^2)\
s_5(n)
&=sum_i=1^n sum_j=i^nx_i^2\
&=sum_i=1^n (n-i+1)x_i^2\
textso\
s_2(n)
&=s_3(n)-2s_4(n)+s_5(n)\
&=sum_j=1^n jx_j^2-((sum_i=1^n x_i)^2+sum_i=1^n x_i^2)+sum_i=1^n (n-i+1)x_i^2\
&=-((sum_i=1^n x_i)^2+sum_i=1^n x_i^2)+sum_i=1^n (n+1)x_i^2\
&=-(sum_i=1^n x_i)^2+nsum_i=1^n x_i^2\
textso\
s(n)
&=s_1(n)-s_2(n)\
&=sum_i=1^n (2i-n-1)x_i-(nsum_i=1^n x_i^2-(sum_i=1^n x_i)^2)\
&=(sum_i=1^n x_i)^2-nsum_i=1^n x_i^2+sum_i=1^n (2i-n-1)x_i\
endarray
$
Whew!
answered Mar 21 at 3:52
marty cohenmarty cohen
74.9k549130
$endgroup$
$begingroup$
Nice! can you post the second $=?$
$endgroup$
– function sug
Mar 21 at 8:22
$begingroup$
Sorry. I'm all burnt out on this.
$endgroup$
– marty cohen
Mar 21 at 9:47
add a comment |
$begingroup$
This was a pain,
but here it is.
$beginarray\
s(n)
&=sum_1le i<jle nleft((x_j-x_i)-(x_j-x_i)^2right)\
&=sum_i=1^n sum_j=i+1^n((x_j-x_i)-(x_j-x_i)^2)\
&=sum_i=1^n sum_j=i+1^n(x_j-x_i)-sum_i=1^n sum_j=i+1^n(x_j-x_i)^2\
&=s_1(n)-s_2(n)\
s_1(n)
&=sum_i=1^n sum_j=i+1^n(x_j-x_i)\
&=sum_i=1^n sum_j=i^n(x_j-x_i)\
&=sum_i=1^n sum_j=i^nx_j-sum_i=1^n sum_j=i^nx_i\
&=sum_j=1^n sum_i=1^jx_j-sum_i=1^n (n-i+1)x_i\
&=sum_j=1^n x_jsum_i=1^j1-sum_i=1^n (n-i+1)x_i\
&=sum_j=1^n jx_j-sum_i=1^n (n-i+1)x_i\
&=sum_i=1^n ix_i-sum_i=1^n (n-i+1)x_i\
&=sum_i=1^n (i-n+i-1)x_i\
&=sum_i=1^n (2i-n-1)x_i\
s_2(n)
&=sum_i=1^n sum_j=i+1^n(x_j-x_i)^2\
&=sum_i=1^n sum_j=i^n(x_j-x_i)^2\
&=sum_i=1^n sum_j=i^n(x_j^2-2x_jx_i+x_i^2)\
&=sum_i=1^n sum_j=i^nx_j^2-2sum_i=1^n sum_j=i^nx_jx_i+sum_i=1^n sum_j=i^nx_i^2\
&=s_3(n)-2s_4(n)+s_5(n)\
s_3(n)
&=sum_i=1^n sum_j=i^nx_j^2\
&=sum_j=1^n sum_i=1^jx_j^2\
&=sum_j=1^n jx_j^2\
s_4(n)
&=sum_i=1^n sum_j=i^nx_jx_i\
&=sum_i=1^n x_isum_j=i^nx_j\
&=sum_i=1^n x_i(sum_j=1^nx_j-sum_j=1^i-1x_j)\
&=sum_i=1^n x_isum_j=1^nx_j-sum_i=1^n sum_j=1^i-1x_ix_j\
&=(sum_i=1^n x_i)^2-sum_j=1^n-1 sum_i=j+1^nx_ix_j\
&=(sum_i=1^n x_i)^2-sum_j=1^n-1 x_jsum_i=j+1^nx_i\
&=(sum_i=1^n x_i)^2-sum_j=1^n x_jsum_i=j+1^nx_i\
&=(sum_i=1^n x_i)^2-sum_j=1^n x_j(sum_i=j^nx_i-x_j)\
&=(sum_i=1^n x_i)^2-sum_j=1^n x_jsum_i=j^nx_i+sum_j=1^n x_j^2\
&=(sum_i=1^n x_i)^2-sum_i=1^n x_isum_j=i^nx_j+sum_j=1^n x_j^2\
&=(sum_i=1^n x_i)^2-s_4(n)+sum_j=1^n x_j^2\
textso\
s_4(n)
&=frac12((sum_i=1^n x_i)^2+sum_i=1^n x_i^2)\
s_5(n)
&=sum_i=1^n sum_j=i^nx_i^2\
&=sum_i=1^n (n-i+1)x_i^2\
textso\
s_2(n)
&=s_3(n)-2s_4(n)+s_5(n)\
&=sum_j=1^n jx_j^2-((sum_i=1^n x_i)^2+sum_i=1^n x_i^2)+sum_i=1^n (n-i+1)x_i^2\
&=-((sum_i=1^n x_i)^2+sum_i=1^n x_i^2)+sum_i=1^n (n+1)x_i^2\
&=-(sum_i=1^n x_i)^2+nsum_i=1^n x_i^2\
textso\
s(n)
&=s_1(n)-s_2(n)\
&=sum_i=1^n (2i-n-1)x_i-(nsum_i=1^n x_i^2-(sum_i=1^n x_i)^2)\
&=(sum_i=1^n x_i)^2-nsum_i=1^n x_i^2+sum_i=1^n (2i-n-1)x_i\
endarray
$
Whew!
answered Mar 21 at 3:52
marty cohenmarty cohen
74.9k549130
$endgroup$
$begingroup$
Nice! can you post the second $=?$
$endgroup$
– function sug
Mar 21 at 8:22
$begingroup$
Sorry. I'm all burnt out on this.
$endgroup$
– marty cohen
Mar 21 at 9:47
add a comment |
$begingroup$
This was a pain,
but here it is.
$beginarray\
s(n)
&=sum_1le i<jle nleft((x_j-x_i)-(x_j-x_i)^2right)\
&=sum_i=1^n sum_j=i+1^n((x_j-x_i)-(x_j-x_i)^2)\
&=sum_i=1^n sum_j=i+1^n(x_j-x_i)-sum_i=1^n sum_j=i+1^n(x_j-x_i)^2\
&=s_1(n)-s_2(n)\
s_1(n)
&=sum_i=1^n sum_j=i+1^n(x_j-x_i)\
&=sum_i=1^n sum_j=i^n(x_j-x_i)\
&=sum_i=1^n sum_j=i^nx_j-sum_i=1^n sum_j=i^nx_i\
&=sum_j=1^n sum_i=1^jx_j-sum_i=1^n (n-i+1)x_i\
&=sum_j=1^n x_jsum_i=1^j1-sum_i=1^n (n-i+1)x_i\
&=sum_j=1^n jx_j-sum_i=1^n (n-i+1)x_i\
&=sum_i=1^n ix_i-sum_i=1^n (n-i+1)x_i\
&=sum_i=1^n (i-n+i-1)x_i\
&=sum_i=1^n (2i-n-1)x_i\
s_2(n)
&=sum_i=1^n sum_j=i+1^n(x_j-x_i)^2\
&=sum_i=1^n sum_j=i^n(x_j-x_i)^2\
&=sum_i=1^n sum_j=i^n(x_j^2-2x_jx_i+x_i^2)\
&=sum_i=1^n sum_j=i^nx_j^2-2sum_i=1^n sum_j=i^nx_jx_i+sum_i=1^n sum_j=i^nx_i^2\
&=s_3(n)-2s_4(n)+s_5(n)\
s_3(n)
&=sum_i=1^n sum_j=i^nx_j^2\
&=sum_j=1^n sum_i=1^jx_j^2\
&=sum_j=1^n jx_j^2\
s_4(n)
&=sum_i=1^n sum_j=i^nx_jx_i\
&=sum_i=1^n x_isum_j=i^nx_j\
&=sum_i=1^n x_i(sum_j=1^nx_j-sum_j=1^i-1x_j)\
&=sum_i=1^n x_isum_j=1^nx_j-sum_i=1^n sum_j=1^i-1x_ix_j\
&=(sum_i=1^n x_i)^2-sum_j=1^n-1 sum_i=j+1^nx_ix_j\
&=(sum_i=1^n x_i)^2-sum_j=1^n-1 x_jsum_i=j+1^nx_i\
&=(sum_i=1^n x_i)^2-sum_j=1^n x_jsum_i=j+1^nx_i\
&=(sum_i=1^n x_i)^2-sum_j=1^n x_j(sum_i=j^nx_i-x_j)\
&=(sum_i=1^n x_i)^2-sum_j=1^n x_jsum_i=j^nx_i+sum_j=1^n x_j^2\
&=(sum_i=1^n x_i)^2-sum_i=1^n x_isum_j=i^nx_j+sum_j=1^n x_j^2\
&=(sum_i=1^n x_i)^2-s_4(n)+sum_j=1^n x_j^2\
textso\
s_4(n)
&=frac12((sum_i=1^n x_i)^2+sum_i=1^n x_i^2)\
s_5(n)
&=sum_i=1^n sum_j=i^nx_i^2\
&=sum_i=1^n (n-i+1)x_i^2\
textso\
s_2(n)
&=s_3(n)-2s_4(n)+s_5(n)\
&=sum_j=1^n jx_j^2-((sum_i=1^n x_i)^2+sum_i=1^n x_i^2)+sum_i=1^n (n-i+1)x_i^2\
&=-((sum_i=1^n x_i)^2+sum_i=1^n x_i^2)+sum_i=1^n (n+1)x_i^2\
&=-(sum_i=1^n x_i)^2+nsum_i=1^n x_i^2\
textso\
s(n)
&=s_1(n)-s_2(n)\
&=sum_i=1^n (2i-n-1)x_i-(nsum_i=1^n x_i^2-(sum_i=1^n x_i)^2)\
&=(sum_i=1^n x_i)^2-nsum_i=1^n x_i^2+sum_i=1^n (2i-n-1)x_i\
endarray
$
Whew!
answered Mar 21 at 3:52
marty cohenmarty cohen
74.9k549130
$endgroup$
This was a pain,
but here it is.
$beginarray\
s(n)
&=sum_1le i<jle nleft((x_j-x_i)-(x_j-x_i)^2right)\
&=sum_i=1^n sum_j=i+1^n((x_j-x_i)-(x_j-x_i)^2)\
&=sum_i=1^n sum_j=i+1^n(x_j-x_i)-sum_i=1^n sum_j=i+1^n(x_j-x_i)^2\
&=s_1(n)-s_2(n)\
s_1(n)
&=sum_i=1^n sum_j=i+1^n(x_j-x_i)\
&=sum_i=1^n sum_j=i^n(x_j-x_i)\
&=sum_i=1^n sum_j=i^nx_j-sum_i=1^n sum_j=i^nx_i\
&=sum_j=1^n sum_i=1^jx_j-sum_i=1^n (n-i+1)x_i\
&=sum_j=1^n x_jsum_i=1^j1-sum_i=1^n (n-i+1)x_i\
&=sum_j=1^n jx_j-sum_i=1^n (n-i+1)x_i\
&=sum_i=1^n ix_i-sum_i=1^n (n-i+1)x_i\
&=sum_i=1^n (i-n+i-1)x_i\
&=sum_i=1^n (2i-n-1)x_i\
s_2(n)
&=sum_i=1^n sum_j=i+1^n(x_j-x_i)^2\
&=sum_i=1^n sum_j=i^n(x_j-x_i)^2\
&=sum_i=1^n sum_j=i^n(x_j^2-2x_jx_i+x_i^2)\
&=sum_i=1^n sum_j=i^nx_j^2-2sum_i=1^n sum_j=i^nx_jx_i+sum_i=1^n sum_j=i^nx_i^2\
&=s_3(n)-2s_4(n)+s_5(n)\
s_3(n)
&=sum_i=1^n sum_j=i^nx_j^2\
&=sum_j=1^n sum_i=1^jx_j^2\
&=sum_j=1^n jx_j^2\
s_4(n)
&=sum_i=1^n sum_j=i^nx_jx_i\
&=sum_i=1^n x_isum_j=i^nx_j\
&=sum_i=1^n x_i(sum_j=1^nx_j-sum_j=1^i-1x_j)\
&=sum_i=1^n x_isum_j=1^nx_j-sum_i=1^n sum_j=1^i-1x_ix_j\
&=(sum_i=1^n x_i)^2-sum_j=1^n-1 sum_i=j+1^nx_ix_j\
&=(sum_i=1^n x_i)^2-sum_j=1^n-1 x_jsum_i=j+1^nx_i\
&=(sum_i=1^n x_i)^2-sum_j=1^n x_jsum_i=j+1^nx_i\
&=(sum_i=1^n x_i)^2-sum_j=1^n x_j(sum_i=j^nx_i-x_j)\
&=(sum_i=1^n x_i)^2-sum_j=1^n x_jsum_i=j^nx_i+sum_j=1^n x_j^2\
&=(sum_i=1^n x_i)^2-sum_i=1^n x_isum_j=i^nx_j+sum_j=1^n x_j^2\
&=(sum_i=1^n x_i)^2-s_4(n)+sum_j=1^n x_j^2\
textso\
s_4(n)
&=frac12((sum_i=1^n x_i)^2+sum_i=1^n x_i^2)\
s_5(n)
&=sum_i=1^n sum_j=i^nx_i^2\
&=sum_i=1^n (n-i+1)x_i^2\
textso\
s_2(n)
&=s_3(n)-2s_4(n)+s_5(n)\
&=sum_j=1^n jx_j^2-((sum_i=1^n x_i)^2+sum_i=1^n x_i^2)+sum_i=1^n (n-i+1)x_i^2\
&=-((sum_i=1^n x_i)^2+sum_i=1^n x_i^2)+sum_i=1^n (n+1)x_i^2\
&=-(sum_i=1^n x_i)^2+nsum_i=1^n x_i^2\
textso\
s(n)
&=s_1(n)-s_2(n)\
&=sum_i=1^n (2i-n-1)x_i-(nsum_i=1^n x_i^2-(sum_i=1^n x_i)^2)\
&=(sum_i=1^n x_i)^2-nsum_i=1^n x_i^2+sum_i=1^n (2i-n-1)x_i\
endarray
$
Whew!
answered Mar 21 at 3:52
marty cohenmarty cohen
74.9k549130
edited Mar 21 at 6:24
answered Mar 21 at 3:52
marty cohenmarty cohen
74.9k549130
answered Mar 21 at 3:52
marty cohenmarty cohen
74.9k549130
answered Mar 21 at 3:52
marty cohenmarty cohen
74.9k549130
74.9k549130
$begingroup$
Nice! can you post the second $=?$
$endgroup$
– function sug
Mar 21 at 8:22
$begingroup$
Sorry. I'm all burnt out on this.
$endgroup$
– marty cohen
Mar 21 at 9:47
add a comment |
$begingroup$
Nice! can you post the second $=?$
$endgroup$
– function sug
Mar 21 at 8:22
$begingroup$
Sorry. I'm all burnt out on this.
$endgroup$
– marty cohen
Mar 21 at 9:47
$begingroup$
Nice! can you post the second $=?$
$endgroup$
– function sug
Mar 21 at 8:22
$begingroup$
Nice! can you post the second $=?$
$endgroup$
– function sug
Mar 21 at 8:22
$begingroup$
Sorry. I'm all burnt out on this.
$endgroup$
– marty cohen
Mar 21 at 9:47
$begingroup$
Sorry. I'm all burnt out on this.
$endgroup$
– marty cohen
Mar 21 at 9:47
add a comment |
$begingroup$
We take an algebraic approach and consider the expressions as quadratic polynomials in $n$ variables $x_1,x_2,ldots,x_n$. We show equality by comparing the coefficients of corresponding terms.
It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.
We introduce $f_1,f_2,f_3$ as
beginalign*
f_1(x_1,ldots,x_n)&=sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
f_2(x_1,ldots,x_n)&=left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_i\
f_3(x_1,ldots,x_n)&=-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2+frac14nsum_i=1^n(n-2i+1)^2
endalign*
We start with the square terms.
We obtain for $1leq kleq n$:
beginalign*
colorblue[x_k^2]f_1(x_1,ldots,x_n)&=[x_k^2]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&=-[x_k^2]sum_1leq i<jleq nleft(x_j-x_iright)^2\
&=-[x_k^2]sum_1leq i<kleft(x_k-x_iright)^2-[x_k^2]sum_k<jleq nleft(x_j-x_kright)^2\
&=-(k-1)-(n-k)\
&,,colorblue=1-n\
colorblue[x_k^2]f_2(x_1,ldots,x_n)&=[x_k^2]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&=[x_k^2]sum_i=1^nx_i^2-n[x_k^2]sum_i=1^nx_i^2\
&,,colorblue=1-n\
colorblue[x_k^2]f_3(x_1,ldots,x_n)&=[x_k^2]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_k^2]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&=-n[x_k^2]sum_i=1^nleft(x_i^2-2x_icdotfrac1nsum_j=1^nx_j+left(frac1nsum_j=1^nx_jright)^2right)\
&=-n[x_k^2]sum_i=1^nx_i^2+2[x_k^2]sum_i=1^nx_isum_j=1^nx_j-frac1n[x_k^2]sum_i=1^nleft(sum_j=1^nx_jright)^2\
&=-n+2-1\
&,,colorblue=1-n
endalign*
Now we check the mixed quadratic terms.
We obtain for $1leq k<lleq n$:
beginalign*
colorblue[x_kx_l]f_1(x_1,ldots,x_n)&=[x_kx_l]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&=-[x_kx_l]sum_1leq i<jleq nleft(x_j-x_iright)^2\
&=2[x_kx_l]sum_1leq i<jleq nx_ix_j\
&,,colorblue=2\
colorblue[x_kx_l]f_2(x_1,ldots,x_n)&=[x_kx_l]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&=[x_kx_l]left(sum_i=1^nx_iright)^2\
&=[x_kx_l]left(sum_i=1^nx_i^2+2sum_1leq i<jleq nx_ix_jright)\
&,,colorblue=2\
colorblue[x_kx_l]f_3(x_1,ldots,x_n)&=[x_k^2]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_kx_l]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&=[x_kx_l]sum_i=1^nleft(2x_isum_j=1^nx_jright)\
&,,colorblue=2
endalign*
... the linear terms ...
We obtain for $ 1leq kleq n$:
beginalign*
colorblue[x_k]f_1(x_1,ldots,x_n)&=[x_k]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&=[x_k]sum_1leq i<jleq nleft(x_j-x_iright)\
&=[x_k]sum_1leq i<kleft(x_k-x_iright)+[x_k]sum_k<jleq nleft(x_j-x_kright)\
&=(k-1)-(n-k)\
&,,colorblue=2k-n-1\
colorblue[x_k]f_2(x_1,ldots,x_n)&=[x_k]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&=[x_k]left(-sum_i=1^n(n-2i+1)x_iright)\
&,,colorblue=2k-n-1\
colorblue[x_k]f_3(x_1,ldots,x_n)&=[x_k]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_k]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&=-n[x_k]sum_i=1^nleft(2x_icdotfracn-2i+12nright)\
&qquadqquadqquad-n[x_k]sum_i=1^nleft(-2cdotfrac1nsum_j=1^nx_jcdotfracn-2i+12nright)\
&=-[x_k]sum_i=1^nx_i(n-2i+1)+[x_k]sum_i=1^nfrac1nsum_j=1^nx_j(n-2i+1)\
&=-(n-2k+1)+sum_i=1^nfrac1n(n-2i+1)\
&=-(n-2k+1)+(n+1-n-1)\
&,,colorblue=2k-n-1
endalign*
and finally the constant term .
We obtain
beginalign*
colorblue[x_0]f_1(x_1,ldots,x_n)&=[x_0]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&,,colorblue=0\
colorblue[x_0]f_2(x_1,ldots,x_n)&=[x_0]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&,,colorblue=0\
colorblue[x_0]f_3(x_1,ldots,x_n)&=[x_0]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_0]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&qquadqquadqquad+frac14nsum_i=1^n(n-2i+1)^2\
&=-n[x_0]sum_i=1^nleft(fracn-2i+12nright)^2+frac14nsum_i=1^n(n-2i+1)^2\
&,,colorblue=0
endalign*
We observe the coefficients of terms with equal powers are equal.
Conclusion:
We obtain by collecting the results from above
beginalign*
colorbluef_1(x_1,ldots,x_n)&colorblue=f_2(x_1,ldots,x_n)=f_3(x_1,ldots,x_n)\
&,,colorblue=(1-n)sum_i=1^nx_i^2+2sum_1leq i<jleq nx_ix_j+sum_i=1^n(2i-n-1)x_i
endalign*
answered Mar 25 at 14:48
Markus ScheuerMarkus Scheuer
63.5k460151
$endgroup$
add a comment |
$begingroup$
We take an algebraic approach and consider the expressions as quadratic polynomials in $n$ variables $x_1,x_2,ldots,x_n$. We show equality by comparing the coefficients of corresponding terms.
It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.
We introduce $f_1,f_2,f_3$ as
beginalign*
f_1(x_1,ldots,x_n)&=sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
f_2(x_1,ldots,x_n)&=left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_i\
f_3(x_1,ldots,x_n)&=-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2+frac14nsum_i=1^n(n-2i+1)^2
endalign*
We start with the square terms.
We obtain for $1leq kleq n$:
beginalign*
colorblue[x_k^2]f_1(x_1,ldots,x_n)&=[x_k^2]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&=-[x_k^2]sum_1leq i<jleq nleft(x_j-x_iright)^2\
&=-[x_k^2]sum_1leq i<kleft(x_k-x_iright)^2-[x_k^2]sum_k<jleq nleft(x_j-x_kright)^2\
&=-(k-1)-(n-k)\
&,,colorblue=1-n\
colorblue[x_k^2]f_2(x_1,ldots,x_n)&=[x_k^2]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&=[x_k^2]sum_i=1^nx_i^2-n[x_k^2]sum_i=1^nx_i^2\
&,,colorblue=1-n\
colorblue[x_k^2]f_3(x_1,ldots,x_n)&=[x_k^2]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_k^2]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&=-n[x_k^2]sum_i=1^nleft(x_i^2-2x_icdotfrac1nsum_j=1^nx_j+left(frac1nsum_j=1^nx_jright)^2right)\
&=-n[x_k^2]sum_i=1^nx_i^2+2[x_k^2]sum_i=1^nx_isum_j=1^nx_j-frac1n[x_k^2]sum_i=1^nleft(sum_j=1^nx_jright)^2\
&=-n+2-1\
&,,colorblue=1-n
endalign*
Now we check the mixed quadratic terms.
We obtain for $1leq k<lleq n$:
beginalign*
colorblue[x_kx_l]f_1(x_1,ldots,x_n)&=[x_kx_l]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&=-[x_kx_l]sum_1leq i<jleq nleft(x_j-x_iright)^2\
&=2[x_kx_l]sum_1leq i<jleq nx_ix_j\
&,,colorblue=2\
colorblue[x_kx_l]f_2(x_1,ldots,x_n)&=[x_kx_l]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&=[x_kx_l]left(sum_i=1^nx_iright)^2\
&=[x_kx_l]left(sum_i=1^nx_i^2+2sum_1leq i<jleq nx_ix_jright)\
&,,colorblue=2\
colorblue[x_kx_l]f_3(x_1,ldots,x_n)&=[x_k^2]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_kx_l]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&=[x_kx_l]sum_i=1^nleft(2x_isum_j=1^nx_jright)\
&,,colorblue=2
endalign*
... the linear terms ...
We obtain for $ 1leq kleq n$:
beginalign*
colorblue[x_k]f_1(x_1,ldots,x_n)&=[x_k]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&=[x_k]sum_1leq i<jleq nleft(x_j-x_iright)\
&=[x_k]sum_1leq i<kleft(x_k-x_iright)+[x_k]sum_k<jleq nleft(x_j-x_kright)\
&=(k-1)-(n-k)\
&,,colorblue=2k-n-1\
colorblue[x_k]f_2(x_1,ldots,x_n)&=[x_k]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&=[x_k]left(-sum_i=1^n(n-2i+1)x_iright)\
&,,colorblue=2k-n-1\
colorblue[x_k]f_3(x_1,ldots,x_n)&=[x_k]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_k]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&=-n[x_k]sum_i=1^nleft(2x_icdotfracn-2i+12nright)\
&qquadqquadqquad-n[x_k]sum_i=1^nleft(-2cdotfrac1nsum_j=1^nx_jcdotfracn-2i+12nright)\
&=-[x_k]sum_i=1^nx_i(n-2i+1)+[x_k]sum_i=1^nfrac1nsum_j=1^nx_j(n-2i+1)\
&=-(n-2k+1)+sum_i=1^nfrac1n(n-2i+1)\
&=-(n-2k+1)+(n+1-n-1)\
&,,colorblue=2k-n-1
endalign*
and finally the constant term .
We obtain
beginalign*
colorblue[x_0]f_1(x_1,ldots,x_n)&=[x_0]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&,,colorblue=0\
colorblue[x_0]f_2(x_1,ldots,x_n)&=[x_0]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&,,colorblue=0\
colorblue[x_0]f_3(x_1,ldots,x_n)&=[x_0]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_0]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&qquadqquadqquad+frac14nsum_i=1^n(n-2i+1)^2\
&=-n[x_0]sum_i=1^nleft(fracn-2i+12nright)^2+frac14nsum_i=1^n(n-2i+1)^2\
&,,colorblue=0
endalign*
We observe the coefficients of terms with equal powers are equal.
Conclusion:
We obtain by collecting the results from above
beginalign*
colorbluef_1(x_1,ldots,x_n)&colorblue=f_2(x_1,ldots,x_n)=f_3(x_1,ldots,x_n)\
&,,colorblue=(1-n)sum_i=1^nx_i^2+2sum_1leq i<jleq nx_ix_j+sum_i=1^n(2i-n-1)x_i
endalign*
answered Mar 25 at 14:48
Markus ScheuerMarkus Scheuer
63.5k460151
$endgroup$
add a comment |
$begingroup$
We take an algebraic approach and consider the expressions as quadratic polynomials in $n$ variables $x_1,x_2,ldots,x_n$. We show equality by comparing the coefficients of corresponding terms.
It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.
We introduce $f_1,f_2,f_3$ as
beginalign*
f_1(x_1,ldots,x_n)&=sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
f_2(x_1,ldots,x_n)&=left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_i\
f_3(x_1,ldots,x_n)&=-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2+frac14nsum_i=1^n(n-2i+1)^2
endalign*
We start with the square terms.
We obtain for $1leq kleq n$:
beginalign*
colorblue[x_k^2]f_1(x_1,ldots,x_n)&=[x_k^2]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&=-[x_k^2]sum_1leq i<jleq nleft(x_j-x_iright)^2\
&=-[x_k^2]sum_1leq i<kleft(x_k-x_iright)^2-[x_k^2]sum_k<jleq nleft(x_j-x_kright)^2\
&=-(k-1)-(n-k)\
&,,colorblue=1-n\
colorblue[x_k^2]f_2(x_1,ldots,x_n)&=[x_k^2]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&=[x_k^2]sum_i=1^nx_i^2-n[x_k^2]sum_i=1^nx_i^2\
&,,colorblue=1-n\
colorblue[x_k^2]f_3(x_1,ldots,x_n)&=[x_k^2]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_k^2]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&=-n[x_k^2]sum_i=1^nleft(x_i^2-2x_icdotfrac1nsum_j=1^nx_j+left(frac1nsum_j=1^nx_jright)^2right)\
&=-n[x_k^2]sum_i=1^nx_i^2+2[x_k^2]sum_i=1^nx_isum_j=1^nx_j-frac1n[x_k^2]sum_i=1^nleft(sum_j=1^nx_jright)^2\
&=-n+2-1\
&,,colorblue=1-n
endalign*
Now we check the mixed quadratic terms.
We obtain for $1leq k<lleq n$:
beginalign*
colorblue[x_kx_l]f_1(x_1,ldots,x_n)&=[x_kx_l]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&=-[x_kx_l]sum_1leq i<jleq nleft(x_j-x_iright)^2\
&=2[x_kx_l]sum_1leq i<jleq nx_ix_j\
&,,colorblue=2\
colorblue[x_kx_l]f_2(x_1,ldots,x_n)&=[x_kx_l]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&=[x_kx_l]left(sum_i=1^nx_iright)^2\
&=[x_kx_l]left(sum_i=1^nx_i^2+2sum_1leq i<jleq nx_ix_jright)\
&,,colorblue=2\
colorblue[x_kx_l]f_3(x_1,ldots,x_n)&=[x_k^2]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_kx_l]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&=[x_kx_l]sum_i=1^nleft(2x_isum_j=1^nx_jright)\
&,,colorblue=2
endalign*
... the linear terms ...
We obtain for $ 1leq kleq n$:
beginalign*
colorblue[x_k]f_1(x_1,ldots,x_n)&=[x_k]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&=[x_k]sum_1leq i<jleq nleft(x_j-x_iright)\
&=[x_k]sum_1leq i<kleft(x_k-x_iright)+[x_k]sum_k<jleq nleft(x_j-x_kright)\
&=(k-1)-(n-k)\
&,,colorblue=2k-n-1\
colorblue[x_k]f_2(x_1,ldots,x_n)&=[x_k]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&=[x_k]left(-sum_i=1^n(n-2i+1)x_iright)\
&,,colorblue=2k-n-1\
colorblue[x_k]f_3(x_1,ldots,x_n)&=[x_k]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_k]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&=-n[x_k]sum_i=1^nleft(2x_icdotfracn-2i+12nright)\
&qquadqquadqquad-n[x_k]sum_i=1^nleft(-2cdotfrac1nsum_j=1^nx_jcdotfracn-2i+12nright)\
&=-[x_k]sum_i=1^nx_i(n-2i+1)+[x_k]sum_i=1^nfrac1nsum_j=1^nx_j(n-2i+1)\
&=-(n-2k+1)+sum_i=1^nfrac1n(n-2i+1)\
&=-(n-2k+1)+(n+1-n-1)\
&,,colorblue=2k-n-1
endalign*
and finally the constant term .
We obtain
beginalign*
colorblue[x_0]f_1(x_1,ldots,x_n)&=[x_0]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&,,colorblue=0\
colorblue[x_0]f_2(x_1,ldots,x_n)&=[x_0]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&,,colorblue=0\
colorblue[x_0]f_3(x_1,ldots,x_n)&=[x_0]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_0]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&qquadqquadqquad+frac14nsum_i=1^n(n-2i+1)^2\
&=-n[x_0]sum_i=1^nleft(fracn-2i+12nright)^2+frac14nsum_i=1^n(n-2i+1)^2\
&,,colorblue=0
endalign*
We observe the coefficients of terms with equal powers are equal.
Conclusion:
We obtain by collecting the results from above
beginalign*
colorbluef_1(x_1,ldots,x_n)&colorblue=f_2(x_1,ldots,x_n)=f_3(x_1,ldots,x_n)\
&,,colorblue=(1-n)sum_i=1^nx_i^2+2sum_1leq i<jleq nx_ix_j+sum_i=1^n(2i-n-1)x_i
endalign*
answered Mar 25 at 14:48
Markus ScheuerMarkus Scheuer
63.5k460151
$endgroup$
We take an algebraic approach and consider the expressions as quadratic polynomials in $n$ variables $x_1,x_2,ldots,x_n$. We show equality by comparing the coefficients of corresponding terms.
It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.
We introduce $f_1,f_2,f_3$ as
beginalign*
f_1(x_1,ldots,x_n)&=sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
f_2(x_1,ldots,x_n)&=left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_i\
f_3(x_1,ldots,x_n)&=-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2+frac14nsum_i=1^n(n-2i+1)^2
endalign*
We start with the square terms.
We obtain for $1leq kleq n$:
beginalign*
colorblue[x_k^2]f_1(x_1,ldots,x_n)&=[x_k^2]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&=-[x_k^2]sum_1leq i<jleq nleft(x_j-x_iright)^2\
&=-[x_k^2]sum_1leq i<kleft(x_k-x_iright)^2-[x_k^2]sum_k<jleq nleft(x_j-x_kright)^2\
&=-(k-1)-(n-k)\
&,,colorblue=1-n\
colorblue[x_k^2]f_2(x_1,ldots,x_n)&=[x_k^2]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&=[x_k^2]sum_i=1^nx_i^2-n[x_k^2]sum_i=1^nx_i^2\
&,,colorblue=1-n\
colorblue[x_k^2]f_3(x_1,ldots,x_n)&=[x_k^2]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_k^2]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&=-n[x_k^2]sum_i=1^nleft(x_i^2-2x_icdotfrac1nsum_j=1^nx_j+left(frac1nsum_j=1^nx_jright)^2right)\
&=-n[x_k^2]sum_i=1^nx_i^2+2[x_k^2]sum_i=1^nx_isum_j=1^nx_j-frac1n[x_k^2]sum_i=1^nleft(sum_j=1^nx_jright)^2\
&=-n+2-1\
&,,colorblue=1-n
endalign*
Now we check the mixed quadratic terms.
We obtain for $1leq k<lleq n$:
beginalign*
colorblue[x_kx_l]f_1(x_1,ldots,x_n)&=[x_kx_l]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&=-[x_kx_l]sum_1leq i<jleq nleft(x_j-x_iright)^2\
&=2[x_kx_l]sum_1leq i<jleq nx_ix_j\
&,,colorblue=2\
colorblue[x_kx_l]f_2(x_1,ldots,x_n)&=[x_kx_l]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&=[x_kx_l]left(sum_i=1^nx_iright)^2\
&=[x_kx_l]left(sum_i=1^nx_i^2+2sum_1leq i<jleq nx_ix_jright)\
&,,colorblue=2\
colorblue[x_kx_l]f_3(x_1,ldots,x_n)&=[x_k^2]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_kx_l]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&=[x_kx_l]sum_i=1^nleft(2x_isum_j=1^nx_jright)\
&,,colorblue=2
endalign*
... the linear terms ...
We obtain for $ 1leq kleq n$:
beginalign*
colorblue[x_k]f_1(x_1,ldots,x_n)&=[x_k]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&=[x_k]sum_1leq i<jleq nleft(x_j-x_iright)\
&=[x_k]sum_1leq i<kleft(x_k-x_iright)+[x_k]sum_k<jleq nleft(x_j-x_kright)\
&=(k-1)-(n-k)\
&,,colorblue=2k-n-1\
colorblue[x_k]f_2(x_1,ldots,x_n)&=[x_k]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&=[x_k]left(-sum_i=1^n(n-2i+1)x_iright)\
&,,colorblue=2k-n-1\
colorblue[x_k]f_3(x_1,ldots,x_n)&=[x_k]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_k]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&=-n[x_k]sum_i=1^nleft(2x_icdotfracn-2i+12nright)\
&qquadqquadqquad-n[x_k]sum_i=1^nleft(-2cdotfrac1nsum_j=1^nx_jcdotfracn-2i+12nright)\
&=-[x_k]sum_i=1^nx_i(n-2i+1)+[x_k]sum_i=1^nfrac1nsum_j=1^nx_j(n-2i+1)\
&=-(n-2k+1)+sum_i=1^nfrac1n(n-2i+1)\
&=-(n-2k+1)+(n+1-n-1)\
&,,colorblue=2k-n-1
endalign*
and finally the constant term .
We obtain
beginalign*
colorblue[x_0]f_1(x_1,ldots,x_n)&=[x_0]sum_1leq i<jleq nleft(left(x_j-x_iright)-left(x_j-x_iright)^2right)\
&,,colorblue=0\
colorblue[x_0]f_2(x_1,ldots,x_n)&=[x_0]left(left(sum_i=1^nx_iright)^2-nsum_i=1^nx_i^2-sum_i=1^n(n-2i+1)x_iright)\
&,,colorblue=0\
colorblue[x_0]f_3(x_1,ldots,x_n)&=[x_0]left(-nsum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2right.\
&qquadqquadqquadleft.+frac14nsum_i=1^n(n-2i+1)^2right)\
&=-n[x_0]sum_i=1^nleft(x_i-frac1nsum_j=1^nx_j+fracn-2i+12nright)^2\
&qquadqquadqquad+frac14nsum_i=1^n(n-2i+1)^2\
&=-n[x_0]sum_i=1^nleft(fracn-2i+12nright)^2+frac14nsum_i=1^n(n-2i+1)^2\
&,,colorblue=0
endalign*
We observe the coefficients of terms with equal powers are equal.
Conclusion:
We obtain by collecting the results from above
beginalign*
colorbluef_1(x_1,ldots,x_n)&colorblue=f_2(x_1,ldots,x_n)=f_3(x_1,ldots,x_n)\
&,,colorblue=(1-n)sum_i=1^nx_i^2+2sum_1leq i<jleq nx_ix_j+sum_i=1^n(2i-n-1)x_i
endalign*
answered Mar 25 at 14:48
Markus ScheuerMarkus Scheuer
63.5k460151
edited Mar 25 at 16:07
answered Mar 25 at 14:48
Markus ScheuerMarkus Scheuer
63.5k460151
answered Mar 25 at 14:48
Markus ScheuerMarkus Scheuer
63.5k460151
answered Mar 25 at 14:48
Markus ScheuerMarkus Scheuer
63.5k460151
63.5k460151
add a comment |
add a comment |
$begingroup$
$defpeqmathrelphantom=$For the first identity, because$$
sum_i < j (x_j - x_i) = sum_k = 1^n x_k left( sum_l < k 1 + sum_l > k (-1) right) = sum_k = 1^n (2k - n - 1) x_k,
$$begingather*
sum_i < j (x_j - x_i)^2 = sum_k = 1^n x_k^2 left( sum_l < k 1 + sum_l > k 1 right) - 2 sum_i < j x_i x_j\
= (n - 1) sum_k = 1^n x_k^2 - left( left( sum_k = 1^n x_k right)^2 - sum_k = 1^n x_k^2 right) = n sum_k = 1^n x_k^2 - left( sum_k = 1^n x_k right)^2,
endgather*
then$$
sum_i < j ((x_j - x_i) - (x_j - x_i)^2) = left( sum_k = 1^n x_k right)^2 - n sum_k = 1^n x_k^2 - sum_k = 1^n (n - 2k + 1) x_k.
$$
For the second identity, denoting $barx = dfrac1n sumlimits_k = 1^n x_k$,beginalign*
&peq -n sum_k = 1^n left( x_k - barx + frac12n (n - 2k + 1) right)^2 + frac14n sum_k = 1^n (n - 2k + 1)^2\
&= -sum_k = 1^n left( n(x_k - barx)^2 + (n - 2k + 1)(x_k - barx) + frac14n (n - 2k + 1)^2 right) + frac14n sum_k = 1^n (n - 2k + 1)^2\
&= -sum_k = 1^n left( n(x_k - barx)^2 + (n - 2k + 1)(x_k - barx) right)\
&= -n sum_k = 1^n (x_k - barx)^2 - sum_k = 1^n (n - 2k + 1) x_k + barx sum_k = 1^n (n - 2k + 1)\
&= -n left( sum_k = 1^n x_k^2 - nbarx^2 right) - sum_k = 1^n (n - 2k + 1) x_k + 0\
&= left( sum_k = 1^n x_k right)^2 - n sum_k = 1^n x_k^2 - sum_k = 1^n (n - 2k + 1) x_k.
endalign*
answered Mar 25 at 2:33
SaadSaad
20.3k92352
$endgroup$
$begingroup$
Nice. A lot easier than mine.
$endgroup$
– marty cohen
Mar 27 at 6:53
add a comment |
$begingroup$
$defpeqmathrelphantom=$For the first identity, because$$
sum_i < j (x_j - x_i) = sum_k = 1^n x_k left( sum_l < k 1 + sum_l > k (-1) right) = sum_k = 1^n (2k - n - 1) x_k,
$$begingather*
sum_i < j (x_j - x_i)^2 = sum_k = 1^n x_k^2 left( sum_l < k 1 + sum_l > k 1 right) - 2 sum_i < j x_i x_j\
= (n - 1) sum_k = 1^n x_k^2 - left( left( sum_k = 1^n x_k right)^2 - sum_k = 1^n x_k^2 right) = n sum_k = 1^n x_k^2 - left( sum_k = 1^n x_k right)^2,
endgather*
then$$
sum_i < j ((x_j - x_i) - (x_j - x_i)^2) = left( sum_k = 1^n x_k right)^2 - n sum_k = 1^n x_k^2 - sum_k = 1^n (n - 2k + 1) x_k.
$$
For the second identity, denoting $barx = dfrac1n sumlimits_k = 1^n x_k$,beginalign*
&peq -n sum_k = 1^n left( x_k - barx + frac12n (n - 2k + 1) right)^2 + frac14n sum_k = 1^n (n - 2k + 1)^2\
&= -sum_k = 1^n left( n(x_k - barx)^2 + (n - 2k + 1)(x_k - barx) + frac14n (n - 2k + 1)^2 right) + frac14n sum_k = 1^n (n - 2k + 1)^2\
&= -sum_k = 1^n left( n(x_k - barx)^2 + (n - 2k + 1)(x_k - barx) right)\
&= -n sum_k = 1^n (x_k - barx)^2 - sum_k = 1^n (n - 2k + 1) x_k + barx sum_k = 1^n (n - 2k + 1)\
&= -n left( sum_k = 1^n x_k^2 - nbarx^2 right) - sum_k = 1^n (n - 2k + 1) x_k + 0\
&= left( sum_k = 1^n x_k right)^2 - n sum_k = 1^n x_k^2 - sum_k = 1^n (n - 2k + 1) x_k.
endalign*
answered Mar 25 at 2:33
SaadSaad
20.3k92352
$endgroup$
$begingroup$
Nice. A lot easier than mine.
$endgroup$
– marty cohen
Mar 27 at 6:53
add a comment |
$begingroup$
$defpeqmathrelphantom=$For the first identity, because$$
sum_i < j (x_j - x_i) = sum_k = 1^n x_k left( sum_l < k 1 + sum_l > k (-1) right) = sum_k = 1^n (2k - n - 1) x_k,
$$begingather*
sum_i < j (x_j - x_i)^2 = sum_k = 1^n x_k^2 left( sum_l < k 1 + sum_l > k 1 right) - 2 sum_i < j x_i x_j\
= (n - 1) sum_k = 1^n x_k^2 - left( left( sum_k = 1^n x_k right)^2 - sum_k = 1^n x_k^2 right) = n sum_k = 1^n x_k^2 - left( sum_k = 1^n x_k right)^2,
endgather*
then$$
sum_i < j ((x_j - x_i) - (x_j - x_i)^2) = left( sum_k = 1^n x_k right)^2 - n sum_k = 1^n x_k^2 - sum_k = 1^n (n - 2k + 1) x_k.
$$
For the second identity, denoting $barx = dfrac1n sumlimits_k = 1^n x_k$,beginalign*
&peq -n sum_k = 1^n left( x_k - barx + frac12n (n - 2k + 1) right)^2 + frac14n sum_k = 1^n (n - 2k + 1)^2\
&= -sum_k = 1^n left( n(x_k - barx)^2 + (n - 2k + 1)(x_k - barx) + frac14n (n - 2k + 1)^2 right) + frac14n sum_k = 1^n (n - 2k + 1)^2\
&= -sum_k = 1^n left( n(x_k - barx)^2 + (n - 2k + 1)(x_k - barx) right)\
&= -n sum_k = 1^n (x_k - barx)^2 - sum_k = 1^n (n - 2k + 1) x_k + barx sum_k = 1^n (n - 2k + 1)\
&= -n left( sum_k = 1^n x_k^2 - nbarx^2 right) - sum_k = 1^n (n - 2k + 1) x_k + 0\
&= left( sum_k = 1^n x_k right)^2 - n sum_k = 1^n x_k^2 - sum_k = 1^n (n - 2k + 1) x_k.
endalign*
answered Mar 25 at 2:33
SaadSaad
20.3k92352
$endgroup$
$defpeqmathrelphantom=$For the first identity, because$$
sum_i < j (x_j - x_i) = sum_k = 1^n x_k left( sum_l < k 1 + sum_l > k (-1) right) = sum_k = 1^n (2k - n - 1) x_k,
$$begingather*
sum_i < j (x_j - x_i)^2 = sum_k = 1^n x_k^2 left( sum_l < k 1 + sum_l > k 1 right) - 2 sum_i < j x_i x_j\
= (n - 1) sum_k = 1^n x_k^2 - left( left( sum_k = 1^n x_k right)^2 - sum_k = 1^n x_k^2 right) = n sum_k = 1^n x_k^2 - left( sum_k = 1^n x_k right)^2,
endgather*
then$$
sum_i < j ((x_j - x_i) - (x_j - x_i)^2) = left( sum_k = 1^n x_k right)^2 - n sum_k = 1^n x_k^2 - sum_k = 1^n (n - 2k + 1) x_k.
$$
For the second identity, denoting $barx = dfrac1n sumlimits_k = 1^n x_k$,beginalign*
&peq -n sum_k = 1^n left( x_k - barx + frac12n (n - 2k + 1) right)^2 + frac14n sum_k = 1^n (n - 2k + 1)^2\
&= -sum_k = 1^n left( n(x_k - barx)^2 + (n - 2k + 1)(x_k - barx) + frac14n (n - 2k + 1)^2 right) + frac14n sum_k = 1^n (n - 2k + 1)^2\
&= -sum_k = 1^n left( n(x_k - barx)^2 + (n - 2k + 1)(x_k - barx) right)\
&= -n sum_k = 1^n (x_k - barx)^2 - sum_k = 1^n (n - 2k + 1) x_k + barx sum_k = 1^n (n - 2k + 1)\
&= -n left( sum_k = 1^n x_k^2 - nbarx^2 right) - sum_k = 1^n (n - 2k + 1) x_k + 0\
&= left( sum_k = 1^n x_k right)^2 - n sum_k = 1^n x_k^2 - sum_k = 1^n (n - 2k + 1) x_k.
endalign*
answered Mar 25 at 2:33
SaadSaad
20.3k92352
answered Mar 25 at 2:33
SaadSaad
20.3k92352
answered Mar 25 at 2:33
SaadSaad
20.3k92352
answered Mar 25 at 2:33
SaadSaad
20.3k92352
20.3k92352
$begingroup$
Nice. A lot easier than mine.
$endgroup$
– marty cohen
Mar 27 at 6:53
add a comment |
$begingroup$
Nice. A lot easier than mine.
$endgroup$
– marty cohen
Mar 27 at 6:53
$begingroup$
Nice. A lot easier than mine.
$endgroup$
– marty cohen
Mar 27 at 6:53
$begingroup$
Nice. A lot easier than mine.
$endgroup$
– marty cohen
Mar 27 at 6:53
add a comment |
$begingroup$
An alternative to @martycohen's approach, using derivatives. I think that if I didn't have to write out details about the Kronecker delta, this might be shorter than Marty's, but I can't promist that.
Both sides are evidently quadratics in the $x_i$ variables, with no constant terms. That is to say, they have the form
$$
H = (sum_ij c_ij x_i x_j ) + sum_i e_i x_i
$$
If we differentiate such a thing with respect to $x_k$, we get
$$
fracpartial Hpartial x_k = (sum_i c_ik x_i + sum_j c_kj x_j) + e_k,
$$
and if we set all the $x_i$ to zero, we get just $e_k$. Similarly, if we differentiate twice, we can find $c_kp$. By comparing these for the two sides, we'll see the two quadratics are equal.
The derivative of $x_i$ with respect to $x_k$ is $delta_ik = begincases 1 & i = k\ 0 & i ne k endcases$, and $sum_i x_i delta_ik = x_k$, which we'll use frequently in various forms. Also note that
$$
tagsum-j
sum_i =1^n sum_j = i+1^n delta_jk = k-1,
$$
because the inner sum is either $0$ or $1$; it's $1$ whenever $k > i$. This occurs, in the outer sum, for $i = 1, 2, ldots, k-1$, i.e., $k-1$ times. Similarly,
$$
tagsum-i
sum_i =1^n sum_j = i+1^n delta_ik = n-k.
$$
Finally,
$$
tagsum-pk
sum_i =1^n sum_j = i+1^n delta_ikdelta_jp =
sum_j = k+1^n delta_jp
= delta_k < p,
$$
by which I mean the sum is $1$ if $k < p$, and $0$ otherwise.
Returning to the main equation, and calling the left and right-hand expressions $L$ and $R$, we'll check first to see that the linear-term coefficient of $x_k$ is identical in both.
The derivative of the LHS with respect to $x_k$ is
beginalign
fracpartial Lpartial x_k &= sum_i=1^n sum_j = i+1^n fracpartial left((x_j-x_i)-(x_j-x_i)^2right) partial x_k\
& = sum_i=1^n sum_j = i+1^n left((delta_jk-delta_ik)-2(x_j-x_i)(delta_jk-delta_ik)right)
endalign
Evaluated when all the $x_i$ are zero, we get
beginalign
fracpartial Lpartial x_k(0,0,ldots, 0)
& = sum_i=1^n sum_j = i+1^n (delta_jk-delta_ik)\
& = sum_i=1^n sum_j = i+1^n delta_jk-sum_i=1^n sum_j = i+1^ndelta_ik\
& = (k-1) - (n-k) & textby sum-i and sum-j above \
&= -n + 2k - 1.
endalign
The derivative of the right-hand side is
beginalign
fracpartial Rpartial x_k
&= fracpartial biggl[ big(sum_i=1^nx_ibig)^2-nsum_i=1^nx_i^2 - sum_i=1^n(n-2i+1)x_ibiggr]partial x_k\
&= 2big(sum_i=1^nx_ibig) sum_i=1^n delta_ik -n fracpartial sum_i=1^nx_i^2partial x_k - fracpartial sum_i=1^n(n-2i+1)x_ipartial x_k \
&= 2big(sum_i=1^nx_ibig)
-n biggl[ sum_i=1^n2x_i delta_ik biggr]
- sum_i=1^n (n-2i+1)delta_ik \
&= 2big(sum_i=1^nx_ibig)
-2n x_k
- (n-2k+1) \
endalign
When $x_1 = x_2 = ldots = x_n = 0$, we again get a value of $-(n-2k + 1) = -n + 2k - 1$. So the linear terms on the two sides are equal.
Now let's look at the second derivatives. We have
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = sum_i=1^n sum_j = i+1^n left(-2(delta_jp-delta_ip)(delta_jk-delta_ik)right)\
& = -2 sum_i=1^n sum_j = i+1^n
delta_jpdelta_jk - delta_jpdelta_ik-delta_ipdelta_jk + delta_ipdelta_ik
endalign
First consider the case $k = p$:
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = -2 sum_i=1^n sum_j = i+1^n
delta_jkdelta_jk - delta_jkdelta_ik-delta_ikdelta_jk + delta_ikdelta_ik\
& = -2 sum_i=1^n sum_j = i+1^n
delta_jk - 2delta_jkdelta_ik + delta_ik\
& = -2biggl[ (k-1) + (n-k) - 2sum_i=1^n sum_j = i+1^n
delta_jkdelta_ik biggr] & textby sum-i and sum-j\
endalign
The remaining product $delta_jkdelta_ik$ is $1$ only if $i$ and $j$ are equal, but since $j$ starts at $i+1$, this never happens. Hence
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = 2 - 2n
endalign
in the case where $k = p$.
Now look at $k ne p$. We have
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = -2 sum_i=1^n sum_j = i+1^n delta_jpdelta_jk +
2 sum_i=1^n sum_j = i+1^n delta_jpdelta_ik +
2 sum_i=1^n sum_j = i+1^n delta_ipdelta_jk - 2 sum_i=1^n sum_j = i+1^n delta_ipdelta_ik
endalign
By sum-kp, the two middle terms are $delta_k < p$ and $delta_p<k$, so exactly one of them is $1$, and we can replace their sum with a $1$ (which gets multiplied by the $2$ in front!). So we have
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = 2
-2 sum_i=1^n sum_j = i+1^ndelta_jpdelta_jk - 2 sum_i=1^n sum_j = i+1^n delta_ipdelta_ik \
endalign
Furthermore, because $k$ and $p$ are distinct, $j$ cannot equal both of them, so the first sun is zero; similarly for the second. We end up with
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = 2
endalign
On the right-hand side, we have
beginalign
fracpartial Rpartial x_k
&= 2big(sum_i=1^nx_ibig)
-2n x_k
- (n-2k+1) \
endalign
we get
beginalign
fracpartial^2 Rpartial x_k partial x_p
&= 2big(sum_i=1^n
delta_ipbig)
-2n delta_kp \
&= 2 -2n delta_kp \
endalign
which agrees exactly with the result for the left-hand side. We're done!
answered Mar 22 at 21:42
John HughesJohn Hughes
65.1k24292
$endgroup$
add a comment |
$begingroup$
An alternative to @martycohen's approach, using derivatives. I think that if I didn't have to write out details about the Kronecker delta, this might be shorter than Marty's, but I can't promist that.
Both sides are evidently quadratics in the $x_i$ variables, with no constant terms. That is to say, they have the form
$$
H = (sum_ij c_ij x_i x_j ) + sum_i e_i x_i
$$
If we differentiate such a thing with respect to $x_k$, we get
$$
fracpartial Hpartial x_k = (sum_i c_ik x_i + sum_j c_kj x_j) + e_k,
$$
and if we set all the $x_i$ to zero, we get just $e_k$. Similarly, if we differentiate twice, we can find $c_kp$. By comparing these for the two sides, we'll see the two quadratics are equal.
The derivative of $x_i$ with respect to $x_k$ is $delta_ik = begincases 1 & i = k\ 0 & i ne k endcases$, and $sum_i x_i delta_ik = x_k$, which we'll use frequently in various forms. Also note that
$$
tagsum-j
sum_i =1^n sum_j = i+1^n delta_jk = k-1,
$$
because the inner sum is either $0$ or $1$; it's $1$ whenever $k > i$. This occurs, in the outer sum, for $i = 1, 2, ldots, k-1$, i.e., $k-1$ times. Similarly,
$$
tagsum-i
sum_i =1^n sum_j = i+1^n delta_ik = n-k.
$$
Finally,
$$
tagsum-pk
sum_i =1^n sum_j = i+1^n delta_ikdelta_jp =
sum_j = k+1^n delta_jp
= delta_k < p,
$$
by which I mean the sum is $1$ if $k < p$, and $0$ otherwise.
Returning to the main equation, and calling the left and right-hand expressions $L$ and $R$, we'll check first to see that the linear-term coefficient of $x_k$ is identical in both.
The derivative of the LHS with respect to $x_k$ is
beginalign
fracpartial Lpartial x_k &= sum_i=1^n sum_j = i+1^n fracpartial left((x_j-x_i)-(x_j-x_i)^2right) partial x_k\
& = sum_i=1^n sum_j = i+1^n left((delta_jk-delta_ik)-2(x_j-x_i)(delta_jk-delta_ik)right)
endalign
Evaluated when all the $x_i$ are zero, we get
beginalign
fracpartial Lpartial x_k(0,0,ldots, 0)
& = sum_i=1^n sum_j = i+1^n (delta_jk-delta_ik)\
& = sum_i=1^n sum_j = i+1^n delta_jk-sum_i=1^n sum_j = i+1^ndelta_ik\
& = (k-1) - (n-k) & textby sum-i and sum-j above \
&= -n + 2k - 1.
endalign
The derivative of the right-hand side is
beginalign
fracpartial Rpartial x_k
&= fracpartial biggl[ big(sum_i=1^nx_ibig)^2-nsum_i=1^nx_i^2 - sum_i=1^n(n-2i+1)x_ibiggr]partial x_k\
&= 2big(sum_i=1^nx_ibig) sum_i=1^n delta_ik -n fracpartial sum_i=1^nx_i^2partial x_k - fracpartial sum_i=1^n(n-2i+1)x_ipartial x_k \
&= 2big(sum_i=1^nx_ibig)
-n biggl[ sum_i=1^n2x_i delta_ik biggr]
- sum_i=1^n (n-2i+1)delta_ik \
&= 2big(sum_i=1^nx_ibig)
-2n x_k
- (n-2k+1) \
endalign
When $x_1 = x_2 = ldots = x_n = 0$, we again get a value of $-(n-2k + 1) = -n + 2k - 1$. So the linear terms on the two sides are equal.
Now let's look at the second derivatives. We have
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = sum_i=1^n sum_j = i+1^n left(-2(delta_jp-delta_ip)(delta_jk-delta_ik)right)\
& = -2 sum_i=1^n sum_j = i+1^n
delta_jpdelta_jk - delta_jpdelta_ik-delta_ipdelta_jk + delta_ipdelta_ik
endalign
First consider the case $k = p$:
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = -2 sum_i=1^n sum_j = i+1^n
delta_jkdelta_jk - delta_jkdelta_ik-delta_ikdelta_jk + delta_ikdelta_ik\
& = -2 sum_i=1^n sum_j = i+1^n
delta_jk - 2delta_jkdelta_ik + delta_ik\
& = -2biggl[ (k-1) + (n-k) - 2sum_i=1^n sum_j = i+1^n
delta_jkdelta_ik biggr] & textby sum-i and sum-j\
endalign
The remaining product $delta_jkdelta_ik$ is $1$ only if $i$ and $j$ are equal, but since $j$ starts at $i+1$, this never happens. Hence
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = 2 - 2n
endalign
in the case where $k = p$.
Now look at $k ne p$. We have
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = -2 sum_i=1^n sum_j = i+1^n delta_jpdelta_jk +
2 sum_i=1^n sum_j = i+1^n delta_jpdelta_ik +
2 sum_i=1^n sum_j = i+1^n delta_ipdelta_jk - 2 sum_i=1^n sum_j = i+1^n delta_ipdelta_ik
endalign
By sum-kp, the two middle terms are $delta_k < p$ and $delta_p<k$, so exactly one of them is $1$, and we can replace their sum with a $1$ (which gets multiplied by the $2$ in front!). So we have
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = 2
-2 sum_i=1^n sum_j = i+1^ndelta_jpdelta_jk - 2 sum_i=1^n sum_j = i+1^n delta_ipdelta_ik \
endalign
Furthermore, because $k$ and $p$ are distinct, $j$ cannot equal both of them, so the first sun is zero; similarly for the second. We end up with
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = 2
endalign
On the right-hand side, we have
beginalign
fracpartial Rpartial x_k
&= 2big(sum_i=1^nx_ibig)
-2n x_k
- (n-2k+1) \
endalign
we get
beginalign
fracpartial^2 Rpartial x_k partial x_p
&= 2big(sum_i=1^n
delta_ipbig)
-2n delta_kp \
&= 2 -2n delta_kp \
endalign
which agrees exactly with the result for the left-hand side. We're done!
answered Mar 22 at 21:42
John HughesJohn Hughes
65.1k24292
$endgroup$
add a comment |
$begingroup$
An alternative to @martycohen's approach, using derivatives. I think that if I didn't have to write out details about the Kronecker delta, this might be shorter than Marty's, but I can't promist that.
Both sides are evidently quadratics in the $x_i$ variables, with no constant terms. That is to say, they have the form
$$
H = (sum_ij c_ij x_i x_j ) + sum_i e_i x_i
$$
If we differentiate such a thing with respect to $x_k$, we get
$$
fracpartial Hpartial x_k = (sum_i c_ik x_i + sum_j c_kj x_j) + e_k,
$$
and if we set all the $x_i$ to zero, we get just $e_k$. Similarly, if we differentiate twice, we can find $c_kp$. By comparing these for the two sides, we'll see the two quadratics are equal.
The derivative of $x_i$ with respect to $x_k$ is $delta_ik = begincases 1 & i = k\ 0 & i ne k endcases$, and $sum_i x_i delta_ik = x_k$, which we'll use frequently in various forms. Also note that
$$
tagsum-j
sum_i =1^n sum_j = i+1^n delta_jk = k-1,
$$
because the inner sum is either $0$ or $1$; it's $1$ whenever $k > i$. This occurs, in the outer sum, for $i = 1, 2, ldots, k-1$, i.e., $k-1$ times. Similarly,
$$
tagsum-i
sum_i =1^n sum_j = i+1^n delta_ik = n-k.
$$
Finally,
$$
tagsum-pk
sum_i =1^n sum_j = i+1^n delta_ikdelta_jp =
sum_j = k+1^n delta_jp
= delta_k < p,
$$
by which I mean the sum is $1$ if $k < p$, and $0$ otherwise.
Returning to the main equation, and calling the left and right-hand expressions $L$ and $R$, we'll check first to see that the linear-term coefficient of $x_k$ is identical in both.
The derivative of the LHS with respect to $x_k$ is
beginalign
fracpartial Lpartial x_k &= sum_i=1^n sum_j = i+1^n fracpartial left((x_j-x_i)-(x_j-x_i)^2right) partial x_k\
& = sum_i=1^n sum_j = i+1^n left((delta_jk-delta_ik)-2(x_j-x_i)(delta_jk-delta_ik)right)
endalign
Evaluated when all the $x_i$ are zero, we get
beginalign
fracpartial Lpartial x_k(0,0,ldots, 0)
& = sum_i=1^n sum_j = i+1^n (delta_jk-delta_ik)\
& = sum_i=1^n sum_j = i+1^n delta_jk-sum_i=1^n sum_j = i+1^ndelta_ik\
& = (k-1) - (n-k) & textby sum-i and sum-j above \
&= -n + 2k - 1.
endalign
The derivative of the right-hand side is
beginalign
fracpartial Rpartial x_k
&= fracpartial biggl[ big(sum_i=1^nx_ibig)^2-nsum_i=1^nx_i^2 - sum_i=1^n(n-2i+1)x_ibiggr]partial x_k\
&= 2big(sum_i=1^nx_ibig) sum_i=1^n delta_ik -n fracpartial sum_i=1^nx_i^2partial x_k - fracpartial sum_i=1^n(n-2i+1)x_ipartial x_k \
&= 2big(sum_i=1^nx_ibig)
-n biggl[ sum_i=1^n2x_i delta_ik biggr]
- sum_i=1^n (n-2i+1)delta_ik \
&= 2big(sum_i=1^nx_ibig)
-2n x_k
- (n-2k+1) \
endalign
When $x_1 = x_2 = ldots = x_n = 0$, we again get a value of $-(n-2k + 1) = -n + 2k - 1$. So the linear terms on the two sides are equal.
Now let's look at the second derivatives. We have
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = sum_i=1^n sum_j = i+1^n left(-2(delta_jp-delta_ip)(delta_jk-delta_ik)right)\
& = -2 sum_i=1^n sum_j = i+1^n
delta_jpdelta_jk - delta_jpdelta_ik-delta_ipdelta_jk + delta_ipdelta_ik
endalign
First consider the case $k = p$:
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = -2 sum_i=1^n sum_j = i+1^n
delta_jkdelta_jk - delta_jkdelta_ik-delta_ikdelta_jk + delta_ikdelta_ik\
& = -2 sum_i=1^n sum_j = i+1^n
delta_jk - 2delta_jkdelta_ik + delta_ik\
& = -2biggl[ (k-1) + (n-k) - 2sum_i=1^n sum_j = i+1^n
delta_jkdelta_ik biggr] & textby sum-i and sum-j\
endalign
The remaining product $delta_jkdelta_ik$ is $1$ only if $i$ and $j$ are equal, but since $j$ starts at $i+1$, this never happens. Hence
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = 2 - 2n
endalign
in the case where $k = p$.
Now look at $k ne p$. We have
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = -2 sum_i=1^n sum_j = i+1^n delta_jpdelta_jk +
2 sum_i=1^n sum_j = i+1^n delta_jpdelta_ik +
2 sum_i=1^n sum_j = i+1^n delta_ipdelta_jk - 2 sum_i=1^n sum_j = i+1^n delta_ipdelta_ik
endalign
By sum-kp, the two middle terms are $delta_k < p$ and $delta_p<k$, so exactly one of them is $1$, and we can replace their sum with a $1$ (which gets multiplied by the $2$ in front!). So we have
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = 2
-2 sum_i=1^n sum_j = i+1^ndelta_jpdelta_jk - 2 sum_i=1^n sum_j = i+1^n delta_ipdelta_ik \
endalign
Furthermore, because $k$ and $p$ are distinct, $j$ cannot equal both of them, so the first sun is zero; similarly for the second. We end up with
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = 2
endalign
On the right-hand side, we have
beginalign
fracpartial Rpartial x_k
&= 2big(sum_i=1^nx_ibig)
-2n x_k
- (n-2k+1) \
endalign
we get
beginalign
fracpartial^2 Rpartial x_k partial x_p
&= 2big(sum_i=1^n
delta_ipbig)
-2n delta_kp \
&= 2 -2n delta_kp \
endalign
which agrees exactly with the result for the left-hand side. We're done!
answered Mar 22 at 21:42
John HughesJohn Hughes
65.1k24292
$endgroup$
An alternative to @martycohen's approach, using derivatives. I think that if I didn't have to write out details about the Kronecker delta, this might be shorter than Marty's, but I can't promist that.
Both sides are evidently quadratics in the $x_i$ variables, with no constant terms. That is to say, they have the form
$$
H = (sum_ij c_ij x_i x_j ) + sum_i e_i x_i
$$
If we differentiate such a thing with respect to $x_k$, we get
$$
fracpartial Hpartial x_k = (sum_i c_ik x_i + sum_j c_kj x_j) + e_k,
$$
and if we set all the $x_i$ to zero, we get just $e_k$. Similarly, if we differentiate twice, we can find $c_kp$. By comparing these for the two sides, we'll see the two quadratics are equal.
The derivative of $x_i$ with respect to $x_k$ is $delta_ik = begincases 1 & i = k\ 0 & i ne k endcases$, and $sum_i x_i delta_ik = x_k$, which we'll use frequently in various forms. Also note that
$$
tagsum-j
sum_i =1^n sum_j = i+1^n delta_jk = k-1,
$$
because the inner sum is either $0$ or $1$; it's $1$ whenever $k > i$. This occurs, in the outer sum, for $i = 1, 2, ldots, k-1$, i.e., $k-1$ times. Similarly,
$$
tagsum-i
sum_i =1^n sum_j = i+1^n delta_ik = n-k.
$$
Finally,
$$
tagsum-pk
sum_i =1^n sum_j = i+1^n delta_ikdelta_jp =
sum_j = k+1^n delta_jp
= delta_k < p,
$$
by which I mean the sum is $1$ if $k < p$, and $0$ otherwise.
Returning to the main equation, and calling the left and right-hand expressions $L$ and $R$, we'll check first to see that the linear-term coefficient of $x_k$ is identical in both.
The derivative of the LHS with respect to $x_k$ is
beginalign
fracpartial Lpartial x_k &= sum_i=1^n sum_j = i+1^n fracpartial left((x_j-x_i)-(x_j-x_i)^2right) partial x_k\
& = sum_i=1^n sum_j = i+1^n left((delta_jk-delta_ik)-2(x_j-x_i)(delta_jk-delta_ik)right)
endalign
Evaluated when all the $x_i$ are zero, we get
beginalign
fracpartial Lpartial x_k(0,0,ldots, 0)
& = sum_i=1^n sum_j = i+1^n (delta_jk-delta_ik)\
& = sum_i=1^n sum_j = i+1^n delta_jk-sum_i=1^n sum_j = i+1^ndelta_ik\
& = (k-1) - (n-k) & textby sum-i and sum-j above \
&= -n + 2k - 1.
endalign
The derivative of the right-hand side is
beginalign
fracpartial Rpartial x_k
&= fracpartial biggl[ big(sum_i=1^nx_ibig)^2-nsum_i=1^nx_i^2 - sum_i=1^n(n-2i+1)x_ibiggr]partial x_k\
&= 2big(sum_i=1^nx_ibig) sum_i=1^n delta_ik -n fracpartial sum_i=1^nx_i^2partial x_k - fracpartial sum_i=1^n(n-2i+1)x_ipartial x_k \
&= 2big(sum_i=1^nx_ibig)
-n biggl[ sum_i=1^n2x_i delta_ik biggr]
- sum_i=1^n (n-2i+1)delta_ik \
&= 2big(sum_i=1^nx_ibig)
-2n x_k
- (n-2k+1) \
endalign
When $x_1 = x_2 = ldots = x_n = 0$, we again get a value of $-(n-2k + 1) = -n + 2k - 1$. So the linear terms on the two sides are equal.
Now let's look at the second derivatives. We have
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = sum_i=1^n sum_j = i+1^n left(-2(delta_jp-delta_ip)(delta_jk-delta_ik)right)\
& = -2 sum_i=1^n sum_j = i+1^n
delta_jpdelta_jk - delta_jpdelta_ik-delta_ipdelta_jk + delta_ipdelta_ik
endalign
First consider the case $k = p$:
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = -2 sum_i=1^n sum_j = i+1^n
delta_jkdelta_jk - delta_jkdelta_ik-delta_ikdelta_jk + delta_ikdelta_ik\
& = -2 sum_i=1^n sum_j = i+1^n
delta_jk - 2delta_jkdelta_ik + delta_ik\
& = -2biggl[ (k-1) + (n-k) - 2sum_i=1^n sum_j = i+1^n
delta_jkdelta_ik biggr] & textby sum-i and sum-j\
endalign
The remaining product $delta_jkdelta_ik$ is $1$ only if $i$ and $j$ are equal, but since $j$ starts at $i+1$, this never happens. Hence
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = 2 - 2n
endalign
in the case where $k = p$.
Now look at $k ne p$. We have
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = -2 sum_i=1^n sum_j = i+1^n delta_jpdelta_jk +
2 sum_i=1^n sum_j = i+1^n delta_jpdelta_ik +
2 sum_i=1^n sum_j = i+1^n delta_ipdelta_jk - 2 sum_i=1^n sum_j = i+1^n delta_ipdelta_ik
endalign
By sum-kp, the two middle terms are $delta_k < p$ and $delta_p<k$, so exactly one of them is $1$, and we can replace their sum with a $1$ (which gets multiplied by the $2$ in front!). So we have
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = 2
-2 sum_i=1^n sum_j = i+1^ndelta_jpdelta_jk - 2 sum_i=1^n sum_j = i+1^n delta_ipdelta_ik \
endalign
Furthermore, because $k$ and $p$ are distinct, $j$ cannot equal both of them, so the first sun is zero; similarly for the second. We end up with
beginalign
fracpartial^2 Lpartial x_k partial x_p
& = 2
endalign
On the right-hand side, we have
beginalign
fracpartial Rpartial x_k
&= 2big(sum_i=1^nx_ibig)
-2n x_k
- (n-2k+1) \
endalign
we get
beginalign
fracpartial^2 Rpartial x_k partial x_p
&= 2big(sum_i=1^n
delta_ipbig)
-2n delta_kp \
&= 2 -2n delta_kp \
endalign
which agrees exactly with the result for the left-hand side. We're done!
answered Mar 22 at 21:42
John HughesJohn Hughes
65.1k24292
edited Mar 23 at 18:00
answered Mar 22 at 21:42
John HughesJohn Hughes
65.1k24292
answered Mar 22 at 21:42
John HughesJohn Hughes
65.1k24292
answered Mar 22 at 21:42
John HughesJohn Hughes
65.1k24292
65.1k24292
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3155506%2fhow-to-prove-this-identity-nicely%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Now I bounty because I can't find this the last identity
$endgroup$
– function sug
Mar 25 at 1:07