Find all polynomials $p$ such that $p(x+1)=p(x)+2x+1.$

Let $p_n = p(n)$, we then have the recurrence $$p_{n+1} = p_n + (2n+1) \implies p_{n+1} - (n+1)^2 = p_n - n^2$$ Hence, we have $$p_n = n^2 + k$$ where $k$ is some constant. Since $p(n) = n^2+k$ at all integer points and the fact that $p(n)$ is a polynomial, we have $p(x) = x^2+k$. This is because we then have $p(x)-x^2-k$ has infinitely many roots and the only polynomial having infinitely many roots is the zero polynomial. Hence, we obtain that $$p(x)=x^2+k$$

Let me try. Put $h(x) = p(x) - x^2$. Then you have $$h(x+1) = h(x)$$, for all $x$. Then, you have $h(x)$ is constant. Let $h(x) = c$, then $p(x) = x^2 + c$.

Hint If $P(x)=a_nx^n+...+a_1x+a_0$ with $a_n \neq 0$ show that $$P(x+1)-P(x)=na_{n-1}x^{n-1}+...$$ has degree $n-1$.

Since in your case $P(X+1)-P(X)=2X+1$ it follows that $P(X)$ is a monic quadratic polynomial.

Writing $P(X)=X^2+ax+b$ and plugging in the equation, you get the answer.