I have just started to read something about interpolation problem, and in a book it is written:
Interpolation problem. Given $n+1$ points $(x_i,y_i)$ we look for a polynomial of degree $n$ passing through all these points...
Then come some examples and some history of this problem.
I have several questions about this problem that can, hopefully, be answered in one single answer.
First, why the number of points is $n+1$ and not $n+k$ for some $k \in \mathbb Z \setminus \{1\}$. I am taking a guess that it has something to do with invertibility of Vandermonde matrix obtained when converting system of equations in vector-matrix form, but, I would like to have a simple geometricoanalytical explanation of why the number of points is required to be $n+1$ (i am thinking also about fundamental theorem of algebra).
Next, when we know why $n+1$ points are required through which a polynomial passes then how to show, with as easy as possible arguments, that such a polynomial will really exist for every choice of $n+1$ points in the plane (uniqueness is easily shown).
And finally, are there some generalizations of this theorem about interpolating polynomial?
For the existence question, the shortest answer is that you can explicitly construct the desired polynomial. Once you know the construction, it's just a matter of plugging in the $x$-values and seeing that you get the right $y$-values. I'm not aware of any straightforward nonconstructive existence proof.
Re: generalizations: Yes there are generalizations, but there are also fairly strong impossibility results. Because of this, the theory gets considerably more involved. You can read more about it in these lecture notes.
On the significance of $k=1$: Your guess about Vandermonde will definitely work. But it sounds like you wanted some more simple description; perhaps you will find this satisfying.
If you try to keep your polynomial of degree at most $n$ while fitting $n+2$ or more points, you'll generally fail because the polynomial cannot oscillate fast enough. For instance, you know that a non-constant polynomial of degree at most $n$ can have at most $n-1$ minima and maxima. But if you choose the indexing of the points so that $x_1<x_2<\cdots< x_{n+2}$ and then pick $y$-values which "oscillate" i.e. $y_1\geq y_2\leq y_3\geq \cdots \leq y_{n+2}$ (or $\geq y_n$ depending on the parity of $y_n$), then you can see visually that this would require the polynomial to have at least $n$ mins/maxs.
(For other patterns of inequalities among the $y_i$, the issue is more subtle. But this at least shows that you can't expect to interpolate between arbitary $n+2$ points.)
If your polynomial has degree $n$ but you are fitting $n$ points (or fewer), then the existence question (discussed below) implies that uniqueness is impossible. Attempting to start the uniqueness proof, suppose that $f(x_i)=g(x_i)=y_i$ for all $i$, and $f,g$ have degree $n$. Then $f-g$ has degree at most $n$ and has roots at each $x_i$. To complete uniqueness, you're supposed to show that $f=g$, i.e. $f-g=0$ everywhere— but that's simply not true; it could be that, e.g. $$f(x)-g(x)= (x-x_1)(x-x_2)\cdots(x-x_n).$$