Simplying linear recurrence sum with binomials

Question

Is there a way to simplify

$$\sum_{k=1}^{n} \binom{n}{k}f(k)$$

Where $f(k)$ is a large linear recurrence?

Answer 1

Yes there is. Assuming that $f(k)$ is a sequence with a characteristic polynomial $p(x)$, then: $$ G(n) = \sum_{k=0}^{n}\binom{n}{k}\,f(k) $$ gives a linear recurrence, too, and the characteristic polynomial associated with $G(n)$ is just $p(x-1)$, by the binomial theorem. For instance, if $f(k)$ is the $k$-th Fibonacci number, we have $p(x)=x^2-x-1$ and: $$ G(n) = \sum_{k=0}^{n}\binom{n}{k}F_k = \frac{1}{\sqrt{5}}\sum_{k=0}^{n}\binom{n}{k}\left(\phi^n-\bar\phi^n\right) = \frac{1}{\sqrt{5}}\left((1+\phi)^n-(1+\bar\phi)^n\right), $$ so: $$ G(n) = \frac{1}{\sqrt{5}}\left(\phi^{2n}-\bar\phi^{2n}\right) = F_{2n} $$ is a sequence with characteristic polynomial $x^2-3x+1 = p(x-1)$.