特征方程法解一階線性代數遞推式
數列{ a n a_n an}滿足 a 1 = b , a n + 1 = c a n + d a_1=b,a_{n+1}=ca_n+d a1=b,an+1=can+d，求該數列的通項公式
針對遞推關系式作出一個特征方程 x = c x + d x=cx+d x=cx+d
定理：設上述遞推關系式的特征方程根為 x 0 x_0 x0
- 當 x 0 = a 1 x_0=a_1 x0=a1時， a n = a 1 a_n=a_1 an=a1
- 當 x 0 ≠ a 1 x_0\neq a_1 x0=a1時， a n = b n + x 0 , b n = b 1 c n − 1 , b 1 = a 1 − x 0 a_n=b_n+x_0,b_n=b_1c^{n-1},b_1=a_1-x_0 an=bn+x0,bn=b1cn−1,b1=a1−x0
證明2：
∵ c ≠ 0 , 1 \because c\neq 0,1 ∵c=0,1
得 x 0 = d 1 − c x_0=\frac{d}{1-c} x0=1−cd
作換元 b n = a n − x 0 b_n=a_n-x_0 bn=an−x0，
∴ b n + 1 = a n + 1 − x 0 = c a n + d − d 1 − c = c a n − c d 1 − c = c ( a n − x 0 ) = c b n \therefore b_{n+1}=a_{n+1}-x_0=ca_n+d-\frac{d}{1-c}=ca_n-\frac{cd}{1-c}=c(a_n-x_0)=cb_n ∴bn+1=an+1−x0=can+d−1−cd=can−1−ccd=c(an−x0)=cbn
特征方程法解二階線性代數遞推式
有數列{ a n a_n an}，遞推公式為 a n + 2 = p a n + 1 + q a n , a 1 = α , a 2 = β a_{n+2}=pa_{n+1}+qa_n,a_1=\alpha,a_2=\beta an+2=pan+1+qan,a1=α,a2=β
特征方程為 x 2 − p x − q = 0 x^2-px-q=0 x2−px−q=0
- 當 x 1 ≠ x 2 x_1\neq x_2 x1=x2時， a n = A x 1 n − 1 + B x 2 n − 1 a_n=Ax_1^{n-1}+Bx_2^{n-1} an=Ax1n−1+Bx2n−1
- 當 x 1 = x 2 x_1=x_2 x1=x2時， a n = ( A + B ) x 1 n − 1 a_n=(A+B)x_1^{n-1} an=(A+B)x1n−1
(以上兩式中的 A , B A,B A,B由 a 1 = α , a 2 = β a_1=\alpha,a_2=\beta a1=α,a2=β決定)
當然解高階線性代數都可以用疊代法
斐波那契數列 f ( n + 2 ) = f ( n + 1 ) + f ( n ) f(n+2)=f(n+1)+f(n) f(n+2)=f(n+1)+f(n)的特征方程為 x 2 − x − 1 = 0 x^2-x-1=0 x2−x−1=0，得 x = 1 ± 5 2 x=\frac{1\pm\sqrt{5}}{2} x=21±5
真題
T ( n ) = 2 T ( n 2 ) + 2 n T(n)=2T(\frac{n}{2})+2n T(n)=2T(2n)+2n
= 2 ( 2 T ( n 4 ) + 2 × n 2 ) + 2 n =2(2T(\frac{n}{4})+2\times\frac{n}{2})+2n =2(2T(4n)+2×2n)+2n
= 4 T ( n 4 ) + 2 n + 2 n =4T(\frac{n}{4})+2n+2n =4T(4n)+2n+2n
= 4 ( 2 T ( n 8 ) + 2 × n 4 ) + 2 n + 2 n =4(2T(\frac{n}{8})+2\times \frac{n}{4})+2n+2n =4(2T(8n)+2×4n)+2n+2n
= 8 T ( n 8 ) + 2 n + 2 n + 2 n =8T(\frac{n}{8})+2n+2n+2n =8T(8n)+2n+2n+2n
猜想 T ( n ) = 2 k T ( n 2 k ) + 2 n × k T(n)=2^kT(\frac{n}{2^k})+2n\times k T(n)=2kT(2kn)+2n×k
當 n 2 k = 1 \frac{n}{2^k}=1 2kn=1時， n = 2 k , k = l o g 2 n n=2^k,k=log_2n n=2k,k=log2n
∴ T ( n ) = 2 k T ( 1 ) + 2 n × k = a n + 2 n l o g 2 n \therefore T(n)=2^kT(1)+2n\times k=an+2nlog_2n ∴T(n)=2kT(1)+2n×k=an+2nlog2n
故選B
這個的疊代就很簡單了，選D
同理， T ( n ) = 2 k T ( n 4 k ) + k n T(n)=2^kT(\frac{n}{4^k})+k\sqrt{n} T(n)=2kT(4kn)+kn
n = 4 k , 2 k = n , k = l o g 2 n 2 n=4^k,2^k=\sqrt{n},k=\frac{log_2n}{2} n=4k,2k=n
,k=2log2n
T ( n ) = n + n 2 l o g 2 n T(n)=\sqrt{n}+\frac{\sqrt{n}}{2}log_2\sqrt n T(n)=n
+2n
log2n
顯然答案為C
特征方程為 2 x 2 − x − 1 = 0 2x^2-x-1=0 2x2−x−1=0
得 x 1 = − 1 2 , x 2 = 1 x_1=-\frac{1}{2},x_2=1 x1=−21,x2=1
a 1 = A + B = 0 , a 2 = A x 1 + B x 2 = − 1 2 A + B = 1 a_1=A+B=0,a_2=Ax_1+Bx_2=-\frac{1}{2}A+B=1 a1=A+B=0,a2=Ax1+Bx2=−21A+B=1
解得 A = − 2 3 , B = 2 3 A=-\frac{2}{3},B=\frac{2}{3} A=−32,B=32
a n = − 2 3 × ( − 1 2 ) n − 1 + 2 3 × 1 n − 1 a_n=-\frac{2}{3}\times(-\frac{1}{2})^{n-1}+\frac{2}{3}\times1^{n-1} an=−32×(−21)n−1+32×1n−1
lim n → + ∞ a n = 2 3 {\lim_{n \to +\infty}}a_n=\frac{2}{3} n→+∞liman=32
選擇B
下面是一道…神題…？其實也沒這麼難
一樣的疊代
T ( n ) = 2 T ( n 2 ) + n l o g 2 n T(n)=2T(\frac{n}{2})+nlog_2n T(n)=2T(2n)+nlog2n
T ( n 2 ) = 2 T ( n 4 ) + n 2 ( l o g 2 n − 1 ) T(\frac{n}{2})=2T(\frac{n}{4})+\frac{n}{2}(log_2n-1) T(2n)=2T(4n)+2n(log2n−1)
T ( n 4 ) = 2 T ( n 8 ) + n 4 ( l o g 2 n − 2 ) T(\frac{n}{4})=2T(\frac{n}{8})+\frac{n}{4}(log_2n-2) T(4n)=2T(8n)+4n(log2n−2)
T ( n ) = 2 ( 2 T ( n 4 ) + n 2 ( l o g 2 n − 1 ) ) + n l o g 2 n T(n)=2(2T(\frac{n}{4})+\frac{n}{2}(log_2n-1))+nlog_2n T(n)=2(2T(4n)+2n(log2n−1))+nlog2n
= 4 T ( n 4 ) + n ( l o g 2 n − 1 ) + n l o g 2 n =4T(\frac{n}{4})+n(log_2n-1)+nlog_2n =4T(4n)+n(log2n−1)+nlog2n
= 4 ( 2 T ( n 8 ) + n 4 ( l o g 2 n − 2 ) ) + n ( l o g 2 n − 1 ) + n l o g 2 n =4(2T(\frac{n}{8})+\frac{n}{4}(log_2n-2))+n(log_2n-1)+nlog_2n =4(2T(8n)+4n(log2n−2))+n(log2n−1)+nlog2n
= 8 T ( n 8 ) + n ( l o g 2 n − 2 ) + n ( l o g 2 n − 1 ) + n l o g 2 n =8T(\frac{n}{8})+n(log_2n-2)+n(log_2n-1)+nlog_2n =8T(8n)+n(log2n−2)+n(log2n−1)+nlog2n
= 8 T ( n 8 ) + 3 n l o g 2 n − 2 n − n =8T(\frac{n}{8})+3nlog_2n-2n-n =8T(8n)+3nlog2n−2n−n
= 2 k T ( n 2 k ) + k n l o g 2 n − k ( k − 1 ) 2 n =2^kT(\frac{n}{2^k})+knlog_2n-\frac{k(k-1)}{2}n =2kT(2kn)+knlog2n−2k(k−1)n
當 n 2 k = 1 , n = 2 k , k = l o g 2 n \frac{n}{2^k}=1,n=2^k,k=log_2n 2kn=1,n=2k,k=log2n時
T ( n ) = n + n l o g 2 n − 1 2 l o g 2 n T(n)=n+nlog^2n-\frac{1}{2}log^2n T(n)=n+nlog2n−21log2n
選C
更新：時隔一年，NOIp死了，CSP-J/S活了，LZ也來更一次部落格以示尊重
（下面假設T(1)=1）
根據疊代的思想 T ( n ) = n log 2 2 n + 2.5 × ( 2 n / 5 ) log 2 2 n + 2. 5 2 × ( 2 / 5 ) 2 log 2 2 n + . . . T(n)=n\log_2^2n+2.5\times (2n/5)\log_2^2n+2.5^2\times (2/5)^2\log_2^2n+... T(n)=nlog22n+2.5×(2n/5)log22n+2.52×(2/5)2log22n+...
= n log 2 2 n + n log 2 2 n + n log 2 2 n + . . . ( log 2 n 個 ) =n\log_2^2n+n\log_2^2n+n\log_2^2n+...(\log_2n個) =nlog22n+nlog22n+nlog22n+...(log2n個)
= n log 2 3 n =n\log_2^3n =nlog23n
這裡可以發現 T ( n ) T(n) T(n)最終比 n log 2 2 n n\log_2^2n nlog22n多了一個 log \log log
為了對比，我們再看一道題
發現與上面 2.5 × 2 n / 5 = n 2.5\times 2n/5=n 2.5×2n/5=n不同的是 3 n / 4 < n 3n/4<n 3n/4<n了，會有什麼不同呢？
依舊疊代 T ( n ) = n log 2 n + ( 3 n / 4 ) log 2 n + ( 3 4 ) 2 n log 2 n + . . . T(n)=n\log_2n+(3n/4)\log_2n+(\frac{3}{4})^2n\log_2n+... T(n)=nlog2n+(3n/4)log2n+(43)2nlog2n+...
= ( 1 + 3 4 + ( 3 4 ) 2 + . . . ) n log 2 n =(1+\frac{3}{4}+(\frac{3}{4})^2+...)n\log_2n =(1+43+(43)2+...)nlog2n
根據收斂原則 T ( n ) = 1 1 − 3 4 × n log 2 n = 4 n log 2 n T(n)=\frac{1}{1-\frac{3}{4}}\times n\log_2n=4n\log_2n T(n)=1−431×nlog2n=4nlog2n
發現4是個沒用的常數
是以 T ( n ) = n log 2 n T(n)=n\log_2n T(n)=nlog2n
為什麼在這裡我們就發現 T ( n ) T(n) T(n)和 n log 2 n n\log_2n nlog2n是同階的了呢
原因在于：
- 在前一題中 2.5 × 2 5 = 1 2.5\times \frac{2}{5}=1 2.5×52=1是不收斂的，這樣的東西一共有 log 2 \log_2 log2項，是以多了一個 log \log log
- 而後一題中 3 / 4 < 1 3/4<1 3/4<1是收斂的，最終收斂于一個常數可以被省略，是以什麼都沒有多
-
那麼當 k / m > 1 k/m>1 k/m>1時， T ( n ) = ( 1 + k m + ( k m ) 2 + . . . + ( k m ) log m n ) n log 2 n T(n)=(1+\frac{k}{m}+(\frac{k}{m})^2+...+(\frac{k}{m})^{\log_mn})n\log_2n T(n)=(1+mk+(mk)2+...+(mk)logmn)nlog2n（假設給定的是 T ( n ) = k T ( n / m ) + n log 2 n T(n)=kT(n/m)+n\log_2n T(n)=kT(n/m)+nlog2n）
= ( 1 − ( k m ) log m n 1 − k m ) n log 2 n = ( k log m n n ) × n log 2 n =(\frac{1-(\frac{k}{m})^{\log_mn}}{1-\frac{k}{m}})n\log_2n=(\frac{k^{\log_mn}}{n})\times n\log_2n =(1−mk1−(mk)logmn)nlog2n=(nklogmn)×nlog2n
= k log m n log 2 n =k^{\log_mn}\log_2n =klogmnlog2n