令函數 $f: \mathbb{N} \to (0,\infty)$,則下列等式成立
$$
\min_{0 \leq k \leq N} \frac{f(k)}{\max_{i\leq k}f(i)} = \min_{0\leq \ell \leq k \leq N} \frac{f(k)}{f(\ell)}
$$
Proof: 令
$$\frac{f(k_0)}{f(\ell_0)} := \min_{0\leq k\leq N}\frac{f(k)}{ \max_{i\leq k} f(i)}
$$ 其中 $\ell_0\leq k_0$ 使得 $\text{min}_{0\leq\ell\leq k\leq N}\frac{f(k)}{f(\ell)}\leq\frac{f(k_0)}{f(\ell_0)}$。
另一方面,令
$$\frac{f(k_1)}{f(\ell_1)}= \min_{0\leq\ell\leq k\leq N}\frac{f(k)}{f(\ell)}
$$ 且 $\ell_1\leq k_1$,則我們必定有
$$\frac{f(k_0)}{f(\ell_0)}\leq\frac{f(k_1)}{ \max_{i\leq k_1}\;f(i)}\leq\frac{f(k_1)}{f(\ell_1)}$$
由上述結果,我們得到
$$
\frac{f(k_0)}{f(\ell_0)}=\frac{f(k_1)}{f(\ell_1)}
$$ 亦即
$$\min_{0\leq k\leq N}\frac{f(k)}{ \max_{i\leq k} f(i)}= \min_{0\leq\ell\leq k\leq N}\frac{f(k)}{f(\ell)}$$ 至此得證。$\square$
$$
\min_{0 \leq k \leq N} \frac{f(k)}{\max_{i\leq k}f(i)} = \min_{0\leq \ell \leq k \leq N} \frac{f(k)}{f(\ell)}
$$
Proof: 令
$$\frac{f(k_0)}{f(\ell_0)} := \min_{0\leq k\leq N}\frac{f(k)}{ \max_{i\leq k} f(i)}
$$ 其中 $\ell_0\leq k_0$ 使得 $\text{min}_{0\leq\ell\leq k\leq N}\frac{f(k)}{f(\ell)}\leq\frac{f(k_0)}{f(\ell_0)}$。
另一方面,令
$$\frac{f(k_1)}{f(\ell_1)}= \min_{0\leq\ell\leq k\leq N}\frac{f(k)}{f(\ell)}
$$ 且 $\ell_1\leq k_1$,則我們必定有
$$\frac{f(k_0)}{f(\ell_0)}\leq\frac{f(k_1)}{ \max_{i\leq k_1}\;f(i)}\leq\frac{f(k_1)}{f(\ell_1)}$$
由上述結果,我們得到
$$
\frac{f(k_0)}{f(\ell_0)}=\frac{f(k_1)}{f(\ell_1)}
$$ 亦即
$$\min_{0\leq k\leq N}\frac{f(k)}{ \max_{i\leq k} f(i)}= \min_{0\leq\ell\leq k\leq N}\frac{f(k)}{f(\ell)}$$ 至此得證。$\square$
留言
張貼留言