# Summation of this series.

I wanted to compute the total length of the substrings of a string for a coding problem I am attempting.

i.e For $input = abcd$ then then required answer would be $4 + 6 + 6 + 4$ i.e) $abcd + abc + bcd + ab + bc + cd + a + b + c + d$

The total length of substrings where length of the string is $n$ would be

$\sum_{r=1}^{n/2} r * 2 * nCr$ where n is even and

$\sum_{r=1}^{n/2} r * 2 * nCr$ plus addition term $n/2 * nCr$ where n is odd

I can brute force this an compute it but that would increase the time complexity of the solution.

Could you please help me convert this summation formula to a single equation that can be computed in constant time.

• Noting that $$r{n\choose r}=n{n-1\choose r-1}$$ and the symmetry $${n\choose k}={n\choose n-k}$$ together with the identities $$\sum_{k=0}^n{n\choose k}=2^n$$ trivializes this rather drastically, no?
– Did
May 6, 2018 at 12:26
• For $n=4$, I get $\sum_{r=1}^{n/2}r*2*nCr=1*2*4+2*2*6=32\not=20=4+6+6+4$. So how do the formulas relate to the example? May 6, 2018 at 13:07
• @BarryCipra Yes, you are right. The equation is wrong. Turns out the problems doesn't involve combinations at all. May 6, 2018 at 15:42

Let $n$ be the length of the string and $k$ be a possible length of a substring, so $1\leq k\leq n$. Now the first $n-k+1$ places of the string could be the start of the substring, because you need at least $k-1$ places for the rest of the substring. So there are exactly $n-k+1$ substrings of length $k$, their combined length being $k(n-k+1)$
So if we sum over all possible substring lengths, we get $$S(n)=\sum_{k=1}^n k(n-k+1)=(n+1)\sum_{k=1}^n k - \sum_{k=1}^n k^2 = \frac{n(n+1)^2}{2}-\frac{n(n+1)(2n+1)}{6}$$
I'm sure you can simplify the right hand side yourself. (We really have $S(4)=20$.) The problem is easier than you anticipated, but I'm afraid you cannot calculate it in "constant time", as $S(n)\in\mathcal{O}(n^3)$, but in a line of code? Sure.