Symmetry relation for finite sums of generalized harmonic numbers EDITs
- extension to alternating sums (6)
- extension to general sums with parameter $x$ (8)
- extension to general sums with two parameters (11)
Extended post
The relation
$$\sum _{k=1}^{n } \left(\frac{H_k^{(p)}}{k^q}+\frac{H_k^{(q)}}{k^p}\right)=H_n^{(p)} H_n^{(q)}+H_n^{(p+q)}\tag{1}$$ 
where $H_k^{(p)} = \sum_{j=1}^k j^{-p}$, is a nice and important symmetry relation with various applications. Notice the finite upper index $n$. The proof is not hard.
Corollary 1
If $q = p$ the relation simplifies to
$$\sum _{k=1}^n \frac{H_k^{(p)}}{k^p}= \frac{1}{2}\left(  (H_n^{(p)})^2+H_n^{(2p)}  \right)\tag{2}$$ 
Corollary 2
In the limit $n \to \infty$ (1)  turns into
$$\sum _{k=1}^{\infty } \left( \frac{H_k^{(p)}}{k^q}+\frac{H_k^{(q)}}{k^p}\right)=\zeta(p)\zeta(q)+ \zeta(p+q)\tag{3}$$ 
where 
$$\zeta(s) = \lim_{n\to \infty } \, H_n^{(s)}=\sum_{k=1}^\infty k^{-s}\tag{3a}$$ 
is the Riemann zeta function.
For $q=p$ formula (3) gives the analogue to (2)
$$\sum _{k=1}^{\infty } \frac{H_k^{(p)}}{k^p}=\frac{1}{2}\left(\zeta(p)^2+ \zeta(2p)\right)\tag{4}$$ 
This formula was also given in [1], and there it was claimed that it is valid for real $p$.
Alternating sums
A similar relation can be derived for alternating sums.
Define
$$A_n^{(p)}= \sum_{k=1}^n (-1)^k \frac{1}{k^p}\tag{5}$$
then the basic relation is
$$\sum _{k=1}^{n} (-1)^k \frac{H_k^{(p)}}{k^q} +\sum _{k=1}^{n} \frac{A_k^{(q)}}{k^p} = H_n^{(p)} A_n^{(q)}+A_n^{(p+q)}\tag{6}$$ 
From (6) other corollaries and formulas can be derived in a manner similar to the one for the non-alternating sums described above.
Generalized relation with parameter $x$
It can be shown with similar methods as before that a more general relation holds from which the two formulas discussed before are special cases.
Let 
$$H_n^{(p)}(x) = \sum_{k=1}^n \frac{x^k}{k^p}\tag{7}$$
$H_n^{(p)}$ is understood as $H_n^{(p)}(+1)$ and we have $H_n^{(p)}(-1)=A_n^{(p)}$ (c.f. (5)).
Then the relation is
$$\sum_{k=1}^n \left(x^k \frac{H_k^ {(p)}(1)}{k^q} + \frac{H_k^{(q)}(x)}{k^p}\right)=H_n^{(p)}(1)H_n^{(q)}(x)+ H_n^{(p+q)}(x)\tag{8}$$
Notice that this relation has lost the symmetry.
For $x=1$ and $x=-1$ we recover the relations (1) and (6), respectively.
In the limit $n\to\infty$ we encounter on the right hand side the polylog function
$$\lim_{n\to\infty}\,  H_n^{(p)}(x)=\sum_{k=1}^\infty \frac{x^k}{k^p} = Li_p(x)\tag{9}$$
so that we have
$$\sum_{k=1}^{\infty} \left(x^k \frac{H_k^ {(p)}(1)}{k^q} + \frac{H_k^{(q)}(x)}{k^p}\right)=Li_p(1)Li_q(x)+ Li_{p+q}(x)\tag{10}$$
Note "added in proof"
The special case $x=-1$ of relation (10) can be uncovered (it is there more or less conceiled) from [2], page 33, where it is called "shuffle relation". We now have here an elementary proof of a generalization it.
Generalized relation with two parameters $x$ and $y$
We can even go one final step further and write down this two-parametric symmetry relation
$$\sum_{k=1}^n \frac{x^k}{k^q}\sum_{m=1}^k \frac{y^m}{m^p} + \sum_{k=1}^n \frac{y^k}{k^p}\sum_{m=1}^k \frac{x^m}{m^q}=\left( \sum_{k=1}^n \frac{x^k}{k^q}\right)\left( \sum_{k=1}^n \frac{y^k}{k^p}\right)+ \sum_{k=1}^n \frac{(x y)^k}{k^{p+q}}\tag{11}$$
This relation includes the various cases of alternating and non-alternating sums for apropriate choices of $x$ and $y$. 
In the limit $n\to\infty$ we obtain
$$\sum_{k=1}^\infty \frac{x^k}{k^q}\sum_{m=1}^k \frac{y^m}{m^p} + \sum_{k=1}^\infty \frac{y^k}{k^p}\sum_{m=1}^k \frac{x^m}{m^q}=\text{Li}_q(x) \text{Li}_p(y)+ \text{Li}_{p+q}(x y)\tag{12}$$
The zeta functions of (3) have been generalized to polylog functions.
Question
Prove (1), (6), (8), (11) and (12)
References
[1] Identities For Generalized Harmonic Number 
[2] http://algo.inria.fr/flajolet/Publications/FlSa98.pdf
 A: To prove (1) I will use summation by parts in the form given by 
$$\sum_{k = 1}^n f_k g_k = f_n G_n - \sum_{k = 1}^{n - 1} G_k (f_{k + 1} - f_k), \quad \text{where} \quad G_n = \sum_{k = 1}^n g_k.$$
Now consider the sum
$$\sum_{k = 1}^n \frac{H_k^{(p)}}{k^q}.$$
Let $f_k = H_k^{(p)}$ and $g_k = 1/k^q$. So
$$G_n = \sum_{k = 1}^n \frac{1}{k^q} = H^{(q)}_n,$$
and
$$f_{k + 1} - f_k = H^{(p)}_{k + 1} - H^{(p)}_k = \left (H^{(p)}_k + \frac{1}{(k + 1)^p} \right ) - H^{(p)}_k = \frac{1}{(k + 1)^p},$$
where we have made use of the following result for the generalised harmonic numbers
$$H^{(a)}_{n + 1} = H^{(a)}_n + \frac{1}{(n + 1)^a}.$$
On applying the summation by parts result to our sum we have
$$\sum_{k = 1}^n \frac{H^{(p)}_k}{k^q} = H^{(p)}_n H^{(q)}_n - \sum_{k = 1}^{n - 1} \frac{H^{(q)}_k}{(k + 1)^p}.$$
Shifting the index is the sum appearing to the right gives
\begin{align*}
\sum_{k = 1}^n \frac{H^{(p)}_k}{k^q} &= H^{(p)}_n H^{(q)}_n - \sum_{k = 2}^{n} \frac{H^{(q)}_{k - 1}}{k^p}\\\
&= H^{(p)}_n H^{(q)}_n - \sum_{k = 2}^{n} \frac{1}{k^p} \left (H^{(q)}_k - \frac{1}{k^q} \right )\\
&= H^{(p)}_n H^{(q)}_n - \sum_{k = 2}^{n} \frac{H^{(q)}_k}{k^p} + \sum_{k = 2}^n \frac{1}{k^{p+q}}\\
&= H^{(p)}_n H^{(q)}_n - \sum_{k = 1}^{n} \frac{H^{(q)}_k}{k^p} + \sum_{k = 1}^n \frac{1}{k^{p+q}}\\
&= H^{(p)}_n H^{(q)}_n - \sum_{k = 1}^{n} \frac{H^{(q)}_k}{k^p} + H^{p + q)}_n
\end{align*}
or after arranging
$$\sum_{k = 1}^n \left (\frac{H^{(p)}_k}{k^q} + \frac{H^{(q)}}{k^p} \right ) = H^{(p)}_n \cdot H^{(q)}_n + H^{(p + q)}_n,$$
as required to show. 
The result given by (6) can be proved in a similar fashion as to what was done above using summation by parts. 
A: Proof
@omegadot has given a proof using partial summation. My proof is based on interchanging the order of summation.
Starting with $\sum_{k=1}^n \frac{H_k^{(p)}}{k^q}$, then inserting the definition $H_k^{(p)} = \sum_{i=1}^k \frac{1}{i^p}$ we arrive at a double sum in which we $\color{red}{\text{interchange the order of summation}}$ (notice the change in the ranges of the indices), $\color{violet}{\text{complete the sum (and subtract the correction)}}$, and $\color{blue}{\text{shift an index}}$ as follows
$$\sum_{k=1}^n \frac{H_k^{(p)}}{k^q}=\color{red}{\sum_{k=1}^n \sum_{i=1}^k \frac{1}{k^q}\frac{1}{i^p} = \sum_{i=1}^n   \sum_{k=i}^n \frac{1}{i^p}\frac{1}{k^q}}
= \left( \sum_{i=1}^n \frac{1}{i^p}\right)\color{violet}{\left(\sum_{k=1}^n \frac{1}{k^q} - \sum_{k=1}^{i-1}  \frac{1}{k^q}
\right)}
=\left( \sum_{i=1}^n \frac{1}{i^p}\right)\left(\sum_{k=1}^n \frac{1}{k^q} \color{blue}{- \sum_{k=1}^{i}  \frac{1}{k^q}+\frac{1}{i^q}}
\right)
=\left(\sum_{i=1}^n \frac{1}{i^p}\right)\left(\sum_{k=1}^n \frac{1}{k^q}  
\right)
- \sum_{i=1}^n \frac{H_i^{(q)}}{i^p}+\sum_{i=1}^n \frac{1}{i^q i^p}
= H_n^{(p)} H_n^{(q)} + H_n^{(p+q)} - \sum_{i=1}^n \frac{H_i^{(q)}}{i^p}
\tag{s1}$$
Rearranging gives (1). QED.
The proof can easily be extended to (6).
Generalization and visualization
The general version of the symmetry relation is
$$\sum_{k=1}^n a_k \sum_{i=1}^k b_i + \sum_{i=1}^n b_i \sum_{k=1}^i a_k= (\sum_{k=1}^n a_k)(\sum_{i=1}^n b_i)+ \sum_{k=1}^n a_k b_k\tag{s2}$$
The basic interchange rule 
$$\sum_{k=1}^n a_k \sum_{i=1}^k b_i=\sum_{i=1}^n b_k \sum_{k=i}^n a_k\tag{s3} $$
can be illustrated as follows.
The left hand side of (s3) can be written as 
$$\begin{array}\\
&a_1(b_1)\\
+&a_2(b_1+b_2)\\
+&a_3(b_1+b_2+b_3)\\
+&...\\
+&a_n(b_1+b_2+b_3+...+b_n)
\end{array}$$
Summing vertically gives 
$$\begin{array}\\
&b_1(a_1+a_2+a_3+...+a_n)\\
+&b_2(\;\;\;\;   +\;a_2+ a_3+...+a_n)\\
+&b_3(\;\;\;\;\;\;\;\;\;\;\;\;+\; a_3+...+a_n)\\
+&...\\
+&b_n(\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;+ a_n)
\end{array}$$
which is the right hand side of (s3). done.
