Nested Summation
I have the following nested sum : $$\sum_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=1}^{j}x = x+1$$
I don't have a clue how to solve this one, can somebody help me?
Thanks in advance. ${}{}$
$\endgroup$ 23 Answers
$\begingroup$I will use the rules found on this page.
First, note that $x$ is not in the base or limit of any of the sums, so it can be "pulled out": $$x\sum_{i=1}^n\sum_{j=1}^i\sum_{k=1}^j 1= x+1$$
Work from inside to outside, simplifying the sum: $$\sum_{k=1}^j 1 = j$$ $$\sum_{j=1}^ij = \frac{i(i+1)}{2}=\frac{1}{2}\cdot\left(i^2 + i\right)$$ $$\sum_{i=1}^n\frac{1}{2}\cdot\left(i^2 + i\right) = \frac{1}{2}\left(\sum_{i=1}^ni^2+\sum_{i=1}^ni\right) = \frac{1}{2}\left(\frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2}\right)$$
Now we're done, and can plug back in:
$$\frac{x}{2}\left(\frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)}{2}\right)=x+1$$
Now, solving for $x$: $$x\left(\frac{n(n+1)(2n+1)}{12} + \frac{n(n+1)}{4} - 1\right)=1$$ $$ \begin{align*} x &= \frac{1}{\left(\frac{n(n+1)(2n+1)}{12} + \frac{n(n+1)}{4} - 1\right)} \\ &= \frac{6}{n^3 + 3 n^2 + 2 n - 6} \end{align*} $$
$\endgroup$ 0 $\begingroup$After a little rearrangement we have
$$\begin{align*} 1+\frac1x&=\sum_{i=1}^n\sum_{j=1}^i\sum_{k=1}^j1\\ &=\sum_{i=1}^n\sum_{j=1}^ij\\ &=\sum_{1=1}^n\frac{i(i+1)}2\\ &=\frac12\left(\sum_{i=1}^ni^2+\sum_{i=1}^ni\right)\\ &=\frac12\left(\frac{n(n+1)(2n+1)}6+\frac{n(n+1)}2\right)\\ &=\frac1{12}\Big(n(n+1)(2n+1)+3n(n+1)\Big)\\ &=\frac{n(n+1)}{12}(2n+4)\\ &=\frac16n(n+1)(n+2)\\ &=\binom{n+2}3\;, \end{align*}$$
so
$$\begin{align*} x&=\frac1{\binom{n+2}3-1}\\ &=\frac6{n(n+1)(n+2)-6}\\ &=\frac6{n^3+3n^2+2n-6}\\ &=\frac6{(n-1)(n^2+4n+6)}\;. \end{align*}$$
$\endgroup$ 2 $\begingroup$This question can be solved in a different way. Your equation is equivalent to $1+\frac1x=\sum_{(i,j,k)\in A}1=|A|$
Where $A={(i,j,k)| 1\leq k \leq j\leq i\leq n }$
So,$|A|= ^nC_3 +2^nC_2+^nC_1$ This is because, we can choose 3 distinct i,j,k or distinct i with the same j and k, or distinct k with the same i and j, or i=j=k.
So we get $1+\frac1x=^nC_3 +2^nC_2+^nC_1=^{n+2}C_3$
$\endgroup$
