Generalizing observations made from the sequence $1,2,4,8,16,31,57,99,...$

Question

Generalizing observations made from the sequence $1,2,4,8,16,31,57,99,...$

The first differences between the terms are:

$1,2,4,8,15,26,42...$

The second differences (the differences between the differences) are:

$1,2,4,7,11,16...$

The third differences (the differences between the second differences are):

$1,2,3,4,5...$

the Oeis sequence database gave the $n'th$ term of this sequence by:

$a_n=\Sigma_{k=0}^4$${n-1}\choose{k}$

This got me thinking, it seems that a sequence can be uniquely defined by it's initial value and the value of it's $n'th$ differences. And so, my question is this: Given a sequence with initial value $1$ and whose $n'th$ differences are given by $1,2,3,4,5,6,7.....$, can the $n'th$ term of this sequence be related to the binomial coefficients? Is there any other insight's that can clarify what's going on here?

Answer 1

Claim $1$

Let $A(m, n)$ denote the number of regions in $\mathbb{R}^{m}$ formed by $n$ hyperplanes. For a sequence whose $(m-1)$th differences are $1,2,3,4,5...$, the $n$th term of the sequence is given by $A(m, n-1)$.

Connecting the dots

Let $T_{m, n}$ denote the $n$th term of a sequence whose $(m-1)$th differences are $1,2,3,4,5,...$.

This answer demonstrates that

$$A(m, n-1) = \sum_{k=0}^{m} {n-1 \choose k}$$

Hence, if we can prove Claim $1$, i.e. $T_{m, n} = A(m, n-1)$, we are done.

An attempt to prove Claim $1$

Note that $$A(m, n) = A(m, n-1) + A(m-1, n-1) \iff A(m,n) - A(m, n-1) = A(m-1, n-1)$$

(Proof here)

If Claim $1$ is true, it follows that $$T_{m, n} = A(m, n-1) \implies T_{m, n+1} = A(m, n)$$ $$T_{m, n+1} - T_{m, n} = A(m, n) - A(m, n-1) = A(m-1, n-1) \tag{1}$$

I have been unable to prove $(1)$, i.e. the difference between the $(n+1)$th and $n$th terms of a sequence whose $(m-1)$th differences are $1,2,3,4,5...$ is the same as the number of regions formed by $n-1$ hyperplanes in $\mathbb{R}^{m-1}$. If someone is able to demonstrate this, however, the proof is complete.

Edit: Claim $1$ has been proven here.

Answer 2

Yes, given a sequence with $k$th differences being $1,2,3,...$ we can always find a polynomial of degree $k+1$ that satisfies the sequence. To show this, let $f_0(n)$ be the original sequence, $f_1(n)=f_0(n+1)-f_0(n)$ be the first difference sequence, and in general

$$f_m(n)=f_{m-1}(n+1)-f_{m-1}(n)$$

be the $m$th difference sequence. To prove the $f_0(n)$ is some $k+1$ degree polynomial, we will use backwards induction. That is, we will start with the base case of $f_k(n)$, and work backwards to $f_0(n)$. In general, we will show that $f_m(n)$ is described by a $k+1-m$ degree polynomial.

Base Case: Obviously we have

$$f_k(n)=n$$

which has degree $1=k+1-k$.

Induction Step: Assume that $f_{m}(n)$ is some polynomial of degree $k+1-m$

$$f_m(n)=\sum_{i=0}^{k+1-m}a_i n^i$$

where $a_{k+1-m}\neq 0$. Then

$$f_m(n-1)=f_{m-1}(n)-f_{m-1}(n-1)$$

$$\vdots$$

$$f_m(0)=f_{m-1}(1)-f_{m-1}(0)$$

This implies

$$f_{m-1}(n)=\sum_{i=0}^{n-1}f_m(i)-f_{m-1}(0)=-f_{m-1}(0)+\sum_{j=0}^{n-1}\sum_{i=0}^{k+1-m}a_i j^i$$

Changing the order of sums gives us

$$=-f_{m-1}(0)+\sum_{i=0}^{k+1-m}a_i\sum_{j=0}^{n-1}j^i$$

It is well known that

$$\sum_{j=0}^{n-1}j^i=\sum_{r=1}^{i+1}b_rn^{r}=b_{i+1}n^{i+1}+\sum_{r=1}^{i}b_rn^{r}$$

where $b_{i+1}\neq 0$. But then this gives us

$$-f_{m-1}(0)+\sum_{i=0}^{k+1-m}a_i\sum_{j=0}^{n-1}j^i$$

$$=-f_{m-1}(0)+\sum_{i=0}^{k+1-m}a_i\left[b_{i+1}n^{i+1}+\sum_{r=1}^{i}b_rn^{r} \right]$$

$$=a_{k+1-m}b_{k+1-(m-1)}n^{k+1-(m-1)}+\sum_{i=0}^{k+1-m}c_i n^i$$

where $a_{k+1-m}b_{k+1-(m-1)}\neq 0$. Since this is a polynomial of degree $k+2-m=k+1-(m-1)=$ we are done.

Answer 3

Denoting the (forward) difference as $$\Delta \,a_n = a_{n + 1} - a_n$$ and its iteration as $$\Delta ^m \,a_n = \Delta \left( {\Delta ^{m - 1} \,a_n } \right)$$ then the general solution to the equation $\Delta ^m \,a_n = 0$ is $$ \Delta ^m \,a_n = 0\quad \Leftrightarrow \quad a_n = c_0 n^{\,\underline {0\,} } + c_1 n^{\,\underline {1\,} } + \cdots + c_{m - 1} n^{\,\underline {m - 1\,} } $$ where:

• the $c$'s are undetermined constants,
• $x^{\,\underline {\,k\,} } $ represents the Falling Factorial.

You need $q $ (independent) initial conditions to fix the constants and obtain a unique sequence.

Now consider that $$ \begin{array}{l} \Delta \;n^{\,\underline {\,q\,} } = \left( {n + 1} \right)^{\,\underline {\,q\,} } - n^{\,\underline {\,q\,} } = qn^{\,\underline {\,q - 1\,} } \\ n^{\,\underline {q\,} } = n\left( {n - 1} \right) \cdots \left( {n - q + 1} \right) = q!\left( \begin{array}{c} n \\ q \\ \end{array} \right) = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,q} \right)} {\left( { - 1} \right)^{\,q - k} \left[ \begin{array}{l} q \\ k \\ \end{array} \right]x^{\,k} } \\ \end{array} $$ so the solution is actually a polynomial of degree $(m-1)$.