조합 식을 계산적으로 단순화하는 방법은 무엇입니까?

Question

다음과 같은 표현이 있습니다. $$\sum_{m=1}^{n}\sum_{k=m}^{n} (-1)^{k-m} {k\choose m} P_k$$ 어디 $P_k$ 다음에 만 의존하는 임의의 함수입니다. $k$.

이제이 표현이 같은 것을 반복해서 계산한다는 것을 쉽게 알 수 있습니다. 이 문제를 극복하는 더 간결한 표현이 있습니까? (나는 계산 솔루션이 아니라 계산 절약을 반영하는 대수 솔루션을 원합니다)

Answer 1

의견의 Peter Foreman이 맞습니다. 합산 순서를 반대로하고 이항 공식을 사용합니다.

$$\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*}$$