Post Reply 
 
Thread Rating:
  • 3 Votes - 4.33 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Linear recursion (constent coefficients) 线性递归序列
02-17-2010, 02:43 PM
Post: #1
Linear recursion (constent coefficients) 线性递归序列
中文连接Chinese
For \(k \geq 2\) and constants \(c_0, c_1, \cdots, c_k \in \mathbf{C}\) with \(c_k \neq 0\), the recursion relation
(\(\star \)) \(\quad\quad\quad\quad\quad c_k a_{n+k-1} + \cdots + c_1 a_n + c_0 = 0 \quad\quad\quad\quad (\forall n \in \mathbf{N}_0=\left\{n \in \mathbf{Z}:n\geq 0\right \})\)
defines a family of sequences \(\left\{ \left\{a_n\right \} \in \mathbf{C}^{\mathbf{N}_0}: c_k a_{n+k-1} + \cdots + c_1 a_n + c_0 = 0 \quad\quad(\forall n \in \mathbf{N}_0)\right\} \)

We call
(0.1) \(P(x) = c_k x^{k-1} + \cdots + c_2 x + c_1\) the characteristic polynomial of (\(\star \))
(0.2) \(c_k a_{n+k-1} + \cdots + c_1 a_n = 0\) the homogeneous part of (\(\star \))

We claim that
(1) If \(\xi\) is a root of \(P(x)\) and \(\left\{\beta_n\right \}\) satisfies (\(\star \)), then \(\left\{\xi^n\right \}\) satisfies (0.2)
hence \(a_n = \xi^n + \beta_n\) satisfies the recursion (\(\star \))
(2) If \(\xi\) is a \(r\)-fold zero of \(P(x)\), then \(a_n = n^d \xi^n\) satisfies (0.2) for any fixed \(d \in \left\{0,\cdots,r-1\right \}\)
(3) (\(\star \)) has a solution of the form \(\beta_n = \gamma n^p\) for some constant \(\gamma\) and \(p \in \mathbf{N}_0\).

(1)~(3) implies that the general solution of (\(\star \)) has the form:\[a_n = \sum_{i=1}^{m} \xi_{i}^n (\sum_{j=0}^{r_i-1}\alpha_{i,j}n^j) + \gamma n^p\] where \(\alpha_{i,j}\) are constants, \(\xi_i\) is \(r_i\)-fold zero of \(P(x)\) and \(r_1+\cdots+r_m = k-1\).

Proof of (2): We have \(P^{(j)}(\xi) = 0, \quad j=\overline{0,r-1}\) since \(\xi\) is a \(r\)-fold zero of \(P(x)\).
Clearly \(c_k \xi^{n+k-1} + \cdots + c_1 \xi^n = \xi^n P(\xi) = 0\) i.e. \(\left\{n^0 \xi^n\right \}\) satisties (0.2).
Assume
(p.1) \(\left\{n^d \xi^n\right \}\) satisfies (0,2) when \(0\leq d<q\leq r-1\) for some \(q\),
then \[\begin{align} 0&=\frac{d^q}{dx^q} (x^q P(x)) |_{x=\xi}= \sum_{j=1}^k c_j \xi^{j-1}\left((q+j-1)\cdots j\right)= \sum_{j=1}^k c_j \xi^{j-1}(j^q + Q(j)) \\
&= \sum_{j=1}^k c_j \xi^{j-1}j^q = \sum_{j=1}^k c_j j^q \xi^{j-1} \end{align}\] this is because that \(Q(j)\) is a polynomial with degree less then \(q\) and our assumption (p.1) and the expected result follows.
Proof of (3). Consider \(\begin{pmatrix} d_1\\ d_2\\ \vdots\\ d_k \end{pmatrix}=\begin{pmatrix}
1 & 1 & \cdots &1 \\ 1 & 2 & \cdots & k \\ \vdots & \vdots & \ddots & \vdots \\
1 & 2^{k-1} & \cdots & k^{k-1} \end{pmatrix} \begin{pmatrix} c_1\\ c_2\\ \vdots\\ c_k
\end{pmatrix}\). Since the mapping matrix is invertible and \((c_1,\cdots, c_k)^{T} \neq \mathbf{0}\),, there is some \(p \in \left\{0,\cdots,k-1\right \}\) such that \(d_{p+1} = \sum_{j=1}^k j^p c_j \neq 0\) while \(d_i = 0, \quad i < p+1\) thus \[\begin{align} \sum_{j=1}^k c_j (m+j)^p& = \sum_{j=1}^k c_j \sum_{i=0}^p \begin{pmatrix}p \\i \end{pmatrix} m^{p-i} j^i = \sum_{i=0}^p \begin{pmatrix}p \\i \end{pmatrix} m^{p-i} \sum_{j=1}^k j^i c_j\\ & = \sum_{i=0}^p \begin{pmatrix}p \\i \end{pmatrix} m^{p-i} d_{i+1} = d_{p+1}\end{align}\] Let \(\beta_n = \gamma n^p, \; m = n-1\) with \(\gamma = - c_0/d_{p+1}\), we then get \[\begin{align} c_k \beta_{n+k-1} + \cdots + c_1 \beta_n + c_0 & = \gamma(c_k (m+k)^p + \cdots+c_1 (m+1)^p) + c_0\\ & = \gamma d_{p+1} + c_0 = 0 \end{align}\]and we see that (3) is true.
Find all posts by this user
Quote this message in a reply
02-24-2010, 06:06 PM
Post: #2
常系数线性递归序列 Linear recursion sequence (constent coefficients)
Read English
给定常数 \(k \geq 2\), \(c_0, c_1, \cdots, c_k \in \mathbf{C}\), 设 \(c_k \neq 0\), 递归关系
(\(\star\)) \(\quad\quad\quad\quad\quad c_k a_{n+k-1} + \cdots + c_1 a_n + c_0 = 0 \quad\quad\quad\quad (\forall n \in \mathbf{N}_0=\left\{n \in \mathbf{Z}:n\geq 0\right \})\)
确定了一族序列 \(\left\{ \left\{a_n\right \} \in \mathbf{C}^{\mathbf{N}_0}: c_k a_{n+k-1} + \cdots + c_1 a_n + c_0 = 0 \quad\quad(\forall n \in \mathbf{N}_0)\right\} \)


(0.1) \(P(x) = c_k x^{k-1} + \cdots + c_2 x + c_1\) 为 (\(\star\)) 的特征多项式
(0.2) \(c_k a_{n+k-1} + \cdots + c_1 a_n = 0\) 为 (\(\star\)) 的齐次部分。

我们有下列结果
(1) 若 \(\xi\) 是 \(P(x)\) 的根而 \(\left\{\beta_n\right \}\) 满足 (\(\star\)), 则 \(\left\{\xi^n\right \}\) 满足 (0.2) 于是 \(a_n = \xi^n + \beta_n\) 也满足 (\(\star\))
(2) 若 \(\xi\) 是 \(P(x)\) 的 \(r\)-重根 , 则对任一\(d \in \left\{0,\cdots,r-1\right \}\), \(a_n = n^d \xi^n\) 满足 (0.2)
(3) (\(\star\)) 具有形如 \(\beta_n = \gamma n^p\) 的解。其中 \(\gamma\) 及 \(p \in \mathbf{N}_0\) 是由(\(\star\)) 确定的常数.

由(1)~(3), (\(\star\)) 的通解形如:\[a_n = \sum_{i=1}^{m} \xi_{i}^n (\sum_{j=0}^{r_i-1}\alpha_{i,j}n^j) + \gamma n^p\] 其中\(\alpha_{i,j}\) 为任意常数, \(\xi_i\) 为 \(P(x)\) 的 \(r_i\)-重根,\(r_1+\cdots+r_m = k-1\).

(2)的证明: 因 \(\xi\) 是\(P(x)\)的 \(r\)-重根, \(P^{(j)}(\xi) = 0, \quad j=\overline{0,r-1}\).
显然\(c_k \xi^{n+k-1} + \cdots + c_1 \xi^n = \xi^n P(\xi) = 0\) 故 \(\left\{n^0 \xi^n\right \}\) 满足(0.2).
假定对某\(q\leq r-1\)
(p.1) 当\(0\leq d<q\) 时\(\left\{n^d \xi^n\right \}\) 满足(0,2), 则 \[\begin{align} 0&=\frac{d^q}{dx^q} (x^q P(x)) |_{x=\xi}= \sum_{j=1}^k c_j \xi^{j-1}\left((q+j-1)\cdots j\right)= \sum_{j=1}^k c_j \xi^{j-1}(j^q + Q(j)) \\
&= \sum_{j=1}^k c_j \xi^{j-1}j^q = \sum_{j=1}^k c_j j^q \xi^{j-1} \end{align}\] 这是因为 \(Q(j)\) 次数小于 \(q\) 的多项式以及我们的假定(p.1).
(3)的证明: 考虑可逆变换 \(\begin{pmatrix} d_1\\ d_2\\ \vdots\\ d_k \end{pmatrix}=\begin{pmatrix}
1 & 1 & \cdots &1 \\ 1 & 2 & \cdots & k \\ \vdots & \vdots & \ddots & \vdots \\
1 & 2^{k-1} & \cdots & k^{k-1} \end{pmatrix} \begin{pmatrix} c_1\\ c_2\\ \vdots\\ c_k
\end{pmatrix}\). 由于 \((c_1,\cdots, c_k)^{T} \neq \mathbf{0}\), 存在某 \(p \in \left\{0,\cdots,k-1\right \}\) 使 \(d_{p+1} = \sum_{j=1}^k j^p c_j \neq 0\) 而 \(d_i = 0, \quad i < p+1\). 于是 \[\begin{align} \sum_{j=1}^k c_j (m+j)^p& = \sum_{j=1}^k c_j \sum_{i=0}^p \begin{pmatrix}p \\i \end{pmatrix} m^{p-i} j^i = \sum_{i=0}^p \begin{pmatrix}p \\i \end{pmatrix} m^{p-i} \sum_{j=1}^k j^i c_j\\
& = \sum_{i=0}^p \begin{pmatrix}p \\i \end{pmatrix} m^{p-i} d_{i+1} = d_{p+1}\end{align}\] 令 \(\gamma = - c_0/d_{p+1}, \; \beta_n = \gamma n^p, \; m=n-1\) 则有 \[\begin{align} c_k \beta_{n+k-1} + \cdots + c_1 \beta_n + c_0 & = \gamma(c_k (m+k)^p + \cdots+c_1 (m+1)^p) + c_0\\ & = \gamma d_{p+1} + c_0 = 0 \end{align}\]故 (3) 成立.
Find all posts by this user
Quote this message in a reply
02-26-2010, 02:57 PM
Post: #3
Examples Linear recursion sequence 线性递归序列例子
Let's see how to use the post to solve some linear recursion problems.
(1) \(F_{n+1}=F_{n}+F_{n-1} + \lambda \)
\(\quad\) Solution: By the theory above, we have \((c_3,c_2,c_1,c_0)=(1,-1,-1,\lambda)\) and so \[ \begin{pmatrix} 1 & 1 & 1\\ 1 & 2 & 3\\ 1 & 4 & 9 \end{pmatrix}\begin{pmatrix}
c_1\\ c_2\\ c_3 \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1\\ 1 & 2 & 3\\ 1 & 4 & 9 \end{pmatrix}
\begin{pmatrix} 1\\ -1\\ -1 \end{pmatrix} = \begin{pmatrix} -1\\ -4\\ -12 \end{pmatrix}\quad\quad\quad\] \(\quad\) thus \(d_1=-1, \; d_1 y = -c_0 = -\lambda\) and so \(\beta_n = \lambda \)
\(\quad\) Now the characteristic equation is \(x^2-x-1=0\) therefore \(x = \left( 1\pm \sqrt{5}\right)/2\) and\[F_n= \alpha_1\left( \frac{\sqrt{5}+1}{2}\right)^{n}+\alpha_2 \left( \frac{1-\sqrt{5}}{2}\right)^{n}+\lambda\] \(\quad\)When \(\alpha_1=\alpha_2=1/2\) and \(\lambda = 0\), we get the well known Fibonacci sequence \(\left\{F_n\right \}\)

(2) \(a_{n+2}-2a_{n+1}+a_{n} + 2=0 \)
We have \((c_3,c_2,c_1,c_0) = (1,-2,1,2)\)
\[ \begin{pmatrix} 1 & 1 & 1\\ 1 & 2 & 3\\ 1 & 4 & 9 \end{pmatrix}\begin{pmatrix}
c_1\\ c_2\\ c_3 \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1\\ 1 & 2 & 3\\ 1 & 4 & 9 \end{pmatrix} \begin{pmatrix} 1\\ -2\\ 1 \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ 2 \end{pmatrix}\quad\quad\quad\] \(\quad\)
By the theory above, \(d_3 \gamma + c_0 = 2 \gamma + 2 = 0 \Rightarrow \gamma = -1\) thus \(\beta_n = -n^2\).
Also, the characteristic polynomial is \(x^2-2x+1 = (x-1)^2\) hence \(\xi = 1\) is the 2-fold zero and so
\(a_n = \xi^n (\alpha + n \beta) - n^2 = \alpha + n \beta - n^2\) is the general solution sequence of the relation \(a_{n+2}-2a_{n+1}+a_n+2=0\).

Check:
\(a_{n+2}-2a_{n+1}+a_n+2\)
\(= \alpha + (n+2) \beta - (n+2)^2 -2(\alpha + (n+1) \beta - (n+1)^2)+\alpha + n \beta - n^2+2\)
\(= - (n+2)^2 + 2(n+1)^2 - n^2 +2 = 0\)

The close form of \(\left\{a_n\right \}\) may not be better than the recursion itself in calculating the terms of the sequence. But it is definitely helpful to analyse the sequence.
Find all posts by this user
Quote this message in a reply
Post Reply 


Forum Jump:


Contact Us | Software Frontier | Return to Top | Return to Content | Lite (Archive) Mode | RSS Syndication