0
$\begingroup$

After applying binomial and multinomial expansions, I get a multiple summation expression in which some summation indices depends on others. I want to find how many terms in such expression (including zero value terms if there are !!!).

E.g., $$\sum_{k=1}^{N}\sum_{i=0}^{k-1}\sum_{j=0}^{2N-k+i}\sum_{l=1}^{M}A_{k}B_{k,i}C_{k,i,j}D_{l,k} $$

Can you please help me to find how many terms in this example?

$\endgroup$
0
$\begingroup$

If you simply want to count the number of terms there will be, replace the sum by \begin{eqnarray*} \sum_{k=1}^{N}\sum_{i=0}^{k-1}\sum_{j=0}^{2N-k+i}\sum_{l=1}^{M}1. \end{eqnarray*} So the $l$ sum will simply factor and give a value of$M$. Now \begin{eqnarray*} \sum_{j=0}^{2N-k+i}1=2N-k+i+1. \end{eqnarray*} The next sum \begin{eqnarray*} \sum_{i=0}^{k-1}2N-k+i-1=(2N-k+1)k-\frac{k(k-1)}{2}. \end{eqnarray*} And the final sum \begin{eqnarray*} \sum_{k=1}^{N}\left((2N-k-1)k-\frac{k(k-1)}{2}\right)=\frac{N(N+1)}{2}(2N+1)-\frac{N(N+1)(2N+1)}{6}-\frac{(N-1)N(N+1)}{6} \end{eqnarray*} This simplifies to $\frac{N(N+1)^2}{2}$. so there will be $\frac{MN(N+1)^2}{2}$ terms generated by this sum. Weather the terms are zero or not will depend on knowing formulae for $A_{k}$,$B_{k,i}$,$C_{k,i,j}$ & $D_{l,k}$.

$\endgroup$
  • $\begingroup$ Great !!! Thanks @Donald $\endgroup$ – Frey Feb 1 '17 at 4:11

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.