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$.
 A: 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.
A: 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}
$$
