2
$\begingroup$

I was solving "multiple sigma" questions, while I stumbled upon this:

Find $$\sum_{i=0}^n\sum_{j=0}^n\sum_{k=0}^n \frac{1}{3^i3^j3^k} \ ,i\ne j \ne k$$


I'm used to solve double sigma problems (like $\sum_{1\le i<j\le n}\sum i.j$) using triangles like these:

However I'm not sure about how I'm going to construct a cube and splitting it into tetrahedrons(if at all possible)!! Else how do I approach this?

P.S.: The variables are dependent

The answer is $\boxed{\frac{81}{208}}$ when $n\to\infty$

$\endgroup$
5
  • $\begingroup$ You can just do some casework: take the sum where all indices are independent, then subtract the extra terms (2 indices the same, or all 3 indices the same) $\endgroup$
    – lc2r43
    Sep 20, 2020 at 16:35
  • $\begingroup$ I tried doing something like that but was really confused about what to add/subtract $\endgroup$
    – DatBoi
    Sep 20, 2020 at 16:36
  • $\begingroup$ If 2 indices the same, then you have a sum of the form $\sum_{i=0}^n\sum_{j=0}^n \frac{1}{3^{2i}3^j}$ (there are 3 pairs like this), if 3 indices the same, you have $\sum_{i=0}^n\frac{1}{3^{3i}}$ $\endgroup$
    – lc2r43
    Sep 20, 2020 at 16:38
  • $\begingroup$ Yes, I understand. But again, which ones should I add/subtract? I couldn't get any clear idea(probably a difficult case of inclusion/exclusion?) $\endgroup$
    – DatBoi
    Sep 20, 2020 at 16:42
  • $\begingroup$ Should this be the limit as $n \to \infty$? $\endgroup$ Sep 21, 2020 at 2:40

2 Answers 2

2
$\begingroup$

The requitred sum is $$S=(\sum_{0k=0}^{\infty} 3^{-k})^3-3 \sum_{i=0}^{\infty} 9^{-i} \sum_{j=0} 3^{-j} +2 \sum_{k=0}^{\infty} 3^{-3k}$$ $$\implies S=\left(\frac{1}{1-1/3}\right)^3-3\frac{1}{1-1/9}.\frac{1}{1-1/3}+2\frac{1}{1-1/27}=\frac{27}{8}-\frac{81}{16}+\frac{27}{13}=\frac{81}{208}$$

You may see my answer in this post for the explanation:

$\sum_i \sum_j \sum_k (1 \le i \le j \le k \le n) ~~f_i f_j f_k $ in terms of $\sum f_i~, \sum f^2 _i ~\mbox{and}~ \sum f^3 _i $

$\endgroup$
5
  • $\begingroup$ Why is the $i=j=k$ sum added twice? $\endgroup$
    – DatBoi
    Sep 20, 2020 at 17:32
  • $\begingroup$ You may see: my answer in math.stackexchange.com/questions/3274832/… $\endgroup$
    – Z Ahmed
    Sep 20, 2020 at 17:40
  • $\begingroup$ It was indeed helpful. So principle of inclusion/exclusion has got nothing to do with this? $\endgroup$
    – DatBoi
    Sep 20, 2020 at 17:51
  • $\begingroup$ No, exclusion/inclusion it is actually there. The first part is the free sum then three sums where two of (i,j,k) are equal are subtracted (excluded). But since in these THREE cases, $i=j=k$ features 3 times. So we have over subtracted 2 times extra. So double of (i=j=k) should be added (included) $\endgroup$
    – Z Ahmed
    Sep 21, 2020 at 4:44
  • $\begingroup$ I see....thanks for the help $\endgroup$
    – DatBoi
    Sep 21, 2020 at 4:46
2
$\begingroup$

I'm going to construct a cube and splitting it into tetrahedrons(if at all possible)!!

It is not necessary to construct a cube. Let $A = \{0,1,2,...,n\}$. The required combinations (which you mentioned in the square) is basically Cartesian product $A×A$. Extending this further $A×A×A = (A×A)×A$. So write down elements of $A×A$ (which you found by your square) in row and elements of $A$ in column. Combine elements in the rectangle to arrive at the required combinations.

EDIT 2.0 (Approach towards solution)

While the given problem can also be solved using Principle of Inclusion and Exclusion, I am going to solve it using the 'square'/'rectangle' method that I have mentioned earlier. Write $\{ (0,0),(0,1),...,(0,n),(1,0),(1,1),...,(1,n),...,(n,0),(n,1),...,(n,n) \}$ in the horizontal direction and $\{ 0,1,2,...,x,...,n \}$ in the vertical direction. This rectangle can be split into squares formed by Cartesian Product of $\{ (x,0),(x,1),...,(x,n) \}$ and $\{0,1,...,n\}$ for $0\leq x \leq n$. This is shown below: Approach

for $i \neq j \neq k$, we have to find for total $-$(minus) yellow portion. Total $=3^{-x} (\sum_{i=o}^n{3^{-i}})^2$ [solve row-wise and add up all the row-wise results to arrive at this result]. Yellow portion = diagonal + (x,x) column + x row - 2(x,x,x)[since I have deducted (x,x,x) 3 times but want it to be deducted only once]. Diagonal $= 3^{-x} \sum_{i=0}^n{3^{-2i}}$. (x,x) Column $= 3^{-2x} \sum_{i=0}^n{3^{-i}}$. x row $= 3^{-2x} \sum_{i=0}^n{3^{-i}} $ .So, Yellow portion $= 3^{-x} \sum_{i=0}^n{3^{-2i}} + 2 \times 3^{-2x} \sum_{i=0}^n{3^{-i}} -2 \times 3^{-3x}$. Therefore required answer is $$\sum_{x=0}^n{(3^{-x} (\sum_{i=o}^n{3^{-i}})^2-3^{-x} \sum_{i=0}^n{3^{-2i}} -2 \times 3^{-2x} \sum_{i=0}^n{3^{-i}} + 2 \times 3^{-3x})}$$ $$= \frac{27}{8}-\frac{27}{16}-2\times \frac{27}{16} + 2\times \frac{27}{26} = \boxed{\frac{81}{208}}$$

Note: We can solve for $i<j<k$ by reducing the original square into a smaller version $\{ (x,x+1),...,(x,n) \} \times \{x+1,...,n\}$ (see the diagram). The logic here is area of green portion = (area of reduced square -(minus) area of diagonal of reduced square)/2

$\endgroup$
7
  • 1
    $\begingroup$ I suppose the symmetry would be a problem... $\endgroup$
    – DatBoi
    Feb 3, 2022 at 17:06
  • $\begingroup$ @DatBoi I made an edit regarding Symmetry. $\endgroup$
    – S Das
    Feb 4, 2022 at 6:23
  • $\begingroup$ I really appreciate your efforts!! It does seem very tedious but I'll try looking for other possible symmetries to exploit! $\endgroup$
    – DatBoi
    Feb 4, 2022 at 6:40
  • $\begingroup$ I found a better symmetry that is why I made another edit. The key is to split rectangles into squares. $\endgroup$
    – S Das
    Feb 4, 2022 at 12:28
  • $\begingroup$ Can you please clarify what $x$ here is? $\endgroup$
    – DatBoi
    Feb 4, 2022 at 13:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .