Surprising Summation (3): $\sum_{i=1}^n\sum_{j=1}^i 2(n-i)+1=\sum_{i=1}^n i^2$ Show that 

$$\sum_{i=1}^n\sum_{j=1}^i 2(n-i)+1=\sum_{i=1}^ni^2$$

without expanding the summation to its closed-form solution, i.e. $\dfrac 16n(n+1)(2n+1)$ or equivalent.
Background as requested:
The summands for both equations are not the same but the results are the same. The challenge here is to transform LHS into RHS without solving the summation. It seems like an interesting challenge. If you like this question, please vote to reopen it!
 A: \begin{array}\\
\sum_{i=1}^n\sum_{j=1}^i (2(n-i)+1)
&=\sum_{j=1}^n\sum_{i=j}^n (2(n-i)+1)
\qquad \text{(switch order of summation)}\\
&=\sum_{j=1}^n\sum_{i=0}^{n-j} (2i+1)
\qquad (i \to n-i)\\
&=\sum_{j=1}^n(n-j+1)^2
\qquad\text{(since }\sum_{j=0}^m (2j+1) = (m+1)^2)\\
&=\sum_{j=1}^n j^2
\qquad (j \to n-j+1)\\
\end{array}
A: $$\sum_{i=1}^{n}\sum_{j=1}^{i}(2(n-i)+1)-\sum_{i=1}^{n}i^2$$
$$=\sum_{i=1}^{n}(2n+1)i-3\sum_{i=1}^{n}i^2$$
$$=(2n+1)\frac n2(n+1)-3\times\frac n6(n+1)(2n+1)=0$$
A: You may use the following (discrete version of $\int x^k\,dx = \frac{x^{k+1}}{k+1}$):

Lemma: if $p(x)$ is a polynomial having degree $k$, then:
  $$ P(n) = \sum_{k=1}^{n}p(k) $$
  is a polynomial with degree $k+1$.

That lemma gives that both sides are third degree polynomials in $n$. If you check that both sides agree for $n=1,2,3,4$, it follows that they are the same polynomial, hence your identity holds for every $n$.
Proof of the lemma: we may write any polynomial in the binomial base, then the well-known identity:
$$ \sum_{k=1}^{n}\binom{k}{r} = \binom{n+1}{r+1} $$
proves the claim.
A: $$\begin{align}
\sum_{i=1}^n\sum_{j=1}^i2(n-i)+1
&=\sum_{i=1}^n\sum_{j=1}^i 2(n-i+1)-1\\
&=\sum_{s=1}^n\sum_{r=s}^n (2s-1)
&& (\text{putting }s=n-i+1\text{ and } r=n-j+1)\\
&=\sum_{r=1}^n\sum_{s=1}^r (2s-1)
&&(1\le s\le r\le n)\\
&=\sum_{r=1}^n\sum_{s=1}^r s^2-(s-1)^2\\
&=\sum_{r=1}^n r^2\qquad\blacksquare
\end{align}$$
