$\sum _{r=1}^{p-1}r^{2k}\left(\frac{r}{p}\right)=\sum_{i=1}^{2k-1} c_i(p)\sum _{r=1}^{p-1}r^{2k-i}\left(\frac{r}{p}\right)$

[Analytic Number Theory - Florian Luca and Jean Marie De Koninck, chapter 14, question 14.2]

A series of questions asks to prove the following:-

1. Prove $$\sum _{r=1}^{p-1}r\left(\frac{r}{p}\right)=0$$ for any prime $$p\equiv 1\pmod 4$$.

2. Prove $$\sum _{r=1}^{p-1}r^2\left(\frac{r}{p}\right)=p\sum _{r=1}^{p-1}r\left(\frac{r}{p}\right)$$ for any prime $$p\equiv 3\pmod 4$$.

3. Prove $$\sum _{r=1}^{p-1}r^3\left(\frac{r}{p}\right)=\frac{3p}{2}\sum _{r=1}^{p-1}r^2\left(\frac{r}{p}\right)$$ for any prime $$p\equiv 1\pmod 4$$.

4. Prove $$\sum _{r=1}^{p-1}r^4\left(\frac{r}{p}\right)=2p\sum _{r=1}^{p-1}r^3\left(\frac{r}{p}\right)-p^2\sum_{r=1}^{p-1}r^2\left(\frac rp\right)$$ for any prime $$p\equiv 3\pmod 4$$.

All these exercises can be solved by manipulating the expressions a bit and using the fact that for $$p\equiv 1\pmod 4$$, we have $$\left(\frac{-1}{p}\right)=1$$ and for $$p\equiv 3\pmod 4$$, we have $$\left(\frac{-1}{p}\right)=-1$$.

But, the form in which these are written suggests that there is room for generalizing these equalities. My question is whether any general equation of the following type is true :- $$\sum _{r=1}^{p-1}r^{2k}\left(\frac{r}{p}\right)=\sum_{i=1}^{2k-1} c_i(p)\sum _{r=1}^{p-1}r^{2k-i}\left(\frac{r}{p}\right)$$ for $$p\equiv 3\pmod 4$$, and $$\sum _{r=1}^{p-1}r^{2k-1}\left(\frac{r}{p}\right)=\sum_{i=1}^{2k-2} c^\prime_i(p)\sum _{r=1}^{p-1}r^{2k-1-i}\left(\frac{r}{p}\right)$$ for $$p\equiv 1\pmod 4$$.

It would probably not be very difficult (in terms of ideas, not computation) to prove such an equality if it's already known to be true. But, I can't see how one can derive one without getting their hands a little too dirty.

There do exist such relations. Let $$S_k(p)=\sum_{r=1}^{p-1}r^k(r/p)$$ for notational simplicity.
For $$p\equiv 3\pmod 4$$, we have \begin{align*} S_{2k}(p) &=\frac 12\sum_{r=1}^{p-1}\left(r^{2k}\left(\frac rp\right)+(p-r)^{2k}\left(\frac{p-r}p\right)\right)\\ &=\frac 12\sum_{r=1}^{p-1}\left(r^{2k}-(p-r)^{2k}\right)\left(\frac rp\right)\\ &=\frac 12\sum_{r=1}^{p-1}\left(-\sum_{j=0}^{2k-1}\binom{2k}jp^{2k-j}(-1)^jr^j\right)\left(\frac rp\right)\\ &=-\frac 12\sum_{j=0}^{2k-1}\binom{2k}j(-1)^jp^{2k-j}S_j(p)\\ &=\sum_{j=0}^{2k-1}\left(\frac 12(-1)^{j+1}\binom{2k}jp^{2k-j}\right)S_j(p). \end{align*} For $$p\equiv 1\pmod 4$$, we have \begin{align*} S_{2k-1}(p) &=\frac 12\sum_{r=1}^{p-1}\left(r^{2k-1}\left(\frac rp\right)+(p-r)^{2k-1}\left(\frac{p-r}p\right)\right)\\ &=\frac 12\sum_{r=1}^{p-1}\left(r^{2k}+(p-r)^{2k-1}\right)\left(\frac rp\right)\\ &=\frac 12\sum_{r=1}^{p-1}\left(\sum_{j=0}^{2k-2}\binom{2k-1}jp^{2k-1-j}(-1)^jr^j\right)\left(\frac rp\right)\\ &=\frac 12\sum_{j=0}^{2k-2}\binom{2k-1}jp^{2k-1-j}(-1)^jS_j(p)\\ &=\sum_{j=0}^{2k-2}\left(\frac 12(-1)^j\binom{2k-1}jp^{2k-1-j}\right)S_j(p). \end{align*} In each case, there are many more relations of this form; for $$p\equiv 3\pmod 4$$, say, we may replace any occurrence of $$S_2$$ with $$pS_1$$, for example. This allows us to get the relation in problem part (4) from the above relation for $$k=2$$.