Difference operator: Proof by induction that $\Delta^k (X_t)= k!a_k+\Delta^k (Y_t)$ 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 
 A: 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$.
A: 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. 
