• 3 Votes - 4.33 Average
• 1
• 2
• 3
• 4
• 5
 Linear recursion (constent coefficients) 线性递归序列
02-17-2010, 02:43 PM
Post: #1
 elim Moderator Posts: 580 Joined: Feb 2010 Reputation: 0
Linear recursion (constent coefficients) 线性递归序列

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.
02-24-2010, 06:06 PM
Post: #2
 elim Moderator Posts: 580 Joined: Feb 2010 Reputation: 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 \})$$

(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$$) 确定的常数.

(2)的证明: 因 $$\xi$$ 是$$P(x)$$的 $$r$$-重根, $$P^{(j)}(\xi) = 0, \quad j=\overline{0,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) 成立.
02-26-2010, 02:57 PM
Post: #3
 elim Moderator Posts: 580 Joined: Feb 2010 Reputation: 0
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.
 « Next Oldest | Next Newest »

Forum Jump: