Difference operator: Proof by induction that $\Delta^k (X_t)= k!a_k+\Delta^k (Y_t)$

Question

Hello I am having issues with the following exercise.

I have to prove that

$$\Delta^k (X_t)= k!a_k+\Delta^k (Y_t)$$

where $X_t = m_t +Y_t=\sum_{j=0}^ka_jt^j+Y_t$ for $t \in \mathbb {Z}$. Note: $\Delta$ is the backward difference operator: $\Delta X_t = X_t - X_{t-1}$, $\Delta^{j} X_t = \Delta(\Delta^{j-1} X_tX_t)$, $\Delta^{0} X_t = X_t$ etc.

Basis step: I have managed to show this for k=1.

Induction step: I assume that it holds for k and show that it holds for k+1. However, for some reason I just cannot figure out how to write it up for $k+1$ and show that it also holds. I can show it if I choose $k$ to be a certain number say 2 or 3 etc. but not for $k+1$.

What I have so far

$$\Delta^{k+1} (X_t)=\Delta(\Delta^{k} (X_t) ) = \Delta \left(k!a_k+\Delta^k (Y_t)\right)$$

where I used the assumption that it holds for k.

But how do I continue from here? What do I do with $k!a_k$ if I multiply with $\Delta$?

UPDATE:

I also tried the following $$\Delta^{k+1} (X_t)=\Delta^{k}(\Delta (X_t) ) = \Delta^{k}(X_{t}- X_{t-1} )= \Delta^{k}X_t - \Delta^{k}X_{t-1} = \Delta^{k}\left((m_t + Y_t) - (m_{t-1} + Y_{t-1})\right) = \Delta^{k+1}m_t + \Delta^{k+1}Y_t $$

But what about

$$\Delta^{k+1}m_t$$

I order to finish the prove I have to show that

$$\Delta^{k+1}m_t= (k+1)!a_{k+1}$$

Again I managed to do this for the basis step and I assume it holds for k. But same problem as before: I cannot figure out how to do it for k+1.

Hope some one can help. I am stuck.

Best Husky

Answer 1

You can think of the operator $\Delta$ as an approximation of the derivative operator. When reading the solution think of the corresponding claims where you have differentiation instead of $\Delta$. By the way, you have a typo in one of the formulae in the question: $\Delta^jX_t=\Delta(\Delta^{j-1}X_t X_t)$ should be $\Delta^j X_t=\Delta(\Delta^{j-1}X_t)$. A quick counterexample for the current formula is $Y_t=0 $ $X_t=2$.

So, back to the question: it is easy to show that $\Delta^k$ is linear, i.e. $\Delta^k(aX_t + bY_t) = a\Delta^k X_t + b\Delta^kY_t$ for all $a,b \in \mathbb{R}$, and therefore you have to show the given result only for the case $X_t = m_t$ It is a simple proof by induction on $k$ that $\Delta^{k} (t^k) = k!$ and, if $k > l$ $\Delta^{k} (t^l) = 0$ The base case $k=1$ is clear. $\Delta^{k+1}(t^{k+1}) =\Delta^k( t^{k+1} - t^k) = \Delta^k((k+1)t^k + (\text{low order terms}))$ By linearity and the induction hypothesis the last expression is $(k+1)k! = (k+1!)$ Because of this result, $\Delta^{k+1}x^l = 0$ for $l \leq k+1$ and the induction is complete.

So now, by linearity and the claim we just showed $\Delta^k(m_k) =\sum a_j \Delta_k(t^j) = k!a_k $ which we wanted to prove.

Answer 2

Here is a variation based upon induction slighty different than your last approach with $\Delta^{k+1}m_t$.

Let \begin{align*} X_t=\sum_{j=0}^ka_jt^j+Y_t\qquad\qquad k\geq 1 \end{align*} The following is valid \begin{align*} \Delta^k(X_t)=k!a_k+\Delta^k(Y_t)\qquad\qquad \tag{1} \end{align*}

$$ $$

Base step: k=1

\begin{align*} \Delta X_t&=\Delta\left(\sum_{j=0}^1a_jt^j+Y_t\right)\\ &=\left(a_0+a_1t+Y_t\right)-\left(a_0+a_1(t-1)+Y_{t-1}\right)\\ &=a_1+Y_t-Y_{t-1}\\ &=a_1+\Delta(Y_t) \end{align*}

Induction hypothesis: The claim (1) is valid for $k$

Inductive step: $k\longrightarrow k+1$

\begin{align*} \Delta^{k+1}(X_t)&=\Delta^{k+1}\left(\sum_{j=0}^{k+1}a_jt^j+Y_t\right)\\ &=\Delta^{k+1}\left(a_{k+1}t^{k+1}+\sum_{j=0}^{k}a_jt^j+Y_t\right)\\ &=\Delta^{k+1}\left(a_{k+1}t^{k+1}\right)+\Delta^{k+1}\left(\sum_{j=0}^{k}a_jt^j+Y_t\right)\\ &=\Delta^{k+1}\left(a_{k+1}t^{k+1}\right)+\Delta\left(\Delta^k(X_t)\right)\tag{2}\\ &=\Delta^{k+1}\left(a_{k+1}t^{k+1}\right)+\Delta\left(k!a_k+\Delta^k\left(Y_t\right)\right)\\ &=a_{k+1}\Delta^{k+1}t^{k+1}+\Delta\left(k!a_k\right)+\Delta^{k+1}(Y_t)\\ &=a_{k+1}\Delta^k\left(t^{k+1}-(t-1)^{k+1}\right)+\Delta^{k+1}(Y_t)\\ &=a_{k+1}\Delta^k\left(\sum_{j=0}^k\binom{k+1}{j}t^j(-1)^{k-j}\right)+\Delta^{k+1}(Y_t)\tag{3}\\ &=a_{k+1}\left(k!\binom{k+1}{k}\right)+\Delta^{k+1}(Y_t)\\ &=a_{k+1}(k+1)!+\Delta^{k+1}(Y_t) \end{align*}

Comment:

• In (2) we use the induction hypothesis (1) the first time

• In (3) we use the induction hypothesis (1) again with $a_j=\binom{k+1}{j}(-1)^{k-j}$ and $Y_t\equiv 0$.