# 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. ${}{}$

-
I"m confused. Is it really supposed to be an $x$ on both sides here? – Zev Chonoles Feb 24 '13 at 13:09
This can't be correct. The right-hand side must depend on $n$, it seems to me. – bubba Feb 24 '13 at 13:13

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*}

-
Thank you very much, this made me understand it. – Energyfellow Feb 24 '13 at 20:42

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*}

-
Can't this be done combinatorially? – Ishan Banerjee Feb 24 '13 at 17:20
@Ishan: Conceivably, but I don’t at the moment see such an argument. – Brian M. Scott Feb 24 '13 at 17:50

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$

-