$\sum k^mq^k$待定系数法

tommywong

p(x)为m次多项式
$\displaystyle \sum_{k=1}^n p(k)q^k=(\sum_{k=0}^m a_k n^k)q^n-a_0$

求$\displaystyle \sum_{k=1}^n kq^{k-1}$
$\displaystyle \sum_{k=1}^n kq^{k-1}=(a_0+a_1n)q^n-a_0$
$\begin{cases}(a_0+a_1)q-a_0=1\\(a_0+2a_1)q^2-a_0=1+2q\end{cases}$
$\displaystyle a_0=\frac{-1}{(q-1)^2},a_1=\frac{1}{q-1}$
$\displaystyle \sum_{k=1}^n kq^{k-1}=\frac{(q-1)n-1}{(q-1)^2}q^n+\frac{1}{(q-1)^2}$

但这样不够好，求方程不够简单，能有办法像帕斯卡矩阵那样bug逆矩阵就好了

tommywong

$\displaystyle\sum_{k=1}^n p(k)q^{k-1}=f(n)q^n-f(0)$
$qf(n)-f(n-1)=p(n)$
$P=[(-1)^{i-j}C_{m-(j-1)}^{i-1}]$
$[n^{m+1-j}](qI-P)[f_{i-1}]=[n^{m+1-j}][p_{i-1}]$
$[f_{i-1}]=(qI-P)^{-1}[p_{i-1}]$
$L_0=L_1=1,L_2=q+1,L_3=q^2+4q+1,L_4=q^3+11q^2+11q+1,...$
$(qI-P)^{-1}=[(-1)^{i-j}C_{m-j}^{i-j}L_{i-j}(q-1)^{-(i-j+1)}]$

求$\displaystyle\sum_{k=1}^n kq^{k-1}$
$(qI-P)^{-1}=
\begin{pmatrix}
C_1^0 L_0(q-1)^{-1} & 0\\
-C_1^1 L_1(q-1)^{-2} & C_0^0 L_0(q-1)^{-1}
\end{pmatrix}$
$f(n)=
\begin{pmatrix}n & 1\end{pmatrix}
\begin{pmatrix}
C_1^0 L_0(q-1)^{-1} & 0\\
-C_1^1 L_1(q-1)^{-2} & C_0^0 L_0(q-1)^{-1}
\end{pmatrix}
\begin{pmatrix}1 \\ 0\end{pmatrix}
=(q-1)^{-1}n-(q-1)^{-2}$
$\displaystyle\sum_{k=0}^n kq^{k-1}=[(q-1)^{-1}n-(q-1)^{-2}]q^n+(q-1)^{-2}$

$(qI-P)^{-1}$的通项是写出来了
李善兰数也有通项，但整个看起来感觉很长，要再改

tommywong

这次好看多了

$\displaystyle\sum_{k=1}^n (2k+1)q^{k-1}=f(n)q^n-f(0)$
$P=
\begin{pmatrix}1 & -1\\0 & 1\end{pmatrix},
(qI-P)^{-1}=
\begin{pmatrix}(q-1)^{-1} & -(q-1)^{-2}\\0 & (q-1)^{-1}\end{pmatrix}$
$\displaystyle
\begin{pmatrix}1 & 0\\-1 & 1\end{pmatrix}
\begin{pmatrix}2(1)+1\\2(2)+1\end{pmatrix}=
\begin{pmatrix}3\\2\end{pmatrix}$
$\displaystyle f(n)=
\begin{pmatrix}C_{n-1}^0 & C_{n-1}^1\end{pmatrix}
\begin{pmatrix}(q-1)^{-1} & -(q-1)^{-2}\\0 & (q-1)^{-1}\end{pmatrix}
\begin{pmatrix}3\\2\end{pmatrix}
=\frac{3q-5}{(q-1)^2}+\frac{2}{q-1}C_{n-1}^1$
$\displaystyle f(0)=\frac{3q-5}{(q-1)^2}-\frac{2}{q-1}=\frac{q-3}{(q-1)^2}$
$\displaystyle\sum_{k=1}^n (2k+1)q^{k-1}=
[\frac{3q-5}{(q-1)^2}+\frac{2}{q-1}C_{n-1}^1]q^n-\frac{q-3}{(q-1)^2}$

$m=4,P=
\begin{pmatrix}
1 & -1 & 1 & -1 & 1\\
0 & 1 & -1 & 1 & -1\\
0 & 0 & 1 & -1 & 1\\
0 & 0 & 0 & 1 & -1\\
0 & 0 & 0 & 0 & 1\\
\end{pmatrix}$
$(qI-P)^{-1}=
\begin{pmatrix}
(q-1)^{-1} & -(q-1)^{-2} & q(q-1)^{-3} & -q^2(q-1)^{-4} & q^3(q-1)^{-5}\\
0 & (q-1)^{-1} & -(q-1)^{-2} & q(q-1)^{-3} & -q^2(q-1)^{-4}\\
0 & 0 & (q-1)^{-1} & -(q-1)^{-2} & q(q-1)^{-3}\\
0 & 0 & 0 & (q-1)^{-1} & -(q-1)^{-2}\\
0 & 0 & 0 & 0 & (q-1)^{-1}\\
\end{pmatrix}$

tommywong

$\displaystyle \sum_{k=1}^n p(k)q^{k-1}=f(n)q^n-f(0)$
$\displaystyle f(n)=\frac{p(n)}{q-1}+\frac{1}{(q-1)^2}\sum_{k=1}^m \frac{(-1)^kq^{k-1}}{(q-1)^{k-1}}\Delta^k(p(n))$
$\Delta(2n+1)=2(1)=2$
$\displaystyle f(n)=\frac{2n+1}{q-1}-\frac{2}{(q-1)^2}$
$\displaystyle f(0)=\frac{1}{q-1}-\frac{2}{(q-1)^2}=\frac{q-3}{(q-1)^2}$
$\displaystyle \sum_{k=1}^n (2k+1)q^{k-1}=[\frac{2n+1}{q-1}-\frac{2}{(q-1)^2}]q^n-\frac{q-3}{(q-1)^2}$

tommywong

原来差分算子这么好用
$qf(n)-f(n-1)=p(n),\Delta^{m+1}p(n)=0$
$\displaystyle(qI-E^{-1})^{-1}=...=\frac{1}{q-1}I+\sum_{k=1}^m \frac{(-1)^kq^{k-1}}{(q-1)^{k-1}}\Delta^k$

血狼王

回复 5# tommywong


哈哈，果然有一手

战巡

表示母函数瞬秒

对$\sum q^k$做拉普拉斯变换，有
\[M(t)=\sum_{k=1}^n e^{tk}q^k=\frac{e^{(n+1)t}q^{n+1}-qe^t}{qe^t-1}\]
而后易证
\[M^{(m)}(0)=\sum_{k=1}^n k^mq^k\]

tommywong

回复 7# 战巡

$\displaystyle \sum_{k=1}^n k^mq^k=\sum_{k=0}^m \frac{m!}{k!}(1-(n+1)^kq^n)(\frac{q}{1-q})^{m-k+1}$

不错，挺好看

但我这个不只是对$k^m$，而是对任意多项式$p(k)$

tommywong

回复 7# 战巡

不好意思，我算错了$\displaystyle (\frac{1}{1-qe^t})^{(m-k)}$，所以8#应该是错的

请问你的意思是不是这个$M^{(m)}(0)$有通项？可以写出来吗？

战巡

回复 9# tommywong

不知道，应该没有简单通项，或者只能用伯努利多项式来表示

tommywong

之前有弄过这种东西

$\displaystyle \sum_{k=0}^n C_k^m q^{k-m}=\frac{1}{(1-q)^{m+1}}-\frac{1}{(1-q)^{m+1}}\sum_{k=0}^m C_{n+1}^k q^{n+1-k}(1-q)^k$

可是要用这个的话我又要把多项式换成组合数，这样就变成两重和式了，算起来挺麻烦，除非这个两重和式还可以化简

hbghlyj

战巡 发表于 2015-12-25 09:04
表示母函数瞬秒

对$\sum q^k$做拉普拉斯变换，有

看着像Moment generating function
$$m_{Y}(t)=\sum_{k=0}^{\infty} \frac{\mu_{k}}{k !} t^{k}$$
where $\mu_{k}=\mathbb{E}\left[Y^{k}\right]$ is the $k$-th moment of $Y$.

hbghlyj

Geometric distribution
The moments for the number of failures before the first success are given by
\begin{aligned}\mathrm {E} (Y^{n})&{}=\sum _{k=0}^{\infty }(1-p)^{k}p\cdot k^{n}\\&{}=p\operatorname {Li} _{-n}(1-p)\end{aligned}where $\operatorname {Li} _{-n}(1-p)$ is the polylogarithm function.