初級代數筆記

不等式

例題 1-1. $a, b\in R^+, \frac1a + \frac1b=1$，試證：對所有正整數 $n$，滿足：$(a+b)^n-a^n-b^n\ge 2^{2n}-2^{n+1}$.

  1. $\frac1a+\frac1b=1$
  2. $\frac{a+b}{ab}=1$
  3. $a+b = 1 -a b$

根據算數幾何不等式：$\forall a_i \ge 0,$ $$\frac{a_1+a_2+\dots+a_n}2\ge\sqrt[n]{a_1a_2\dots a_n}$$ 我們得知 $\frac1a + \frac1b \ge 2\sqrt{\frac1{ab}}$，因此 $2 \le \sqrt{ab}$，$ab\ge4$。 因此 $a^n+b^n \ge 2\sqrt{4^n} = 2^{n+1}$；接着我們知道 $a+b \ge 2\sqrt4=4$，因此 $(a+b)^n\ge4^n=2^{2n}$；最後得到結論：$$(a+b)^n-a^n-b^n\ge2^{2n}-2^{n+1}$$

例題 1-2. 假設 $a_1, \dots, a_n, b_1, \dots, b_n \in R^+$ 且滿足 $\Sigma_i^n{a_i}\le1$ 與 $\Sigma_i^n{a_n}\le n$，試證：$(\frac{1}{a_1}+\frac1{b_1})(\frac1{a_2}+\frac1{b_2})\dots(\frac1{a_n}+\frac1{b_n}) \ge (n+1)^n$.

  1. $\frac1{a_i}+\frac{1}{b_i}=n\cdot \frac1{na_i}+\frac{1}{b_i}\ge (n+1)\sqrt[n+1]{(\frac{1}{na_i})^n\frac1{b_i}}$
  2. $1 \ge \Sigma_i^n a_i \ge (n)\sqrt[n]{\Pi_i^na_i}$，因此 $\Pi_i^na_i \le ({\frac1n})^n$
  3. $n \ge \Sigma_i^n b_i \ge (n)\sqrt[n]{\Pi_i^na_i}$，因此 $\Pi_i^nb_i \le 1$
  4. $\Sigma_i^n{\frac1{a_i}+\frac{1}{b_i}} >= (n+1)^n \times \sqrt[n+1]{\frac1{\Pi_i^na_i}\cdot (\frac1{n})^n} \times \sqrt[n+1]{\frac1{\Pi_i^n{b_i}}} \ge (n+1)^n$

例題 1-3. 試證：$\lim_{n \to \infty} \sqrt[n]{n}=1$.

$\sqrt[n]{n}=\sqrt[n]{\sqrt{n}\times\sqrt{n}\times1\times1\times1\times\dots}\le \frac{1}n(2\sqrt{n}+n-2)=1+\frac{2\sqrt{n}-2}{n}$， 可得 $\sqrt{n}-1\le \frac{2\sqrt{n}-2}{n}$，根據嚴格極限定義得證。

例題 1-4. 對數列 $0 < a_1 < 1, a_{n+1} = \sqrt{a_n(3-a_n)}$，試證：數列 ${a_n}$ 單調遞增且存在上界。

先證明上界存在：$a_n + (3-a_n) \ge 2\sqrt{a_n(3-a_n)}$，因此存在上界 $\sqrt{a_n(3-a_n)} \le \frac{3}2$。 接着證明單調性：$a_{n+1}-a_n=\sqrt{a_n(3-a_n)}-\sqrt{a_n}=\sqrt{a_n}(\sqrt{3-a_n}-\sqrt{a_n})$，由於 $a_n \le 3/2$，因此恆正。

柯西不等式：$\forall a_i, b_j \in R$,$$(a_1b_1+a_2b_2+\dots+a_nb_n)^2\le(a_1^2+a_2^n+\dots+a_n^2)(b_1^2+b_2^n+\dots+b_n^2)$$

（題目待補）

生成函數

對於一個數列 ${a_n}$，它的生成函數定義爲：$$G(x) = \Sigma_{n=0}^na_nx^n$$ 例題 2-1. 數列 $a$ 滿足 $a_{n+1} = 2a_n + 1$，且 $a_0=0$，求 $a_n$ 的通項。

$a_{n+1} = 2a_n + 1$，兩邊同時乘上 $\Sigma_{n=0}^\infty{x^{n+1}}$，則有 $\Sigma_{n=0}^\infty a_{n+1}{x^{n + 1}} = \Sigma_{n=0}^\infty2a_n{x^{n+1}} + \Sigma_{n=0}^\infty{x^{n+1}}$； 設 $G(x) = \Sigma_{n=0}^\infty{a_n}{x^n}$：

  1. $G(x) - a_0 = 2xG(x)+\frac{x}{1-x}$.
  2. $(2x-1)G(X)=-\frac{x}{1-x}$
  3. $G(x)=\frac{x}{(1-2x)(1-x)} = x(\frac{2}{1-2x}-\frac{1}{1-x})$
  4. $G(x) = x(1 + 2x + (2x)^2 + (2x)^3 + \dots) - x(1 + x + x^2 + x^3 + \dots)$
  5. $G(x) = 0 + (2 - 1)x + (2 ^ 2 - 1)x^2 + (2 ^ 3 - 1)x^3 + \cdot$

例題 2-2. 數列 $a$ 滿足 $a_{n+1} = 2a_n + n$，且 $a_0=1$，求 $a_n$ 的通項。

一樣的處理方式，$\Sigma_{n=0}^\infty a_{n+1}x^{n+1} = \Sigma_{n=0}^\infty2a_n x^{n+1} + \Sigma_{n=0}^\infty nx^{n + 1}$：

  1. $G(x) - 1 = 2xG(x) + \frac{x^2}{(1-x)^2}$
  2. $(2x-1)G(x)=-\frac{x}{(1-x)^2}+1=\frac{2x^2-2x+1}{(1-x)^2}$
  3. $G(x)=\frac{1+2x-2x^2}{(1-x)^2(1-2x)}$
  4. 想辦法把 $G(x)$ 拆成 $\frac{a}{1-x} + \frac{b}{(1-x)^2} + \frac{c}{1-2x}$ 的形式，找到通解。

例題 2-3. 在 $n$ 種不同物品中選擇 $r$ 個（假設每種物品有無限多個），並且每種物品至少選擇一個，求取法數。

因爲每種物品都要取，而且沒有上限，因此每種物品的對應生成函數是 $G(x) = x + x^2 + x^3 + \dots$，彼此獨立，因此整體情況的生成函數是 $G(x) = (x + x^2 + x^3 + \dots)^n = (\frac{x}{1-x})^n$。

我們先求 $G^\prime(x) = \frac{1}{(1-x)^n}$ 的解，它其實是 $(1-x)^{-n}$，根據廣義二項式定理，其值等於 $\Sigma_{k=0}^{\infty}{\binom{n+k-1}{k}x^k}$；因此生成函數 $G(x) = \Sigma_{k=0}^{\infty}{\binom{n+k-1}{k}x^{n+k}}$。

其中，第 $r$ 項係數對應到 $n = r - k, k = r - n$，即爲 $\binom{r-1}{r-n}$。