Why is the polynomial of an LFSR called so? As far as I understand, the "polynomial" of the LFSR tells us the positions of the register where taps are situated.

However, the natural way to look at the positions would be to think of them as $x_1, x_2, x_3,\cdots$. But we instead identify them as powers of something and call them $x, x^2, x^3, \cdots$

My question is, what are they powers of? And why do we add a 1 to the polynomial?
The polynomial $X^i$ is a delay operator, so formally $X^i(s_t)=s_{t-i}$.

It's also a linear operator so $X^i(a s_t)=a s_{t-i}$.

Let's apply this to the following simple LFSR in Fibonacci configuration


At each clock cycle, a new state $s_t$ is computed from delayed states $s_{t-1}$ and $s_{t-3}$, as $s_t=s_{t-1}+s_{t-3}$. That recurrence can be rewritten as $s_{t-3}+s_{t-1}-s_t=0$, and represented as the polynomial $X^3+X-1=0$ (the $1$ is a shorthand for $X^0$).  In binary, both $+$ and $-$ are eXlusive-OR $\oplus$ and we write the polynomial modulo 2, as $X^3+X+1.$ 

Moreover, not only is there a one to one correspondence between recurrences (equivalently LFSRs) and polynomials, but the roots of the polynomial feature in the solutions, i.e., the sequence generated.