The total number of subarrays

Suppose that your vector is $\langle a_1,a_2,\ldots,a_n\rangle$. Imagine a virtual element $a_{n+1}$ at the end; it doesn’t matter what its value is. A subarray is completely determined by the index of its first element and the index of the element that immediately follows its last element. For example, the subarray $\langle a_3,\ldots,a_{n-2}\rangle$ is determined by the indices $3$ and $n-1$, the subarray $\langle a_k\rangle$ is determined by the indices $k$ and $k+1$, and the subarray $\langle a_2,\ldots,a_n\rangle$ is determined by the indices $2$ and $n+1$. Moreover, each pair of distinct indices from the set $\{1,2,\ldots,n+1\}$ uniquely determines a subarray. Thus, the number of subarrays is the number of pairs of distinct indices from the set $\{1,2,\ldots,n+1\}$, which is

$$\binom{n+1}2=\frac{n(n+1)}2\;.$$

Consider an arbitrary array of N DISTINCT ELEMENTS (if the elements are the same then I am afraid the formula you are seeking to prove no longer works!).

Naturally there exists 1 array consisting of all the elements (indexed from 0 to N-1)

There exist 2 arrays consisting of N-1 consecutive elements (indexed from 0 to N-2)

and in general there are k arrays consisting of N-k+1 consecutive elements (indexed from 0 to N-k-1)

Proof:

We can access elements 0 ... N-k-1 as the first array, then 1 ... N-k+2 is the second array, and this goes on for all N-k+r until N-k+r = N-1 (ie until we have hit the end). The r that does us is can be solved for :

$$ N-k+r = N-1 \rightarrow r -k = -1 \rightarrow r = k-1 $$

And the list $$0 ... k-1$$ contains k elements within it

Thus we note that the total count of subarrays is

1 for N elements

2 for N-1 elements

3 for N-2 elements

.

.

.

N for 1 element

And the total sum must be:

$$ 1 + 2 + 3 ... N$$

Let us see if your formula works

if:

$$ 1 + 2 +3 ... N = \frac{1}{2}N(N+1)$$

then

$$ 1 + 2 + 3 ... N+1 = \frac{1}{2}(N+1)(N+2)$$

We verify:

$$ \frac{1}{2}N(N+1) + N+1 = (N+1)(\frac{1}{2}N + 1) = (N+1)\frac{N+2}{2} $$

So you're formula does indeed work! Now we verify that for N = 1

$$ \frac{1*(1+1)}{2} = 1 $$

And therefore we can use the above logic to show that for any and ALL whole numbers N the formula works!

This calculation can be seen as an arithmetic series (i.e. the sum of the terms of an arithmetic sequence).

Assuming the input sequence: $(a_0, a_1, \ldots, a_n)$, we can count all subarrays as follows:

$ \begin{align} \; 1 & \; \text{subarray from} \; a_0 \; \text{to} \; a_{n-1}\\ + \; 1 &\; \text{subarray from} \; a_1 \; \text{to} \; a_{n-1}\\ & \; \ldots \\ + \; 1 & \; \text{subarray from} \; a_{n-1}\; \text{to} \; a_{n-1}\\ = & \; n \end{align} $

$+$

$ \begin{align} \; 1 & \; \text{subarray from} \; a_0 \; \text{to} \; a_{n-2}\\ + \; 1 &\; \text{subarray from} \; a_1 \; \text{to} \; a_{n-2}\\ & \; \ldots \\ + \; 1 & \; \text{subarray from} \; a_{n-2}\; \text{to} \; a_{n-2}\\ = & \; n-1\\ \end{align} $

$+ \; \ldots$

$ \begin{align} \; \; \; 1 & \; \text{subarray only containing} \; a_0\\ = & \; 1\\ \end{align} $

which results in the arithmetic series: $n + n-1 + … + 1$.

The above can also be represented as $\sum_{i=1}^{n}i\;$ and adds up to $n (n+1)/2$.