0
$\begingroup$

I am reading Chapter 2 of Concrete Mathematics, and have some trouble understanding the rationale behind two identities used for simplification.

1) [1<=j<=k<=n]+[1<=k<=j<=n] = [1<=j,k<=n]+[1<=j=k<=n]
2) [1<=j<k<=n]+[1<=k<j<=n] = [1<=j,k<=n]-[1<=j=k<=n]

Does anyone have any insight on how to prove this, intuition for this or way to think about it. I took some examples of 3X3 matrix and laid out the terms, the relation holds but I don't have an intuition of why it does. Any help is greatly appreciated. Thanks!

$\endgroup$
0
$\begingroup$

Here's how to think about it: it all starts with $[1\le j,k\le n]$. Subtract the other term from both sides to get $$[1\le j,k\le n] = [1\le j\le k\le n]+[1\le k\le j\le n] - [1\le j=k\le n]$$

If $j,k$ are not both int the interval $[1,n]$, then both sides are just zero. If instead they are, then the LHS is $1$. Now, there are three possibilities: $j<k$, $j>k$, $j=k$. If $j<k$, then the first term on the right is $1$, while the others are zero. If $j>k$, then the second term on the right is $1$, while the others are $0$. Lastly, if $j=k$, then the first two terms on the right are both $1$. However, we then add $-1$ from the last term, to get $1$ again, via $1+1-1$.


The other one is similar.

$\endgroup$
  • $\begingroup$ thanks @vadim123 your proof makes sense. Any advice on how one can come up with this kind of relation . Given the relation , I see how this proof works and make sense, but how to develop the intuition to come up with the relation in the first place ? $\endgroup$ – john smith Jun 11 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.