求和公式的原理？

nttz

能解释下立方和求法，怎么不像是二项式展开的

lihpb

连续正整数n次方和可以用错位相减法，但为什么这里不直接求不定积分，而是多次一举搞个极限求和出来

nttz

lihpb 发表于 2024-8-1 15:49
连续正整数n次方和可以用错位相减法，但为什么这里不直接求不定积分，而是多次一举搞个极限求和出来 ...

这儿是最原始的定义求法，都是从0开始的，但是这儿用到的公式似乎和组合数有关系

tommywong

用了朱世傑恆等式，英文是Hockey-stick identity
這是將多項式寫成組合數的線性組合(可以用Newton's series)之後的求和方法

tommywong

所以有這個公式
artofproblemsolving.com/community/c728438h1707806_summation_with_polynomial
$\displaystyle \sum_{k=1}^n p(k)=\sum_{m=0}^{deg(p)} \binom{n}{m+1}\Delta^m p(1)$

nttz

tommywong 发表于 2024-8-1 16:27
所以有這個公式
artofproblemsolving.com/community/c728438h1707806_summation_with_polynomial
$ ...

好高深的知识，如何推导的，能否翻译下啥意思

tommywong

nttz 发表于 2024-8-2 11:07
好高深的知识，如何推导的，能否翻译下啥意思

首先差分算子的定義是$\Delta p(x)=p(x+1)-p(x)$

$\displaystyle \Delta^n p(x)=\Delta (\Delta^{n-1} p(x))
=\sum_{k=0}^n (-1)^{n-k}\binom{n}{k} p(x+k)$

可以先看看公式怎麼用

$\displaystyle \quad\sum_{k=1}^n p(k)=\sum_{m=0}^{deg(p)} \binom{n}{m+1}\Delta^m p(1)$

$p(k)=k,~\Delta p(k)=1$

$\displaystyle \sum_{k=1}^n k=\binom{n}{1}+\binom{n}{2}$

$p(k)=k^2,~\Delta p(k)=2k+1,~\Delta^2 p(k)=2$

$\displaystyle \sum_{k=1}^n k^2=\binom{n}{1}+3\binom{n}{2}+2\binom{n}{3}$

$p(k)=k^3,~\Delta p(k)=3k^2+3k+1,~\Delta^2 p(k)=6k+6,~\Delta^3 p(k)=6$

$\displaystyle \sum_{k=1}^n k^3=\binom{n}{1}+7\binom{n}{2}+12\binom{n}{3}+6\binom{n}{4}$

Newton's series是$\displaystyle p(x)=\sum_{m=0}^{deg(p)} \binom{x-a}{m}\Delta^m p(a)$

Newton's series將多項式寫成組合數的線性組合，可以先待定系數，再找出這些系數的通項。

Let $\displaystyle p(x)=\sum_{m=0}^{deg(p)} c_m \binom{x-a}{m}=c_0+c_1\binom{x-a}{1}+c_2\binom{x-a}{2}+\dots+c_{deg(p)}\binom{x-a}{deg(p)}$

$p(a)=c_0$

$\displaystyle \Delta \binom{x-a}{k}=\binom{x+1-a}{k}-\binom{x-a}{k}=\binom{x-a}{k-1}$

$\displaystyle \Delta p(x)=c_1+c_2\binom{x-a}{1}+c_3\binom{x-a}{2}+\dots+c_{deg(p)}\binom{x-a}{deg(p)-1}$

$\Delta p(a)=c_1$

$\displaystyle \Delta^m p(k)=c_m+c_{m+1}\binom{x-a}{1}+c_{m+2}\binom{x-a}{2}+\dots+c_{deg(p)}\binom{x-a}{deg(p)-m}$

$\Delta^m p(a)=c_m$

Hockey-stick identity可以用組合數的關係式$\displaystyle \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$做出來

nttz

tommywong 发表于 2024-8-1 16:27
所以有這個公式
https://artofproblemsolving.com/community/c728438h1707806_summation_with_polynomial
$ ...

我想问的$i^3$如何分解成这样的线性组合的，如何想到的？后面的组合恒等式还能理解

nttz

tommywong 发表于 2024-8-2 11:44
首先差分算子的定義是$\Delta p(x)=p(x+1)-p(x)$

$\displaystyle \Delta^n p(x)=\Delta (\Delta^{n-1} p ...

n阶差分递推公式怎么来的呢，貌似很多步骤中都没有来源
要么就是数学归纳法，我想问的是这个公式怎么产生，眼睛归纳不出来那么复杂的东西吧

tommywong

nttz 发表于 2024-8-2 12:06
我想问的$i^3$如何分解成这样的线性组合的，如何想到的？后面的组合恒等式还能理解 ...

en.wikipedia.org/wiki/Newton_polynomial#Main_idea

$p_{n}(x) = a_0+a_1(x-x_0)+a_2(x-x_0)(x-x_1)+\cdots + a_n(x-x_0)\cdots(x-x_{n-1})$

牛頓插值多項式用n個點$(x_i,y_i)$構造一個$n-1$次多項式，每個$x_i$都不同。

$\begin{bmatrix}
      1 &         & \ldots &        & 0  \\
      1 & x_1-x_0 &        &        &    \\
      1 & x_2-x_0 & (x_2-x_0)(x_2-x_1) &        & \vdots   \\
\vdots & \vdots  &        & \ddots &    \\
      1 & x_k-x_0 & \ldots & \ldots & \prod_{j=0}^{k-1}(x_k - x_j)
\end{bmatrix}
\begin{bmatrix}     a_0 \\     \\     \vdots \\     \\     a_{k} \end{bmatrix} =
\begin{bmatrix}      y_0 \\  \\  \vdots \\ \\    y_{k} \end{bmatrix}$

左邊是一個下三角矩陣，所以一定有解。

tommywong

nttz 发表于 2024-8-2 14:44
n阶差分递推公式怎么来的呢，貌似很多步骤中都没有来源
要么就是数学归纳法，我想问的是这个公式怎么产生 ...

$\displaystyle \Delta^np(x)=\sum_{k=0}^n (-1)^{n-k}\binom{n}{k} p(x+k)$

$n=1$時, $\displaystyle \Delta^1p(x)=\sum_{k=0}^1 (-1)^{1-k}\binom{1}{k} p(x+k)
=p(x+1)-p(x)$

$n=K$時, $\displaystyle \Delta^Kp(x)=\sum_{k=0}^K (-1)^{K-k}\binom{K}{k} p(x+k)$
$\displaystyle \Delta^{K+1}p(x)=\Delta(\Delta^Kp(x))=\sum_{k=0}^K (-1)^{K-k}\binom{K}{k} p(x+k+1)
-\sum_{k=0}^K (-1)^{K-k}\binom{K}{k} p(x+k)$
$\displaystyle =\sum_{k=1}^{K+1} (-1)^{K+1-k}\binom{K}{k-1} p(x+k)
-\sum_{k=0}^K (-1)^{K-k}\binom{K}{k} p(x+k)$
$\displaystyle =\binom{K}{K}p(x+K+1)+\sum_{k=1}^K (-1)^{K+1-k}\left(\binom{K}{k-1}+\binom{K}{k}\right) p(x+k)-(-1)^K\binom{K}{0}p(x)$
$\displaystyle =\sum_{k=0}^{K+1} (-1)^{K+1-k}\binom{K+1}{k} p(x+k)$