Cara untuk menyederhanakan ekspresi kombinatorial secara komputasi?

Question

Saya memiliki ekspresi berikut, $$\sum_{m=1}^{n}\sum_{k=m}^{n} (-1)^{k-m} {k\choose m} P_k$$ dimana $P_k$ adalah fungsi arbitrer yang hanya bergantung pada $k$.

Sekarang mudah untuk melihat bahwa ekspresi ini akan menghitung hal yang sama berulang kali. Adakah representasi yang lebih kompak untuk ini yang mengatasi masalah ini? (Saya tidak menginginkan solusi komputasi melainkan solusi aljabar yang mencerminkan penghematan dalam komputasi)

Answer 1

Peter Foreman di komentar benar. Balik urutan penjumlahan dan gunakan rumus binomial:

$$\begin{align*} \sum_{m=1}^n\sum_{k=m}^n(-1)^{k-m}\binom{k}mP_k&=\sum_{k=1}^nP_k\sum_{m=1}^k(-1)^{k-m}\binom{k}m\\ &=\sum_{k=1}^nP_k\left(\underbrace{\sum_{m=0}^k(-1)^{k-m}\binom{k}m}_{=0}-(-1)^k\right)\\ &=\sum_{k=1}^n(-1)^{k+1}P_k \end{align*}$$