2/14 笔记

尝试每天记点笔记然后坚持更新吧。

差分

一些定义
  • 差分算子 $\Delta{f(x)} = f(x + 1) – f(x)$
  • 下降阶乘幂 $x^{\underline{m}} = x(x-1)(x-2)\cdots(x – m + 1)$, $m > 0$ , $x ^ {\underline{0}} = 1$

  • 观察$m > 0$时的阶乘幂,可以定义 $m < 0$时,$x^{\underline{m}} = \dfrac{1}{(x+1)(x+2)\cdots(x+m)}$

  • “有限微积分” :令$g(x)=\Delta{f(x)}$,称$\sum{g(x)\delta{x}}$ 是 $g(x)$ 的不定和式。那么
    $$
    \sum_{a}^{b}{g(x)}\delta{x} = \sum_{k=a}^{b-1}{g(k)} = f(x) \big \vert^{b}_{a} = f(b) – f(a)
    $$
  • 移位算子 $Ef(x)$ :$Ef(x) = f(x + 1)$
下降阶乘幂
  • 指数法则 $x^{\underline{m+n}} = x^{\underline{m}}(x-m)^{\underline{n}}$, 其中 $m$ 和 $n$ 是整数。

  • 类似于二项式定理,$(x+y)^{\underline{m}}$ 和 $(x+y)^m$ 有类似的结果。只是需要把每一个幂都改成阶乘幂的形式。

有限微积分
  • 与无限微积分(以下简称“微积分”)有相似的性质:满足区间可加,上下界限交换后取负号的性质。

  • 可以证明,对于有限微积分,有
    $$
    \sum_{k=0}^{n-1}{k^{\underline{m}}} = \dfrac{k^{\underline{m+1}}}{m+1}\Bigg |^{n}_{0}
    $$
    其中 $m \neq -1$

  • 对于 $m=-1$ 的情形,由于
    $$
    x^{\underline{-1}} = \dfrac{1}{x + 1}
    $$

而无穷级数 $H_{n} = \sum{\dfrac{1}{x}}$ 的差分就是 $x^{\underline{-1}}$ 。这样我们就给有限微积分找了个”自然对数”。

  • “自然底数 $e$ ” : 类比微积分,我们有 $f(x + 1) – f(x) = f(x)$ 。简单点,就用 $f(x) = 2^{x}$ 作为我们离散情形下的自然底数 $e$。

  • 分部求和法则:类比微积分,我们先考虑 $\Delta{v(x)u(x)}$ 。可以验证,
    $$
    \begin{aligned}
    LHS &= v(x+1)u(x+1) – v(x)u(x) \\
    &= u(x+1)v(x+1) – u(x)v(x+1) + u(x)v(x+1) – u(x)v(x)\\
    &= v(x+1)\Delta{u(x)} – u(x)\Delta{v(x)}\\
    &= Ev(x)\Delta{u(x)} – u(x)\Delta{v(x)}\\
    \end{aligned}
    $$
    这样我们就得到
    $$
    \sum{u\Delta{v}} = uv – \sum{Ev\Delta{u}}
    $$

取整函数

  • 对于下取整函数,
    若$\lfloor x \rfloor = n$,有
    $$
    \begin{aligned}
    n \leq x < n + 1 \\
    x – 1 < n \leq x
    \end{aligned}
    $$

若$x$是实数,$n$是整数,
$$
\begin{aligned}
x < n \Leftrightarrow \lfloor x \rfloor < n \\
n \leq x \Leftrightarrow n \leq \lfloor x \rfloor
\end{aligned}
$$

  • 对于上取整函数,
    若$\lceil x \rceil = n$,有
    $$\
    \begin{aligned}
    n – 1 < x \leq n \\
    x \leq n < x + 1
    \end{aligned}
    $$
    若$x$是实数,$n$是整数,
    $$
    \begin{aligned}
    x \leq n \Leftrightarrow \lceil x\rceil \leq n\\
    n < x \Leftrightarrow n < \lceil x \rceil
    \end{aligned}
    $$

证明不难。

两者之间的关系:
$$
\big \lceil x \big \rceil – \big \lfloor x \big \rfloor = \big[ x \not \in Z\big ]
$$

两个结论
  • 对于实数 $x \ge 0$,有
    $$
    \Big \lfloor \sqrt{\lfloor x \rfloor}\Big \rfloor =\Big \lfloor \sqrt{x} \Big \rfloor
    $$

略证如下:令$LHS = m$,根据下取整函数的不等关系,
$$
m^2 \leq \lfloor x\rfloor < (m + 1)^2
$$
对于不等式左边,有$m^2 \leq x$,对于不等式右边,有$x < (m + 1)^2$ . 综合可以得到,
$$
m \leq \sqrt{x} < m + 1
$$
这样就得到了$LHS = RHS$

这个等式对于两边都是(包括根号内部)上取整的情形仍然成立。证明类似。

推广 对于定义在实数域上的连续单调递增函数$f(x)$,若$f(x)$有如下性质成立:
$$
f(x) = Integer \Rightarrow x = Integer
$$
那么
$$
\lfloor f(\lfloor x \rfloor) \rfloor = \lfloor f(x) \rfloor
$$
同样对于上取整也成立。

证明
如果$x = \lfloor x \rfloor$,则结论显然。
不然,则$x > \lfloor x \rfloor $,由于函数 $f$ 单调递增,
$$
f(x) > f(\lfloor x \rfloor)
$$
由于下取整函数单调不减,所以
$$
\lfloor f(x) \rfloor \ge \lfloor f(\lfloor x \rfloor) \rfloor
$$
如果$LHS > RHS$,那么由于$f$连续,必然存在 $\lfloor x \rfloor < y \leq x$,使得$f(y) = \lfloor f(x) \rfloor $,又因为$f$的整数性质,这使得$y$为一个整数。这和$y$ 的范围矛盾,所以假设不成立,即$LHS = RHS$。

由该性质的推广,可以立刻得到如下的式子成立,
$$
\lfloor \dfrac{x + m}{n} \rfloor = \lfloor \dfrac{\lfloor{x}\rfloor + m}{n}\rfloor
$$
其中 $m,n$ 是整数,并且 $ n > 0$ 。

关于区间的大小

若$n$ 为整数,

区间

$$
\alpha \leq n < \beta \Leftrightarrow \lceil \alpha \rceil \leq n < \lceil \beta \rceil
$$

$$
\alpha < n \leq \beta \Leftrightarrow \lfloor \alpha \rfloor < n \leq \lfloor \beta \rfloor
$$

相应的大小分别为$ \lceil \beta \rceil – \lceil \alpha \rceil $ 和$\lfloor \beta \rfloor – \lfloor \alpha \rfloor$。

这也对应了之前关于取整函数的几个不等关系。


$$
\sum_{i=0}^{c-1}{\bigg \lfloor \dfrac{ai + b}{c}\bigg \rfloor}
$$
其中整数 $c > 0$ 并且 $a$ 为整数。

引理
$$
\sum_{x=0}^{n}{\bigg\lfloor \dfrac{ax}{b} \bigg\rfloor} = \sum_{x=0}^{n}{\bigg\lfloor\dfrac{(a – \big\lfloor\dfrac{a}{b}\big\rfloor b) + \big\lfloor\dfrac{a}{b}\big\rfloor b}{b}x\bigg\rfloor} = \sum_{x=0}^{n}{(\big\lfloor\dfrac{a \bmod b}{b}x\big\rfloor + \big\lfloor\dfrac{a}{b}\big\rfloor x)}
$$
据此,把 $ai$ 改写成模 $c$ 的形式。
$$
\begin{aligned}
\sum_{i=0}^{c-1}{\bigg \lfloor \dfrac{ai + b}{c}\bigg \rfloor} &= \sum_{i=0}^{c-1}{\bigg \lfloor \dfrac{ai \bmod c + b}{c} \bigg \rfloor } + \sum_{i=0}^{c-1}{\dfrac{ai-ai\bmod c}{c}} \\
&= \dfrac{(c-1)a}{2}-\sum_{i=0}^{c-1}{\dfrac{ai\bmod c}{c}} + \sum_{i=0}^{c-1}{\bigg \lfloor \dfrac{ai \bmod c + b}{c} \bigg \rfloor }
\end{aligned}
$$

现在来考虑 $\sum_{i=0}^{c-1}{\dfrac{ai\bmod c}{c}}$ 。若 $ai \equiv aj \pmod c$,因此 $ai \bmod c$ 的出现周期为 $\dfrac{c}{(a,c)}$。令 $d = (a,c)$,则$ai \bmod c$ 恰好有 $d$ 组 ${0,d,2d,\cdots c – d}$。 这是因为$a = k_{1}d,\ c = k_{2}d$. $ai \bmod c = k_{1}di \bmod k_{2}d = d(k_{1}j) \bmod c$.

于是 $\sum_{i=0}^{c-1}{\dfrac{ai\bmod c}{c}} = \dfrac{0 + (c – d)}{2c}\times\dfrac{c}{d}d = \dfrac{c-d}{2}$

类似的,
$$
\begin{aligned}
\sum_{i=0}^{c-1}{\bigg \lfloor \dfrac{ai \bmod c + b}{c} \bigg \rfloor } &=d\sum_{x = 0}^{c/d – 1}{\bigg \lfloor \dfrac{x+ b / d}{c / d} \bigg \rfloor } \\
&= d\bigg \lfloor \dfrac{b}{d} \bigg\rfloor
\end{aligned}
$$
注意,这里我们用到了 $\big \lfloor mx\big \rfloor =\sum_{i=0}^{m-1}{\big \lfloor x + \dfrac{i}{m} \big \rfloor }$ 这个恒等式

这样我们最后就得到
$$
\sum_{i=0}^{c-1}{\bigg \lfloor \dfrac{ai + b}{c}\bigg \rfloor} = d\bigg\lfloor \dfrac{b}{d} \bigg\rfloor + \dfrac{a(c-1)}{2} + \dfrac{d – c}{2}
$$

这个式子还可以推广到递归的形式,

给定 $a,b,c,n \ (a,b,c,n \in N_{+})$ 求
$$
f(a,b,c,n) = \sum_{i = 0} ^{n}{\bigg \lfloor \dfrac{ai+b}{c}\bigg \rfloor}
$$

因此当 $a \ge c \ \texttt{||} \ b \ge c$ 时,
$$
\begin{aligned}
\sum_{i = 0} ^{n}{\bigg \lfloor \dfrac{ai+b}{c}\bigg \rfloor}
&= \sum_{i=0}^{n}{(\bigg\lfloor\dfrac{a \bmod c}{c}i\bigg\rfloor + \bigg\lfloor\dfrac{a}{c}\bigg\rfloor i + \bigg \lfloor \dfrac{b \bmod c}{c}\bigg \rfloor + \bigg \lfloor \dfrac{b}{c} \bigg \rfloor )} \\
&= \sum_{i=0}^{n}{(\bigg\lfloor\dfrac{(a \bmod c) i + b\bmod c}{c}\bigg\rfloor) + \dfrac{n(n+1)}{2}\bigg\lfloor\dfrac{a}{c}\bigg\rfloor + (n + 1)\bigg \lfloor \dfrac{b}{c} \bigg \rfloor} \\
&= f(a \bmod c,b \bmod c,c,n) + \dfrac{n(n+1)}{2}\bigg\lfloor\dfrac{a}{c}\bigg\rfloor + (n + 1)\bigg \lfloor \dfrac{b}{c} \bigg \rfloor
\end{aligned}
$$

这样问题被转化为 $a < c\ \texttt{&&}\ b < c$ 的情况。令 $m = \bigg \lfloor \dfrac {an + b}{c}\bigg \rfloor$ ,将贡献与条件做转化得到另一个形式的和式。
$$
\begin{aligned}
\sum_{i = 0} ^{n}{\bigg \lfloor \dfrac{ai+b}{c}\bigg \rfloor}
&=\sum_{i=0}^{n}\sum_{j=1}^{m}{\bigg [\big \lfloor \dfrac{ai+b}{c}\big \rfloor \ge j\bigg]} \\
&= \sum_{i=0}^{n}\sum_{j=1}^{m}{\bigg [ \dfrac{ai+b}{c}\ge j\bigg]} \\
&= \sum_{i=0}^{n}\sum_{j=1}^{m}{\bigg [ i > \dfrac{jc – b – 1}{a}\bigg]} \\
&= \sum_{j=1}^{m}\sum_{i=0}^{n}{\bigg [ i > \dfrac{jc – b – 1}{a}\bigg]} \\
&= \sum_{j=1}^{m}{(n – \bigg \lfloor \dfrac{jc- b-1}{a}\bigg \rfloor)} \\
&= mn – \sum_{j=0}^{m-1}{\bigg \lfloor \dfrac{jc+c- b-1}{a}\bigg \rfloor} \\
&= mn – f(c,c-b-1,a,m-1)
\end{aligned}
$$

发表评论