### 1. ($\S 4.1\ ex. 4.9$)

\begin{aligned}
H_1 &= 1 \\
H_2 &= 1+\dfrac{1}{2} \\
H_3 &= 1+\dfrac{1}{2}+\dfrac{1}{3} \\
.\\.\\. \\
H_n &= 1+\dfrac{1}{2}+\dfrac{1}{3}+...+\dfrac{1}{n}\ ,for\ each \ n\in\mathbb{Z}^+ \\
\sum_{j=1}^{n}H_j&=(n+1)H_n-n
\end{aligned}

:::spoiler proof
基礎: $當\ n=1\ 時，$
\begin{aligned}
\sum_{j=1}^{1}H_j&=H_1=(1+1)H_1-1
\end{aligned}
假設：if $n=k$ that：
\begin{aligned}
\sum_{j=1}^{k}H_j&=(k+1)H_k-k\ \ \ is\ true
\end{aligned}
推論：
\begin{aligned}
\sum_{j=1}^{k+1}H_j=\sum_{j=1}^{k}H_j+H_{k+1}&=(k+1)H_k-k+H_{k+1}\\
&=(k+1)(H_{k+1} − \dfrac{1}{k + 1}) − k + H_{k+1}\\
&=(k+2)H_{k+1}-1-k\\
&=(k+2)H_{k+1}-(k+1)
\end{aligned}
基於數學歸納法原理，原式得証。
:::

### 2.
$(a)\ \sum\limits_{j = 1}^{n}(2j-1)^2=1^2+3^2+...+(2n-1)^2=\dfrac{n(2n+1)(2n-1)}{3}$
$(b)\ \sum\limits_{j = 1}^{n}j^3=1^3+2^3+...+n^3=\dfrac{n^2(n+1)^2}{4}=\left(\dfrac{n(n+1)}{2}\right)^2=\left(\sum\limits_{j=1}^{n}j\right)^2$

:::spoiler proof
(a)
$n=1$時，$\sum\limits_{j = 1}^{1}(2j-1)^2=1^2=\dfrac{1(2+1)(2-1)}{3}$ 成立。
假設 $n=k \ge1$ 時成立，即$\sum\limits_{j = 1}^{k}(2j-1)^2=\dfrac{k(2k+1)(2k-1)}{3}$
當 $n=k+1$ 時，
\begin{aligned}
\sum_{j = 1}^{k+1}(2j-1)^2&=[1^2+3^2+...+(2k-1)^2]+[2(k+1)-1]^2\\
&=\dfrac{k(2k+1)(2k-1)}{3}+[2(k+1)-1]^2\\
&=\dfrac{k(2k+1)(2k-1)}{3}+(2k+1)^2\\
&=\dfrac{k(2k+1)(2k-1)+3(2k+1)^2}{3}\\
&=\dfrac{(2k+1)[k(2k-1)+3(2k+1)]}{3}\\
&=\dfrac{(2k+1)(2k^2-k+6k+3)}{3}\\
&=\dfrac{(2k+1)(2k^2+5k+3)}{3}\\
&=\dfrac{(2k+1)(k+1)(2k+3)}{3}\\
&=\dfrac{(k+1)[2(k+1)+1][2(k+1)-1]}{3}
\end{aligned}
基於數學歸納法原理，原式得証。

(b)
$n=1$時，$\sum\limits_{j = 1}^{1}j^3=1^3=\dfrac{1^2(1+1)^2}{4}$ 成立。
假設 $n=k \ge1$ 時成立，即$\sum\limits_{j = 1}^{k}j^3=\dfrac{k^2(k+1)^2}{4}=\left(\sum\limits_{j=1}^{k}j\right)^2$
當 $n=k+1$ 時，
\begin{aligned}
\sum_{j = 1}^{k+1}j^3&=(1^3+2^3+...+k^3)+(k+1)^3\\
&=\dfrac{k^2(k+1)^2}{4}+(k+1)^3\\
&=\dfrac{k^2(k+1)^2+4(k+1)^3}{4}\\
&=\dfrac{(k+1)^2(k^2+4k+4)}{4}\\
&=\dfrac{(k+1)^2(k+2)^2}{4}\\
&=\dfrac{(k+1)^2[(k+1)+1]^2}{4}\\
&=\left(\dfrac{(k+1)[(k+1)+1]}{2}\right)^2\\
&=\left(\sum_{j=1}^{k+1}j\right)^2
\end{aligned}
基於數學歸納法原理，原式得証。
:::

### 3.

$(a)S(n):2^n<n!，證明所有大於\ 3\ 的整數\ n，S(n)均成立。$

$(b)S(n):n^2<2^n，證明所有大於\ 4\ 的整數\ n，S(n)均成立。$

$(c)S(n):n^3<2^n，找出最小的正整數\ n_0，然後證明所有大於\ n_0\ 的整數\ n，S(n)均成立。$

:::spoiler proof
$(a)$
$2^n<n!，n>3，即\ n\ge4。$
當 $n=4$ 時，$2^4=16<4!$，成立。
假設 $n=k\ge4$ 時成立，即 $2k<k!$。
當 $n=k+1$ 時，$2^{k+1}=2\times2^k<2\times k!<(k+1)\times k!=(k+1)!$
故由數學歸納法得證$S(n)$成立。

$(b)$
$n^2<2^n，n\ge5。$
當 $n=5$ 時，$5^2<2^5$，成立。
假設 $n=k\ge5$ 時成立，即 $k^2<2^k$。
當 $n=k+1$ 時，$(k+1)^2=k^2+2k+1<2^k+2k+1<2^k+2^k=2^{k+1}$
即 $(k+1)^2<2^{k+1}$ ，需補上 $(2k+1)<2^k$ 的證明，因已假設$k^2<2^k$，故證明 $(2k+1)<k^2$ 即可，當 $n\ge5$ 時，$(2k+1)<k^2$ 明顯成立，
故得證$S(n)$成立。

$(c)$
$n^3<2^n$
當 $n=10$ 時，$10^3<2^10$，故 $n_0=10$ 為讓 $S(n)$ 成立最小的 $n$ 值。
假設 $n=k\ge10$ 時成立，即 $k^3<2^k$。
當 $n=k+1$ 時，$(k+1)^3=k^3+3k^2+3k+1<2^k+3k^2+3k+1<2^k+2^k=2^{k+1}$
同樣需補上 $3k^2+3k+1<2^k$ 的證明，因已假設$k^3<2^k$，故證明 $3k^2+3k+1<k^3$ 即可，當 $n\ge10$ 時，$3k^2+3k+1<k^3$ 明顯成立，
故得證$S(n)$成立。
:::

### 4.

(a) $\sum\limits_{j = 1}^{n}2^{j-1} (= 2^0+2^1+2^2+... +2^{n-1}) = 2^n-1$
:::spoiler solution
基礎：當 $n=1$ 時，<br>$\qquad\quad\sum\limits_{j = 1}^{n}2^{j-1} =\sum\limits_{j = 1}^{1}2^{j-1} = 2^{1-1}=2^0= 1 = 2^1-1= 2^n-1$，原式成立。
假設：當 $n=k$ 時，該式成立：<br>
$\qquad\quad\sum\limits_{j = 1}^{n}2^{j-1}=\sum\limits_{j = 1}^{k}2^{j-1} = 2^0+2^1+2^2+... +2^{k-1} = 2^k-1$。
推論：當 $n=k+1$ 時，<br>$\qquad\quad\sum\limits_{j = 1}^{n}2^{j-1} = \sum\limits_{j = 1}^{k+1}2^{j-1} = 2^{1-1}+2^{2-1}+2^{3-1}+... +2^{k-1}+2^{(k+1)-1}$
$\qquad\qquad= (2^0+2+2^2+... +2^{k-1})+2^{k} = 2^k-1+2^k$ $\qquad\qquad= 2\times 2^k-1 = 2^{k+1}-1=2^n-1$。<br>$\qquad\quad$可知該式亦成立。
基於數學歸納法原理可得原式成立。
:::
(b) $\sum\limits_{j = 1}^{n}j\times2^{j-1} (= 1\times2^0+2\times2^1+3\times2^2+... +n\times2^{n-1}) = (n-1)\times2^n+1$
:::spoiler solution
基礎：當 $n=1$ 時，<br>$\qquad\quad\sum\limits_{j = 1}^{1}j\times2^{j-1} = 1\times2^{1-1}=1\times2^0= 1 = (1-1)\times2^1+1$，原式成立。
假設：當 $n=k$ 時，該式成立：<br>$\qquad\quad\sum\limits_{j = 1}^{k}j\times2^{j-1} = 1\times2^0+2\times2^1+3\times2^2+... +k\times2^{k-1} = (k-1)\times2^k+1$。
推論：當 $n=k+1$ 時，<br>$\qquad\quad\sum\limits_{j = 1}^{k+1}j\times2^{j-1} = 1\times2^0+2\times2^1+3\times2^2+... +k\times2^{k-1}+(k+1)\times2^{k}$
$\qquad\qquad= (k-1)\times2^k+1+(k+1)\times2^{k} = 2^k(k-1+k+1)+1$ $\qquad\qquad= 2k\times 2^k+1 =k\times2^{k+1}+1 (=((k+1)-1)\times2^{k+1}+1 )$。<br>$\qquad\quad$可知該式亦成立。
基於數學歸納法原理，原式得証。
:::

### 5.

$\sum\limits_{i=0}^{n}F_i^2=F_n\times F_{n+1}\ ,\ n\ge1$

基礎：$n=1$ 時，
\begin{aligned}
\sum\limits_{i=0}^{1}F_i^2=0^2+1^2=1\times 1=F_1\times F_2\ 成立。
\end{aligned}
假設：$n=k$ 時，該式成立。
\begin{aligned}
\sum\limits_{i=0}^{k}F_i^2=F_k\times F_{k+1}
\end{aligned}
推論：$n=k+1$ 時，
\begin{aligned}
\sum\limits_{i=0}^{k+1}F_i^2&=\sum_{i=0}^{k}F_i^2+ F^2_{k+1}=F_k\times F_{k+1}+ F^2_{k+1}\\
&=(F_{k}+F_{k+1})\times F_{k+1}\\
&=F_{k+2}\times F_{k+1}\\
&=F_{k+1}\times F_{k+2}
\end{aligned}
基於數學歸納法原理，原式得証。

### 1. ($\S 4.2\ \sharp 1$)

Give a recursive definition for each of the following integer sequences $c_1, c_2, c_3,...,$
where for all $n\in\mathbb{Z}^+$ we have

\begin{aligned}
&(a)\ c_n= 7n \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (b)\ c_n= 7^n\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (c)\ c_n= 3n+7 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (d)\ c_n= 7\\
&(e)\ c_n= n^2 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (f) \ c_n= 2-(-1)^n
\end{aligned}

:::spoiler 中文
用遞迴方式定義以上數列
:::

:::spoiler solution
$(a)\begin{cases}c_1= 7\\c_{n+1}=c_n+7\ ,for\ n\ge1\end{cases}$

$(b)\begin{cases}c_1= 7\\c_{n+1}=7c_n\ ,for\ n\ge1\end{cases}$

$(c)\begin{cases}c_1= 10\\c_{n+1}=c_n+3\ ,for\ n\ge1\end{cases}$

$(d)\begin{cases}c_1= 7\\c_{n+1}=c_n\ ,for\ n\ge1\end{cases}$

$(e)\begin{cases}c_1= 1\\c_{n+1}=c_n+2n+1\ ,for\ n\ge1\end{cases}$

$(f)\begin{cases}c_1= 3\ ,\ c_2=1\\c_{n+2}=c_n\ ,for\ n\ge1\end{cases}$
:::

證明以下式子。
1. $\sum\limits_{i=0}^{n}F_i=F_{n+2}-1$
2. $\sum\limits_{i=1}^{n}\dfrac{F_{i-1}}{2^i}=1-\dfrac{F_{n+2}}{2^n}$
3. $\sum\limits_{i=1}^{n}L_i^2=L_iL_{i+1}-2$ , $L_n=\begin{cases}2& \text{if n=0}\\1& \text{if n=1}\\L_{n-1}+L_{n-2}& \text{otherwise}\end{cases}$