Decomposition of $ \binom {n} {j-1}j^k $ It is easy to check that: 
$$
\binom {n} {j-1}j = \binom {n-1} {j-1}+\binom {n-1} {j-2}(n+1)
$$
and
$$
\binom {n} {j-1}j^2 = \binom {n-2} {j-1}+\binom {n-2} {j-2}(3n+2)+\binom {n-2} {j-3}(n+1)^2
$$
We are interested in the decomposition:
$$
\binom {n} {j-1}j^k = \sum\limits_{u=0}^k \binom {n-k} {j-1-u}P_{k,u}(n)
$$
Setting $j=1$ implies $P_{k,0}(n)=1$ and setting $j=2$ implies $ P_{k,1}(n)=n2^k-(n-k) $
This is coherent with relations for $k=1 $and $k=2$.
For $k=3$, $P_{3,0}(n)=1$ and $P_{3,1}(n)=7n+3$, and setting $j=3$, Wolfram Alpha computes $ P_{3,2}(n)=6n^2+8n+3$, and with assumption $ P_{3,3}(n)=(n+1)^3 $ it found decomposition is true.
Is there an analytic form of $P_{k,u}(n)$, i.e. in particular is $P_{k,u}(n)$ always a polynomial of variable $n$ and degree $u$? And is it true that  $ P_{k,k}(n)=(n+1)^k     $?
 A: Let $\mathbb{K}$ be a field of characteristic $0$.  For any polynomial $Q(x)\in\mathbb{K}[x]$, $Q(x)=\sum\limits_{i=0}^\infty\,c_i\,\binom{x}{i}$ for some $c_0,c_1,c_2,\ldots\in\mathbb{K}$ (with only finitely many of them being nonzero).  Then, $$\binom{n}{r}\,Q(r)=\sum_{i=0}^\infty\,c_i\,\binom{n}{r}\,\binom{r}{i}=\sum_{i=0}^\infty\,c_i\,\binom{n}{i}\,\binom{n-i}{r-i}\,.$$
Now, if you want the sum of the form $$\binom{n}{r}\,Q(r)=\sum_{\nu=0}^k\,f_\nu(n)\,\binom{n-k}{r-\nu}$$ where $k$ is the degree of $Q(x)$, then use the identity $\binom{m}{t}=\sum\limits_{\mu=0}^t\,\binom{p}{\mu}\,\binom{m-p}{t-\mu}$ to get
$$\binom{n}{r}\,Q(r)=\sum_{i=0}^k\,c_i\,\binom{n}{i}\,\binom{n-i}{r-i}=\sum_{i=0}^k\,c_i\,\binom{n}{i}\,\sum_{\mu=0}^{r-i}\,\binom{k-i}{\mu}\,\binom{n-k}{r-i-\mu}\,.$$
Ergo,
$$\binom{n}{r}\,Q(r)=\sum_{\nu=0}^k\,\left(\sum_{i=0}^{\nu}\,c_i\,\binom{k-i}{\nu-i}\,\binom{n}{i}\right)\,\binom{n-k}{r-\nu}\,.$$
That is, $f_\nu(n)=\sum\limits_{i=0}^{\nu}\,c_i\,\binom{k-i}{\nu-i}\,\binom{n}{i}$, which clearly is a polynomial in $n$ of degree at most $\nu$.  It is also easy to see that, if $n\geq k$, the coefficients $f_\nu(n)$'s are unique (so that the equality holds for all choices of $r$).
For example, if $r=j-1$ and $Q(x)=x+1=1\cdot\binom{x}{0}+1\cdot\binom{x}{1}$, then $$P_{1,0}(n)=f_0(n)=1\cdot\binom{n}{0}\,\binom{1-0}{0-0}=1$$ and $$P_{1,1}(n)=f_1(n)=1\cdot\binom{n}{0}\,\binom{1-0}{1-0}+1\cdot\binom{n}{1}\,\binom{1-1}{1-1}=n+1\,,$$ or $$\binom{n}{j-1}j=\binom{n}{r}\,Q(r)=f_0(n)\,\binom{n-1}{r-0}+f_1(n)\,\binom{n-1}{r-1}=\binom{n-1}{j-1}+(n+1)\,\binom{n-1}{j-2}\,.$$
Hence, your question is reduced to finding the coefficients $c_0,c_1,c_2,\ldots,c_k\in\mathbb{K}$ such that $$(x+1)^k=\sum\limits_{i=0}^k\,c_i\,\binom{x}{i}\,.$$  It turns out that $c_i=i!\,\left\{\begin{array}{c}k\\i\end{array}\right\}+(i+1)!\,\left\{\begin{array}{c}k\\i+1\end{array}\right\}$, where $\left\{\begin{array}{c}m\\t\end{array}\right\}$ denotes the Stirling number of the second kind with parameters $m$ and $t$.  Ergo, 
$$\begin{align}P_{k,\nu}(n)&=f_\nu(n)=\sum_{i=0}^\nu\,c_i\,\binom{k-i}{\nu-i}\,\binom{n}{i}
\\&=\sum_{i=0}^\nu\,\Biggl(i!\,\left\{\begin{array}{c}k\\i\end{array}\right\}+(i+1)!\,\left\{\begin{array}{c}k\\i+1\end{array}\right\}\Biggr)\,\binom{k-i}{\nu-i}\,\binom{n}{i}\,.\end{align}$$  From the equation above, it is evident that the degree of $P_{k,\nu}(n)$ as a polynomial in $n$ is precisely $\nu$.  You can immediately see that $c_0=1$ and $c_1=2^k-1$.  This gives $$P_{k,0}(n)=f_0(n)=1\cdot\binom{k-0}{0-0}\,\binom{n}{0}=1$$ and $$P_{k,1}(n)=f_1(n)=1\cdot\binom{k-0}{1-0}\,\binom{n}{0}+\left(2^k-1\right)\cdot\binom{k-1}{1-1}\,\binom{n}{1}=2^kn-n+k\,.$$  Furthermore, we have $$P_{k,k}(n)=f_k(n)=\sum\limits_{i=0}^k\,c_i\,\binom{k-i}{k-i}\,\binom{n}{i}=\sum\limits_{i=0}^k\,c_i\,\binom{n}{i}=(n+1)^k$$ by the definitions of the $c_i$'s.
