Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
5  
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
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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} $$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.