The total number of subarrays I want to count the number of subarrays for a vector (not combinations of elements).
Ex.  
 A[1,2,3]

It has 6 subarrays :
{1}, {2}, {3}, {1,2}, {2,3}, {1,2,3}

I think that for a vector of N elements the total number of subarrays is N*(N+1)/2.
I am not able to prove it, can someone do it?
 A: 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$.
A: 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!
A: Elaborating on Brian's answer, lets assume we count all the single character sub-strings. There can be n such single character sub-string. By using the Binomial Coefficient, $\binom{n}{r}$ notation, we can say n = $\binom{n}{1}$ .
$$ total_1 = n
                                         = \binom{n}{1}$$
Now let's assume we count all the sub-string that are not single character. Because we have to choose the beginning and end of the sub-string regardless of the order, the count should be $\binom{n}{2}$.
$$total_*  = \binom{n}{2}$$
Now the total number of sub-string,
$$total
= total_1 + total_*
= \binom{n}{1} + \binom{n}{2}$$
Now recall Pascal triangle and recurrence relation $$\binom{n+1}{r} = \binom{n}{r} + \binom{n}{r-1}$$. So we can write,
$$total
= total_1 + total_*
= \binom{n}{1} + \binom{n}{2}
= \binom{n+1}{2}
= n(n+1)/2$$
There we have the mathematical deduction. (I kind of feel we do not need the fancy recurrence relation to get the final answer though).
A: 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\;.$$
A: Trying to explain in layman terms.
Let's say f(0) = 0
f(1) = 1
f(2) = 3
f(3) = 6
f(4) = 10
f(5) = 15   

By observation, you can see that each result is just an addition of previous result and current number.
f(n) = n + f(n-1)

So with this formula let's expand f(5).
f(5) 
=> 5 + f(4) 
=> 5 + 4 + f(3) 
=> 5 + 4 + 3 + f(2) 
=> 5 + 4 + 3 + 2 + f(1) 
=> 5 + 4 + 3 + 2 + 1 + f(0)
=> 5 + 4 + 3 + 2 + 1 + 0 
===> This is equal to sum of n numbers = n(n+1)/2

A: Construct and count the number of subarrays of size k, starting with k = 1 and ending at k = N. Consider k as the “size” of a k-element window that scans through the items from left to right. Scanning stops when the right-most element in the window includes the last of N items.
Number each item 1 through N and name each k-element window by the number on the far left of the window. The name of the k-element window then keeps count of the number of k-element subarrays.
k = 1 (Window of size 1)
[1] 2 3 4 5 6 7   
1 [2] 3 4 5 6 7  
...
1 2 3 4 5 6 [7]
So there are 7 subarrays of size 1. 

k = 2 (Window of size 2)
[1 2] 3 4 5 6 7   
1 [2 3] 4 5 6 7  
...
1 2 3 4 5 [6 7] // Notice the left-most element in the window counts the number of k-element subarrays 
So there are 6 subarrays of size 2

k = N (window of size N)
[1 2 3 4 5 6 7]
There is 1 subarray of size N

So the total number of k-element subarrays, for some particular k, must correspond to the k-element window that includes the N’th item (i.e., the window furthest to the right). The name of this window (and therefore the total number of k-element subarrays) is  N-k+1.
Repeat this computation for k = 1, k = 2, … k = N and take the sum of the result. This can be written as a summation: $\sum_{k=1}^{N}N-k+1\ = N + (N-1) + (N-2) + ... + 3 + 2 + 1 = (N+1)(N/2)$.
