# Proving the formula holds for the $k$-th order differences of a sequence.

Prove that the following formula holds for the $k$-th order differences of a sequence $\{h_n\}_{n\geq0}$:

$$\Delta^kh_0=\sum^k_{j=0}(-1)^{k-j}{k \choose j}h_j$$

by using induction on $k$.

-
After 31 questions, maybe the time has come to start indicating your thoughts on the questions you ask. – Did Apr 7 '13 at 18:01

HINT: This is an obvious candidate for a proof by induction on $k$. The induction step must surely start like this:
\begin{align*} \Delta^{k+1}h_0&=\Delta^kh_1-\Delta^kh_0\\ &=\Delta^kh_1-\sum_{j=0}^k(-1)^{k-j}\binom{k}jh_j&&\text{by the induction hyp.}\\ &=\Delta^kh_1+\sum_{j=0}^k(-1)^{(k+1)-j}\binom{k}jh_j\;. \end{align*}
To handle the $\Delta^kh_1$ term, let $a_i=h_{i+1}$ for $i\ge 0$, and notice that $\Delta^kh_1=\Delta^ka_0$, to which you can apply your induction hypothesis.
As Brian says, this is best proved by induction. However, sometimes proving slightly more makes the proof go easier. For example, prove $$\Delta^kh_n=\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}h_{n+j}\tag{1}$$ The cases $k=0$ and $k=1$ are true by definition. Suppose that $(1)$ is true for some $k$, then \begin{align} \Delta^{k+1}h_n &=\Delta\left(\Delta^kh_n\right)\\ &=\Delta^kh_{n+1}-\Delta^kh_n\\ &=\left(\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}h_{n+1+j}\right) -\left(\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}h_{n+j}\right)\\ &=\left(\sum_{j=1}^{k+1}(-1)^{k-j+1}\binom{k}{j-1}h_{n+j}\right) -\left(\sum_{j=0}^k(-1)^{k-j}\binom{k}{j}h_{n+j}\right)\\ &=\sum_{j=0}^{k+1}(-1)^{k+1-j}\left[\binom{k}{j-1}+\binom{k}{j}\right]h_{n+j}\\ &=\sum_{j=0}^{k+1}(-1)^{k+1-j}\binom{k+1}{j}h_{n+j}\tag{2} \end{align}