Proof of weird formula for method of differences

Question

Suppose we have to find sum of a sequence $t_1,t_2,t_3...t_n$.

For $1\le i\le n$, let $\triangle t_i=t_{i+1} -t_i$, $\triangle ^2t_i=\triangle t_{i+1}-\triangle t_i$ and so on ($\triangle ^{j}t_i=\triangle^{j-1} t_{i+1}-\triangle^{j-1} t_i$).

My book gives the formula for the $j$th term and sum $S_n$ of the sequence as:

$$ t_j = {}^{j-1}C_0\, t_1 + {}^{j-1}C_1\, \triangle t_1 + {}^{j-1}C_2\, \triangle^2 t_1 + \cdots + {}^{j-1}C_{j-1}\, \triangle^{j-1} t_1 $$ and $$ S_n =\sum_{j=1}^nt_j= {}^nC_1\, t_1 + {}^nC_2\, \triangle t_1 + {}^nC_3\, \triangle^2 t_1 + \cdots + {}^nC_n\, \triangle^{n-1} t_1. $$

(See the equations as printed in the book.)

How to prove this? Any reference is appreciated.

P.S- Sorry for the image, as I could not typeset the entire equation in Latex.

Answer 1

I will use the well-known notation $\newcommand{\mbin}[2]{{\small{\binom{#1}{#2}}}}{\displaystyle\mbin ab}$ instead of $\displaystyle{}^aC_b$ because I find it more readable, especially in combination with other symbols that have subscripts and superscripts.

If we define $\triangle^0\, t_i = t_i$ and $\triangle^1\, t_i = \triangle t_i$, your definition says that $$ \triangle^{k+1}\, t_i = \triangle^k\, t_{i+1} - \triangle^k\, t_i $$ for integers $i \geq 1$ and $k\geq 0$.

Equivalently, $$ \triangle^k\, t_{i+1} = \triangle^k\, t_i + \triangle^{k+1}\, t_i. \tag1 $$

It will be useful to define $\triangle^{-1}\, t_1 = 0$ and $$ \triangle^{-1}\, t_i = \sum_{j = 1}^{i-1} t_j $$ for any integer $i > 1$. If we do that, then Equation $(1)$ is true for all integers $i \geq 1$ and $k\geq -1$.

We can apply Equation $(1)$ multiple times for other subscripts/superscripts: \begin{align} \triangle^k\, t_{i+2} &= \triangle^k\, t_{i+1} + \triangle^{k+1}\, t_{i+1} \\ &=\left(\triangle^k\, t_i + \triangle^{k+1}\, t_i\right) + \left(\triangle^{k+1}\, t_i + \triangle^{k+2}\, t_i\right) \\ &= \triangle^k\, t_i + 2 \triangle^{k+1}\, t_i + \triangle^{k+2}\, t_i. \end{align}

\begin{align} \triangle^k\, t_{i+3} &= \triangle^k\, t_{i+2} + \triangle^{k+1}\, t_{i+2} \\ &=\left(\triangle^k\, t_i + 2 \triangle^{k+1}\, t_i + \triangle^{k+2}\, t_i\right) + \left(\triangle^{k+1}\, t_i + 2 \triangle^{k+2}\, t_i + \triangle^{k+3}\, t_i\right) \\ &= \triangle^k\, t_i + 3 \triangle^{k+1}\, t_i + 3 \triangle^{k+2}\, t_i + \triangle^{k+3}\, t_i. \end{align}

Do you recognize the pattern? It is $$ \triangle^k\, t_{i+r} = \mbin r0 \triangle^k\, t_i + \mbin r1 \triangle^{k+1}\, t_i + \mbin r2 \triangle^{k+2}\, t_i + \cdots + \mbin rr \triangle^{k+r}\, t_i. \tag2 $$

We can prove this by induction on $r$. The base case is for $r = 0$, $$ \triangle^k\, t_{i+r} = \mbin 00 \triangle^k\, t_{i} $$ for any $i \geq 1$ and any $k \geq -1$. For the inductive step, assume Equation $(2)$ is true for a certain non-negative integer $r$. Then \begin{align} \triangle^k\, t_{i+r+1} &= \triangle^k\, t_{i+r} + \triangle^{k+1}\, t_{i+r} \\ &= \mbin r0 \triangle^k\, t_i + \mbin r1 \triangle^{k+1}\, t_i + \mbin r2 \triangle^{k+2}\, t_i + \cdots + \mbin rr \triangle^{k+r}\, t_i \\ & \qquad + \mbin r0 \triangle^{k+1}\, t_i + \mbin r1 \triangle^{k+2}\, t_i + \mbin r2 \triangle^{k+3}\, t_i + \cdots + \mbin rr \triangle^{k+r+1}\, t_i \\ &= \triangle^k\, t_i + \left(\!\mbin r0 + \mbin r1\!\right)\triangle^{k+1}\,t_i + \left(\!\mbin r1 + \mbin r2\!\right) \triangle^{k+2}\, t_i + \cdots + \triangle^{k+r+1}\, t_i \\ &= \mbin {r+1}0 \triangle^k\, t_i + \mbin {r+1}1 \triangle^{k+1}\,t_i + \mbin {r+1}2 \triangle^{k+2}\, t_i + \cdots + \mbin {r+1}{r+1} \triangle^{k+r+1}\, t_i. \end{align} That completes the induction.

Now that we have the formula in Equation $(2)$, we can simply apply it to the original question by choosing suitable values of $i$, $k$, and $r$.

With $i = 1$, $k = 0$, $r = n - 1$:

\begin{align} t_n &= \triangle^0\, t_{1+(n-1)}\\ &= \mbin {n-1}0 \triangle^0\, t_1 + \mbin {n-1}1 \triangle^{0+1}\, t_1 + \mbin {n-1}2 \triangle^{0+2}\, t_1 + \cdots + \mbin {n-1}{n-1} \triangle^{0+n-1}\, t_1 \\ &= \mbin {n-1}0 t_1 + \mbin {n-1}1 \triangle t_1 + \mbin {n-1}2 \triangle^2\, t_1 + \cdots + \mbin {n-1}{n-1} \triangle^{n-1}\, t_1. \end{align}

With $i = 1$, $k = -1$, $r = n$:

\begin{align} \sum_{j=1}^n t_j &= \triangle^{-1}\, t_{1+n} \\ &= \mbin n0 \triangle^{-1}\, t_1 + \mbin n1 \triangle^{-1+1}\, t_1 + \mbin n2 \triangle^{-1+2}\, t_1 \\ & \qquad\qquad\qquad\qquad + \mbin n3 \triangle^{-1+3}\, t_1 + \cdots + \mbin nn \triangle^{-1+n}\, t_1 \\ &= \mbin n0\cdot 0 + \mbin n1 \triangle^0 t_1 + \mbin n2 \triangle^1\, t_1 + \mbin n3 \triangle^2\, t_1 + \cdots + \mbin nn \triangle^{n-1}\, t_1 \\ &= \mbin n1 t_1 + \mbin n2 \triangle t_1 + \mbin n3 \triangle^2\, t_1 + \cdots + \mbin nn \triangle^{n-1}\, t_1. \end{align}

---

If you carefully compare the book's formulas with these results, you should be able to spot some errors in the book. Where the book says

$$ t_n = {}^{n-1}C_0\, t_1 + {}^{n-1}C_1\, \triangle t_1 + {}^{n-1}C_2\, \triangle^2 t_1 + \cdots + {}^{n-1}C_{r-1}\, \triangle^{r-1} t_1, $$

the final term should be ${}^{n-1}C_{n-1}\, \triangle^{n-1} t_1$ rather than ${}^{n-1}C_{r-1}\, \triangle^{r-1} t_1$ (that is, the formula should use $n$ rather than $r$, which has no role in this formula), and where the book says

$$ S_n = {}^nC_1\, t_1 + {}^nC_2\, \triangle t_1 + {}^nC_3\, \triangle^2 t_1 + \cdots + {}^nC_r\, \triangle^r t_1, $$

the final term should be ${}^nC_n\, \triangle^{n-1} t_1$ rather than ${}^nC_r\, \triangle^r t_1$, that is, again it should use $n$, not $r$, but the superscript of the $\triangle$ symbol should be only $n-1$, not simply replacing $r$ by $n$.

Answer 2

I edited the equations so they can be proved as follows. We want to prove $$ t_j=\sum_{i=0}^{j-1}\binom{j-1}{i}\Delta^i t_1\qquad (1)$$ The sum $S_n=\sum_{j=1}^n t_j$ expression can be deduced from (1) by inversing the summation order and noticing $$\sum_{j=i+1}^n \binom{j-1}{i}=\binom{n}{i+1},$$ this can be proved from Pascal's identity ($\binom{p}{q}=\binom{p-1}{q-1}+\binom{p-1}{q}$) and induction.

Back to (1) also by induction. Say $t_j= \sum\limits_{i=0}^{j-1}\binom{j-1}{i}\Delta^i t_1$ is true we want $$t_{j+1}=\sum_{i=0}^{j}\binom{j}{i}\Delta^i t_1=t_1+\sum_{i=1}^{j}\left[\binom{j-1}{i}+\binom{j-1}{i-1}\right]\Delta^i t_1.$$ This equals after writing $\Delta^i t_1=\Delta^{i-1} t_2-\Delta^{i-1}t_1$ to $$t_1+t_j-t_1-t_j+\sum\limits_{i=0}^{j-1}\binom{j-1}{i}\Delta^i t_2$$ which is by induction hypothesis (up to a reindexation) $t_{j+1}$.