Interpolation with a new point of $f'$ Background: 
(Lagrange Interpolation) Let $f\in C^{n+1}([a,b])$ and $x_0,...,x_n\in[a,b]$. If they are different there is a unique $p_n\in\mathcal{P}_n$ such that $p_n(x_i)=f(x_i)$. Also, we have that for each $x\in[a,b]$ exist $\xi_x\in[a,b]$ such that 
$$f(x)-p_n(x)=\dfrac{f^{(n+1)}(\xi_x)}{(n+1)!}W_{n+1}(x)$$
where $W_{n+1}(x)=(x-x_0)(x-x_1).\dots.(x-x_n)$.
Now, we can consider other problem: find $p(x)$ such that $p(x_i)=f(x_i)$ for $i=0,...,n$ and $p'(x_n)=f'(x_n)$. In this case, I can prove that the additional data $p'(x_n)=f'(x_n)$ is equivalent to  interpolate $f$ into one more data, ie, $p\in \mathcal{P}_{n+1}$ and the bound is similar with n+2.
Intuitively, this fact is because the problem is equivalent that the problem: "find $p$ such that $p(x_i)=f(x_i)$ for $i=0,...,n+1$ with $x_{n+1}=x_n +\epsilon$", using that $f'(x_n)\sim \dfrac{f(x_n)-f(x_{n+1})}{\epsilon}$.
This problem can be generalizated (Hermite interpolation) for more $x_j$'s and $f'', f'''$, etc, always in $x_i$ with $i=0,...,n$.
And here is my question: 
Consider the problem: find $p$ such that $p(x_i)=f(x_i)$ for $i=0,...,n$ and $p'(x_{n+1})=f'(x_{n+1})$, where $x_{n+1}\in [a,b]$ is a new point. 
My intuition says that $p\in\mathcal{P}_{n+2}$ because one (new) point in $f'$ can be replaced with two points in $f$, $x_{n+1}-\epsilon$ and $x_{n+1}+\epsilon$. Is this correct? Any proof? 
 A: I’ll assume that $\mathcal P_n$ is the set of all polynomials with real coeffiecients of degree at most $n$. 

find $p$ such that $p(x_i)=f(x_i)$ for $i=0,...,n$ and $p'(x_{n+1})=f'(x_{n+1})$, where $x_{n+1}\in [a,b]$ is a new point. ... My intuition says that $p\in\mathcal{P}_{n+2}$.

Dap’s comment shows how to find such $p\in \mathcal P_{n+2}$, but it is natural to look for such $p\in\mathcal P_{n+1}$. Pick any $p_0\in\mathcal P_{n+1}$ such that $p(x_i)=f(x_i)$ for $i=0,\dots,n$. For instance, we can put as $p_0$ the unique polynomial of $\mathcal P_n$ with this property. Let $p\in\mathcal P_{n+1}$ be any polynomial such that  $p(x_i)=f(x_i)$ for each $i=0,\dots,n$. Then  $(p-p_0)(x_i)=0$ for each $i$, so $(p-p_0)(x)= \lambda W_{n+1}(x)$ for some $\lambda\in\Bbb R$ (we recall that $W_{n+1}(x)=(x-x_0)\dots (x-x_n)$). It remains to choose $\lambda$ to satisfy $p'(x_{n+1})=f'(x_{n+1})$, that is $f'(x_{n+1})-p’_0(x_{n+1})=\lambda W’_{n+1}(x_{n+1})$. If  $W’_{n+1}(x_{n+1})\ne 0$ then there exists a unique such $\lambda$. Otherwise we are lucky if  $ p’_0(x_{n+1})$ already equals $f'(x_{n+1})$ but have to look for a polynomial $p\in\mathcal P_{n+2}$ as is described in Dap’s comment, otherwise.
A: I think that requirements to $f(x)$ is not valuable, because really we have the set of points.
Let us consider the example
$$\quad p(x) = 12\sin \dfrac \pi6\,x\ \text{ for } x\in \{x_0, x_1, x_2\},\quad \text{and}\quad p'(x_3)=1.$$

Last condition can be provided due to "right" choice of value $p(x_3).$
Denote $\mathbf{p(x_3)=t}$ and construct Lagrange interpolatiщn polynomial with
unknown parameter $t.$
Then calculate parameter $t,$ using the
condition to the polynomial derivative in the given point.

The data table is
\begin{vmatrix}
x_0 & p_0 & x_1 & p_1 & x_2 & p_2 & x_3 & p_3 & (p'(x_3))\\
-1 & -6 & 0 & 0 & 1 & 6 & 2 & t & 1\\
\end{vmatrix}
Let us construct Lagrange interpolation polynomial
$$p(x,t) = \dfrac{x(x-1)(x-2)}{(-1)(-1-1)(-1-2)}(-6)
+\dfrac{(x+1)x(x-2)}{(1+1)1(1-2)}6
+\dfrac{(x+1)x(x-1)}{(2+1)2(2-1)}t$$
$$p(x,t) = x(x-1)(x-2)-3(x+1)x(x-2) + (x+1)x(x-1)\dfrac t6,$$
$$p(x,t)=\dfrac t6(x^3-x)+8x-2x^3.$$
The derivative is
$$p'(x,t)=\dfrac t6(3x^2-1)+8-6x^2,$$
$$p'(2,t)=\dfrac{11}6t-16 = 1,$$
so
$$t=\dfrac{102}{11}.$$
This allows to obtain the required polynomial
$$p_3(x)=p\left(x, \dfrac{102}{11}\right)=-\dfrac5{11}x^3+\dfrac{71}{11}x,$$
$$p'_3(x)=-\dfrac{15}{11}x^2+\dfrac{71}{11}.$$
$$p_3(-1)=-6,\quad p_3(0)=0,\quad p_3(1)=6,\quad p'_3(2)=1.$$
Easy to see that one new condition increments required polynomial degree on $1,$
due to the value choice.
This mean that
$$\boxed{p\in\mathcal P_{n+1}}.$$
Remark. Can be used, for example, condition $p(3)=t$ instead $p(x_3)=t.$
A: Let $p_i$ for $i=1,$...$n+1$ be the usual Lagrange polynomial which is zero at each $x_j$ except $x_i$, where it is 1. Then let $q_i$ be given by $p_i(x) (x- x_{n+1})$ for each $i$. Normalize each $q_i$ up to $q_n$ so they are 1 at $x_i$, and $q_{n+1}$ so that it’s derivative at $x_{n+1}$ is 1. Now each of our polynomials has a double root at $x_{n+1}$ except the last one, whose derivative is 1 there. Take now the linear combination $\sum_{i=1}^n a_i q_i + b q_{n+1}$.  So this way we need degree $n+2$. 
Slightly less elegantly we can do it this way: specify out Lagrange polynomials at points $x_1$ through $x_n$ and then at some other point $y$, just so long as as the the polynomial which is 1 at $y$ does not have derivative 0 at $x_{n+1}$. Then taking linearly combinations of these $n+1$ polynomials we see that we can specify the values at $x_1$ through $x_n$ with the first $n$ coefficients, and then by varying the coefficient of that last polynomial we can control the derivative of the linear combination at $x_{n+1}$. 
