Finding out nth term of a sequence by method of diference

Question

Let us consider $$S_n=t_1+t_2+...+t_n$$ and let $∆_{t_1}=t_2-t_1,∆_{t_2}=t_3-t_2,...,∆_{t_{n-1}}=t_n-t_{n-1}$ be the first order difference.

Similarly $∆^2_{t_1}=∆_{t_2}-∆_{t_1},...∆^2_{t_{n-2}}=∆_{t_{n-1}}-∆_{t_{n-2}}$ be the second other difference.

Similarly we calculate $∆^{n-1}_{t_1}$ .

The question is to prove that $$t_n=t_1+\binom{n-1}{1} ∆_{t_1}+\binom{n-1}{2}∆^2_{t_1}+...+∆^{n-1}_{t_1}$$

I tried to verify it for simple cases and tried to proof via induction but couldn't proceed.Any ideas?

Answer 1

You can prove it by induction but it won't be very much fun. Here's a much cleaner proof.

Consider the shift operator $S$, which takes as input a sequence $t_n$ and returns as output a new sequence

$$(St)_n = t_{n+1}.$$

The shift operator can be used to write down the forward difference operator

$$(\Delta t)_n = t_{n+1} - t_n = \left( (S - 1) t \right)_n$$

where $1$ denotes the identity operator, which sends a sequence $t_n$ to $t_n$, and $S - 1$ is the sum of operators. The key to the approach I'm about to describe is that it is possible to perform algebra on operators: you can add them by adding them pointwise, and multiply them by composing them. For example, the second difference is

$$(\Delta^2 t)_n = (t_{n+2} - t_{n+1}) - (t_{n+1} - t_n) = t_{n+2} - 2 t_{n+1} + t_n$$

and it is possible to see this directly in terms of operators by computing

$$\Delta^2 = (S - 1)^2 = S^2 - 2S + 1.$$

Repeating this argument for larger exponents gives

$$\Delta^k = (S - 1)^k = \sum_{i=0}^k (-1)^i {k \choose i} S^i$$

simply by the binomial theorem! Translated into sequences, this means

$$\boxed{ (\Delta^k t)_n = \sum_{i=0}^k (-)^i {k \choose i} t_{n+i} }.$$

But we want to go the other way: to express the shift $S^n$ in terms of the difference operator. But since $\Delta = S - 1$, we have $S = \Delta + 1$, and hence

$$S^k = (\Delta + 1)^k = \sum_{i=0}^k {k \choose i} \Delta^i$$

so, applied to sequences, this gives

$$\boxed{ t_{n+k} = \sum_{i=0}^k {k \choose i} (\Delta^i t)_n }.$$

This is your desired identity, reindexed a bit.

Answer 2

NOTE: THIS IS NOT A COMPLETE ANSWER.

So I start with \begin{align} ∆^{n-1}_{t_{1}}&=∆^{n-2}_{t_2}-∆^{n-2}_{t_1}\\ &=∆^{n-3}_{t_3}-∆^{n-3}_{t_2}-∆^{n-3}_{t_2}+∆^{n-3}_{t_1}\\ &=∆^{n-3}_{t_3}-2∆^{n-3}_{t_2}+∆^{n-3}_{t_1}\\ &=∆^{n-4}_{t_4}-∆^{n-4}_{t_3}-2∆^{n-4}_{t_3}+2∆^{n-4}_{t_2}+∆^{n-4}_{t_2}-∆^{n-4}_{t_1}\\ &=∆^{n-4}_{t_4}-3∆^{n-4}_{t_3}+3∆^{n-4}_{t_2}-∆^{n-4}_{t_1}\\ \end{align}

So the binomial coefficient pattern with alternating signs similar to that of $(a-b)^k$ is quite clear here. We can use induction to check but I will leave it out for now. So we have \begin{align} ∆^{n-1}_{t_{1}}&=(-1)^0{k \choose 0}∆^{n-(k+1)}_{t_{k+1}}+(-1)^1{k \choose 1}∆^{n-(k+1)}_{t_{(k+1)-1}}+\dots+(-1)^k{k \choose k}∆^{n-(k+1)}_{t_{(k+1)-k}}\\ &=(-1)^0{k \choose 0}∆^{n-(k+1)}_{t_{k+1}}+(-1)^1{k \choose 1}∆^{n-(k+1)}_{t_{(k+1)-1}}+\dots+(-1)^k{k \choose k}∆^{n-(k+1)}_{t_{1}}\\ &=\sum_{r=0}^{k}{(-1)^r}{k \choose r}{∆^{n-(k+1)}_{t_{k-r+1}}} \end{align}

Now I will set $k=n-1$, then we have \begin{align} ∆^{n-1}_{t_{1}}&=\sum_{r=0}^{n-1}{(-1)^r}{n-1 \choose r}{t_{n-r}} \end{align} So in general, we have \begin{align} ∆^{n-m}_{t_{1}}&=\sum_{r=0}^{n-m}{(-1)^r}{n-m \choose r}{t_{n-m-r+1}}\\ {{n-1} \choose{n-m}}∆^{n-m}_{t_{1}}&=\sum_{r=0}^{n-m}{(-1)^r}{{n-1} \choose{n-m}}{n-m \choose r}{t_{n-m-r+1}}\\ \end{align} The right hand side expression of the given expression is \begin{align} \sum_{m=1}^{n-1}{{n-1} \choose{n-m}}∆^{n-m}_{t_{1}}&=\sum_{m=1}^{n-1}\sum_{r=0}^{n-m}{(-1)^r}{{n-1} \choose{n-m}}{n-m \choose r}{t_{n-m-r+1}}\\ \end{align} I have tried changing index but my attempts so far also are not successful.

Answer 3

Here we show by induction the following is valid for $n\geq 1$

\begin{align*} t_n=\sum_{j=0}^{n-1}\binom{n-1}{j}\Delta_{t_1}^j\tag{1} \end{align*}

Note that we additionally set $\Delta_{t_1}^0:=t_1$.

Base step: $n=1$

The right-hand side of (1) evaluated at $n=1$ is \begin{align*} \sum_{j=0}^{0}\binom{0}{j}\Delta_{t_1}^j =\binom{0}{0}\Delta_{t_1}^0=t_1 \end{align*} and the base step follows.

Induction hypothesis: We assume the validity of (1)

Induction step: $n\rightarrow n+1$

We have to show \begin{align*} t_{n+1}=\sum_{j=0}^{n}\binom{n}{j}\Delta_{t_1}^j \end{align*}

We start with the right-hand side and obtain \begin{align*} \color{blue}{\sum_{j=0}^{n}\binom{n}{j}\Delta_{t_1}^j } &=\binom{n}{0}\Delta_{t_1}^0+\sum_{j=1}^{n-1}\binom{n}{j}\Delta_{t_1}^j+\binom{n}{n}\Delta_{t_1}^n\tag{2}\\ &=\Delta_{t_1}^0+\sum_{j=1}^{n-1}\left[\binom{n-1}{j}+\binom{n-1}{j-1}\right]\Delta_{t_1}^j+\Delta_{t_1}^n\tag{3}\\ &=\Delta_{t_1}^0+\sum_{j=1}^{n-1}\binom{n-1}{j}\Delta_{t_1}^j+\sum_{j=0}^{n-2}\binom{n-1}{j}\Delta_{t_1}^{j+1}+\Delta_{t_1}^n\tag{4}\\ &=\sum_{j=0}^{n-1}\binom{n-1}{j}\Delta_{t_1}^{j}+\sum_{j=0}^{n-1}\binom{n-1}{j-1}\Delta_{t_1}^{j+1}\tag{5}\\ &=\left(1+\Delta_{t_1}\right)\sum_{j=0}^{n-1}\binom{n-1}{j}\Delta_{t_1}^{j}\tag{6}\\ &=(1+\Delta_{t_1})t_n\tag{7}\\ &=t_n+t_{n+1}-t_n\\ &\color{blue}{=t_{n+1}} \end{align*} and the claim follows.

Comment:

• In (2) we split the first and last element as preparation for the next step.

• In (3) we use the binomial identity $\binom{n}{j}=\binom{n-1}{j}+\binom{n-1}{j-1}$.

• In (4) we split the sums and shift the index of the right sum to start with $j=0$.

• In (5) we merge the single terms into the sums.

• In (6) we factor out the sum and are ready to use the induction hypothesis in the next step (7).

Note: To better see the connection with @QiaochuYuan's answer note that we can also write the relationship (1) as

\begin{align*} t_n=(1+\Delta_{t_1})^{n-1} \end{align*}

and the induction step $n\rightarrow n+1$ in this notation simply becomes

\begin{align*} \color{blue}{(1+\Delta_{t_1})^n}=(1+\Delta_{t_1})(1+\Delta_{t_1})^{n-1}=(1+\Delta_{t_1})t_n\color{blue}{=t_{n+1}} \end{align*}

indicating the strength and elegance of the operator based approach, besides the additional insight \begin{align*} (\Delta+1)^n=S^n\qquad\Longleftrightarrow\qquad (S-1)^n=\Delta^n \end{align*}

Answer 4

Qiaochu Yuan's answer is excellent, but I wanted to contribute an alternative method.

We can construct a polynomial $f(x)$ such that $f(k) = t_{k+1}$.

Newton's forward difference formula tells us that

$$f(x + a) = \sum_{k=0}^\infty \binom{a}{k} \Delta^k f(x)$$

Your conjecture is proven simply by taking $x = 0$ and $a = n - 1$.