Sum of Stirling numbers with exponents

I have a trouble with the following sum $\sum_{i=0}^n\binom{n}{i}S(i,m)3^i$, where $S(i,m)$ is the Stirling number of the second kind (the number of all partitions of $i$ elements into $m$ nonempty sets).

Below it was obtained the sum $f(n,m)=\frac{1}{m!}\sum_{k=0}^m(-1)^{m-k}\binom{m}{k}(1+3k)^n$. Is there a further simplification of this expression?

• What exactly would you expect to get? – Igor Rivin Oct 9 '15 at 10:49
• Can you include in your question the array consisting from first values of your function $f(m,n)$? – Alexey Ustinov Oct 9 '15 at 10:55
• I would like to obtain a closed form of my sum (if it exists, of couse). It will be the best solution. But I will be pleased for any advice. – Artem Oct 9 '15 at 11:14
• sometimes an alternating sum is easier to work with – JMP Oct 9 '15 at 11:25
• Unfortunately, my sum can not be alternating, since it occurs in the counting of solutions of equations over some semilattices. – Artem Oct 9 '15 at 11:39

here is a table of $f(m,n)$ for small values of $m$ and $n\geq m$ (note that $f(m,n)=0$ for $n<m$):

$f(n,1)=-1+4^n$

$f(n,2)=\tfrac{1}{2}\left(1-2\cdot 4^n+7^n\right)$

$f(n,3)=\tfrac{1}{6}\left(-1+3\cdot 4^n-3\cdot 7^n+10^n\right)$

$f(n,4)=\tfrac{1}{24}\left(1-4\cdot 4^n+6\cdot 7^n-4\cdot 10^n+13^n\right)$

$f(n,5)=\tfrac{1}{120}\left(-1+5\cdot 4^n-10\cdot 7^n+10\cdot 10^n-5\cdot 13^n+16^n\right)$

$f(n,6)=\tfrac{1}{720}\left(1-6\cdot 4^n +15\cdot 7^n-20\cdot 10^n+15\cdot 13^n-6\cdot 16^n+19^n\right)$

there is a pattern, which as Todd Trimble points out is

$$f(n,m)=\frac1{m!} \sum_{k=0}^m (-1)^{m-k} \binom{m}{k} (1 + 3k)^n$$

note: Mathematica gets $f(n,2)$ wrong... [SE post]

• The general pattern is $\frac1{m!} \sum_{k=0}^m (-1)^{m-k} \binom{m}{k} (1 + 3k)^n$? – Todd Trimble Oct 9 '15 at 11:59
• You are right, and I can prove this formula! Now the question is: how to simplify the obtained pattern? – Artem Oct 9 '15 at 12:03
• Except for the factor in front of the sum, this is the $m^{th}$ iterate of the successive difference operator applied to the function $k \mapsto (1 + 3k)^n$ (for what that's worth). – Todd Trimble Oct 9 '15 at 12:18