Showing ${\sum_{i=0}^n (2i+1)}=(n+1)^2$ (and generally simplifying $\sum P(i)$ for polynomial $P$) Asking WolframAlpha to solve $\displaystyle{\sum_{i=0}^n (2i+1)}$ the answer is $(n+1)^2$.
I wonder if there is a way to prove it or, more generally, which general strategy should be used to compute $\displaystyle{\sum_{i=0}^n P(i)}$ for some given polynomial $P(i)$.
Is it enough linearity and Gauss' identity
$$\displaystyle \sum_{i=0}^n i = \frac{n(n+1)}{2} $$
 A: As said in the comments,
$$ \sum_{i=0}^n (2i+1)=2\sum_{i=0}^n i+\sum_{i=0}^n1 = n(n+1)+n+1=(n+1)^2 $$
There is a general formula for $\sum_{i=0}^n i^k$ which is Faulhaber's formula :
$$ \sum_{i=0}^n i^k=\frac{1}{k+1}\sum_{j=0}^k\binom{k+1}{j}B_jn^{k+1-j} $$
where $B_j$ is the $j$-th Bernoulli number. Since for any polynomial $P\neq 0$,
$$ P(x)=\sum_{k=0}^{\deg P}\frac{P^{(k)}(0)}{k!}x^k $$
we have
$$ \sum_{i=0}^n P(i)=\sum_{k=0}^{\deg P}\frac{P^{(k)}(0)}{(k+1)!}\sum_{j=0}^k\binom{k+1}{j}B_jn^{k+1-j} $$
I'm not sure it is any easier in the end, or even useful.
However, what you can do in practice is to decompose the sum :
$$ \sum_{i=0}^n P(i)=a_p\sum_{i=0}^n i^p+\ldots+a_0\sum_{i=0}^n 1 $$
for $P=\sum_{i=0}^p a_iX^i$, then you compute $\sum_{i=0}^p i^k$ for all $k\leqslant p$ hoping it is not too boring (it is not for small values of $k$). In order to do this, you can say that
$$ \int_i^{i+1}x^k dx=\frac{(i+1)^{k+1}-i^{k+1}}{k+1}=i^k+Q(i) ​$$
where $Q$ is a polynomial of degree at most $k-1$, therefore
$$ \sum_{i=0}^n i^k=\int_0^{n+1}x^kdx-\sum_{i=0}^n Q(i)=\frac{(n+1)^{k+1}-1}{k+1}-\sum_{i=0}^n Q(i) $$
and you can compute the last sum using the expression you've found for $\sum_{i=0}^n 1,\ldots,\sum_{i=0}^n i^{k-1}$. This way, you can successively compute $\sum_{i=0}^n i^2$, $\sum_{i=0}^n i^3$,etc...
