determining the formula of equations similar to ${2}^{x-1}$

Question

the formula for
$1,2,3,4,5,6,7\space\text{is}\space{x}\\ 1,2,4,7,11,16,22,29\space\text{is}\space\frac{x\left(x-1\right)+2}{2}\\ 1,2,4,8,15,26,42,64,93\space\text{is}\space\frac{x\left(x\left(x-3\right)+8\right)}{6}\\ 1,2,4,8,16,31,57,99,163,256\space\text{is}\space\frac{x\left(x\left(x\left(x-6\right)+23\right)-18\right)+24}{24}\\ 1,2,4,8,16,32,63,120,219,382,638\space\text{is}\space\frac{x\left(x\left(x\left(x\left(x-10\right)+55\right)-110\right)+184\right)}{120}\\ 1,2,4,8,16,32,64,127,247,466,848,1486\space\text{is}\space\frac{x\left(x\left(x\left(x\left(x\left(x-15\right)+115\right)-405\right)+964\right)-660\right)+720}{720}\\ \text{is there a way to calculate the formula of these sequences easily?}$

Answer 1

You haven't said what these sequences are, but it looks to me like they are (up to some reindexing) the unique polynomials $P_n(x)$ of degree $n$ with the property that $P_n(k) = 2^k$ for the integers $0 \le k \le n$. These have closed form

$$P_n(x) = \sum_{i=0}^n {x \choose i}$$

which is not hard to prove using the calculus of finite differences, or just by computing that $P_n(k) = 2^k$ for $0 \le k \le n$ and arguing that this (together with the degree condition) uniquely determines $P_n(x)$.

Answer 2

To any finite sequence of integers $(a_1,\cdots,a_n)$, you can associate a polynomial $P(x)$ such that $P(i) = a_i$. This has nothing to do with the fact that your first few values are of the form $f(x) = 2^{x-1}$. The formula is $$ P(x) = \sum_{j=1}^n a_j \left( \underset{i \neq i}{\prod_{j=1}^n} \frac{x-i}{j-i} \right). $$ This is the Lagrange polynomial associated to the sequence of pairs $((1,a_1), \cdots, (n,a_n))$. It's easy to see that $P(k) = a_k$; you just have to notice that in this sum from $1$ to $n$, if $1 \le k \le n$ satisfies $k \neq j$, then one of the linear terms on the top of the form $x-i$ will vanish when $k=i$, so the whole term will disappear. The only term left will be $\underset{i \neq i}{\prod_{j=1}^n} a_j\frac{x-i}{j-i}$ evaluated at $x=j=k$, and in this case the whole term reduces to $a_j$.

A simpler way to write this is to express it in terms of the Lagrange basis polynomials: $$ \ell_j(x) = \underset{j \neq i}{\prod_{i=1}^n} \frac{x-i}{j-i} $$ and write $P(x) = \sum_{j=1}^n a_j \ell_j(x)$. These polynomial functions satisfy $$ \ell_j(i) = \delta_{ij} = \left\{ \begin{matrix} 1 & \text{ if } i = j \\ 0 & \text{ if not} \end{matrix} \right. $$ which is what makes them special. We can then see that $P(i) = \sum_{j=1}^n a_j \delta_{ij} = a_i$.

There is not even anything special about the choice of $1,\cdots,n$ for the initial sequence. You could have chosen $n$ arbitrary pairs $((x_1,a_1), \cdots, (x_n,a_n))$ and consider again the Lagrange basis polynomials $$ \ell_j(x) = \underset{j \neq i}{\prod_{i=1}^n} \frac{x-x_i}{x_j-x_i} $$ and then the polynomial $P(x) = \sum_{j=1}^n a_j \ell_j(x)$ satisfies $P(x_i) = a_i$ for $i=1,\cdots,n$; this follows from the fact that $\ell_j(x_i) = \delta_{ij}$, so $P(x_i) = \sum_{j=1}^n a_j \delta_{ij} = a_i$.

This entire process is called polynomial interpolation.

Hope that helps,