Recently I've been looking at integer sequences that look like exponential at the first few terms but is actual polynomial, like these two sequences [1] [2]. And there seems to be something interesting here.
Suppose we denote $S_m(n)$ to be mth-order polynomial sequence which $S_m(n) = 2^n$ for all non-negative integers up to m. So we have
$S_0(n) = 1$
$S_1(n) = n+1$
$S_2(n) = (n^2+n+2)/2$
$S_3(n) = (n^3+5n+6)/6$
$S_4(n) = (n^4-6n^3+23n^2-18n+24)/24$
And so on. For the first few cases that I've looked at, there seems to be a property that $$S_m(m+1)=2^{m+1} - 1$$
That is, the next term's always off by 1. I'm not sure if it's a general property or just a coincidence; People have been using these sequences to show "patterns in small n may not be legitimate".
Is there any way to prove (or disprove) this, other than the brute-force way of attempting a Gaussian elimination on the equations to find the suitable $S_m(m+1)$ such that the system of equations is solvable? It seems that these sequences have some relationships to combinatorics and binomial expansions (as the explicit form are also written in them, and the denomimator which goes as the factorial), but I'm not familiar with them.
Since $S_m(x)$ is a polynomial of degree $m$ in $x$. Its $(m+1)^{th}$ order finite difference vanishes. i.e
$$\sum_{k=0}^{m+1} (-1)^k \binom{m+1}{k} S_m(m+1-k) = 0$$
This leads to $$\begin{align} S_m(m+1) &= -\sum_{k=1}^{m+1}(-1)^k \binom{m+1}{k} 2^{m+1-k}\\ &= 2^{m+1} - 2^{m+1}\sum_{k=0}^{m+1}\binom{m+1}{k} \left(-\frac12\right)^k\\ &= 2^{m+1} - 2^{m+1}\left(1 - \frac12\right)^{m+1}\\ &= 2^{m+1} - 1 \end{align} $$