Question on the correlation between two dependent variables I'm working on this question and it's stumping me.

Let $S_n = X_1 + \ldots + X_n$ (with $n>=1$) be a random walk with $X_1, \ldots, X_n$ be iid RV's.
  $$
E(X_k)=\mu,\,{\rm Var}(X_k)=\sigma^2. 
$$
  Find the covariance of $S_n$ and $S_m$

Can anyone help out? I am trying to use the equation:
$${\rm Cov}[S_n, S_m] = E[S_nS_m] - E[S_n]E[S_m]$$
 but can't quite figure it out.
 A: The trick is to use the bilinearity of the covariance function. For any collection of random variables $X_i$, $i=1,\ldots,n$ and $Y_j$, $j=1,\ldots,m$:
$$
\mathrm{Cov}\left(\sum_{i=1}^n X_i,\sum_{j=1}^m Y_j\right)=\sum_{i=1}^n\sum_{j=1}^m\mathrm{Cov}\left(X_i, Y_j\right).
$$
Now, for your case, since $X_i$, $i=1,\ldots,n$, are independent (i) and identically distributed (id):
1) If $n=m$,
$$
\mathrm{Cov}\left(S_n,S_n\right)=\sum_{i=1}^n\sum_{j=1}^n\mathrm{Cov}\left(X_i, X_j\right)\stackrel{i}{=}\sum_{i=1}^n\mathbb{V}\mathrm{ar}\left(X_i, X_i\right)\stackrel{id}{=}n\sigma^2.
$$
2) If $n<m$,
\begin{align}
\mathrm{Cov}\left(S_n,S_m\right)=&\sum_{i=1}^n\sum_{j=1}^m\mathrm{Cov}\left(X_i, X_j\right)=\sum_{i=1}^n\left[\sum_{j=1}^n\mathrm{Cov}\left(X_i, X_j\right)+\sum_{j=n+1}^m\mathrm{Cov}\left(X_i, X_j\right)\right]\\
\stackrel{i}{=}&\sum_{i=1}^n\left[\sum_{j=1}^n\mathrm{Cov}\left(X_i, X_j\right)+0\right]\stackrel{1)}{=}n\sigma^2.
\end{align}
3) If $n>m$, obviously, $\mathrm{Cov}\left(S_n,S_m\right)=m\sigma^2$.
So a compact way of expressing this result is $\mathrm{Cov}\left(S_n,S_m\right)=\min(n,m)\sigma^2$.
A: For a  direct derivation using ${\rm Cov}[S_n, S_m] = E[S_nS_m] - E[S_n]E[S_m]$
we have
$$E[S_n]E[S_m] = n\mu\cdot m\mu = nm\mu^2$$
and
$$S_nS_m = \left(\sum_{i=1}^n X_i\right)\left(\sum_{i=1}^m X_i\right) = \sum_{i=1}^{\text{min}(m,n)} X_i^2 + \sum_{i\neq j} X_iX_j$$
where the number of terms in $\sum_{i\neq j} X_iX_j$ are $nm-\text{min}(m,n)$. Taking the expected value
$$E[S_nS_m] = \text{min}(m,n)E(X^2) + [nm-\text{min}(m,n)]\mu^2$$
Bringing it all together
$${\rm Cov}[S_n, S_m] = \text{min}(m,n)E(X^2) + [nm-\text{min}(m,n)]\mu^2 - nm\mu^2$$
and cancelling off
$${\rm Cov}[S_n, S_m] = \text{min}(m,n)\cdot\left (E(X^2) -\mu^2\right) = \text{min}(m,n)\cdot\sigma^2$$
