標籤：

具體數學書籍數學遞歸

具體數學-第3課（遞歸式轉化為求和求解）

05-08

原文鏈接：

具體數學-第3課 - WeiYang Blog?

godweiyang.com

今天講了一種將遞歸式轉化為求和的方法。

考慮如下遞歸式：

${a_n}{T_n} = {b_n}{T_{n - 1}} + {c_n}$

兩邊同時乘以 $(sn)$ 得到：

${s_n}{a_n}{T_n} = {s_n}{b_n}{T_{n - 1}} + {s_n}{c_n}$

要想轉化成可以求和的遞歸式，那麼必須有：

${s_n}{b_n} = {s_{n - 1}}{a_{n - 1}}$

也就是：

${s_n} = frac { { {a_{n - 1}}{a_{n - 2}} cdots {a_1}}}{ { {b_n}{b_{n - 1}} cdots {b_2}}}$

這時令

${S_n} = {s_n}{a_n}{T_n}$

得到：

${S_n} = {S_{n - 1}} + {s_n}{c_n}$

這時就可以轉化為求和了，解出：

${S_n} = {s_0}{a_0}{T_0} + sumlimits_{k = 1}^n { {s_k}{c_k}}$

所以

${T_n} = frac{1}{ { {s_n}{a_n}}}({s_0}{a_0}{T_0} + sumlimits_{k = 1}^n { {s_k}{c_k}} )$

例題1

設 $(n)$ 個數快速排序的操作次數為 $C_n$ ，那麼有

$egin{array}{l}{C_0} = 0\{C_n} = n + 1 + frac{2}{n}sumlimits_{k = 0}^{n - 1} { {C_k}} ,n > 0end{array}$

用 $(n-1)$ 取代 $(n)$ 可以得到

${C_{n - 1}} = n + frac{2}{ {n - 1}}sumlimits_{k = 0}^{n - 2} { {C_k}} ,n > 1$

兩式相減可以得到

$egin{array}{l}{C_0} = 0\n{C_n} = (n + 1){C_{n - 1}} + 2n,n > 0end{array}$

由上面方法可以得到

${a_n} = n,{b_n} = n + 1,{c_n} = 2n$

所以

${s_n} = frac{2}{ {n(n + 1)}}$

進而可以求出

${C_n} = 2(n + 1)sumlimits_{k = 1}^n {frac{1}{ {k + 1}}}$

這裡介紹一個概念叫做調和級數：

${H_n} = 1 + frac{1}{2} + cdots + frac{1}{n} = sumlimits_{k = 1}^n {frac{1}{k}}$

所以

${C_n} = 2(n + 1){H_n} - 2n$

求和三大定律

結合律、分配率、交換律。這裡就不展開說了，相信你們都知道的。

來兩題簡單的例題說明一下。

例題2

求

$S = sumlimits_{0 le k le n} {(a + bk)}$

普通的方法每個人應該都會，等差數列嘛。這裡用求和定律來做一做。

用 $(n-k)$ 取代 $(k)$ ，得到

$S = sumlimits_{0 le n - k le n} {(a + b(n - k))}$

即

$S = sumlimits_{0 le k le n} {(a + b(n - k))}$

兩式相加得到

$2S = sumlimits_{0 le k le n} {(2a + bn)} = (2a + bn)sumlimits_{0 le k le n} 1 = (2a + bn)(n + 1)$

所以

$S = (2a + bn)(n + 1)/2$

例題3

求

$S = sumlimits_{0 le k le n} {k{x^k}}$

這裡用到另一種求和的方法。

兩邊同時加上第 $n+1$ 項，得到

$egin{array}{l}S + (n + 1){x^{n + 1}}\ = sumlimits_{0 le k le n + 1} {k{x^k}} \ = sumlimits_{1 le k le n + 1} {k{x^k}} \ = sumlimits_{0 le k le n} {(k + 1){x^{k + 1}}} \ = xsumlimits_{0 le k le n} {(k{x^k} + {x^k})} \ = xS + xsumlimits_{0 le k le n} { {x^k}} \ = xS + xfrac{ {1 - {x^{n + 1}}}}{ {1 - x}}end{array}$

所以

$S = frac{ {x - (n + 1){x^{n + 1}} + n{x^{n + 2}}}}{ { { {(1 - x)}^2}}}$

這裡介紹另一種方法來求解。

令

$f(x) = sumlimits_{0 le k le n} { {x^k}} = frac{ {1 - {x^{n + 1}}}}{ {1 - x}}$

求導得到

$f(x) = sumlimits_{0 le k le n} {k{x^{k - 1}}} = frac{1}{x}S$

所以

$frac{1}{x}S = frac{ {partial f}}{ {partial x}}(frac{ {1 - {x^{n + 1}}}}{ {1 - x}}) = frac{ {1 - (n + 1){x^n} + n{x^{n + 1}}}}{ { { {(1 - x)}^2}}}$

同樣可以得到

$S = frac{ {x - (n + 1){x^{n + 1}} + n{x^{n + 2}}}}{ { { {(1 - x)}^2}}}$

推薦閱讀：

※二重積分
※練習雜選第3期
※阿貝爾獎真是個雞肋
※練習雜選第2期
※糖水不等式還能這麼用？！解決變壓器等匝變化的神器。

TAG:具體數學書籍 | 數學 | 遞歸 |