• 0 Votes - 0 Average
• 1
• 2
• 3
• 4
• 5
 Examples of General Recursions
03-03-2010, 10:34 AM
Post: #1
 elim Moderator Posts: 581 Joined: Feb 2010 Reputation: 0
Examples of General Recursions

(1) $$a_{n+1}=n a_{n}+2, \quad \quad a_1=1$$

Let $$p(n,m) = n!/(n-m)!$$ then

\begin{align} a_{n+1} = & p(n,1)a_n + 2p(n,0) = p(n,1)((n-1)a_{n-1}+2)+2p(n,0) \\ = & p(n,2)a_{n-1}+2(p(n,0)+p(n,1)) =\cdots \\ = & p(n,n)a_1+2(p(n,0)+\cdots+p(n,n-1)) \\ = & n!+2n! \displaystyle{\left( \frac{1}{1!}+\cdots+\frac{1}{n!}\right)}\end{align}
Therefore $$a_n = (n-1)! \left( 2\displaystyle{\sum_{k=0}^{n-1} 1/(k!) }-1\right)$$. $$\quad n = 1,2,\cdots$$

Non-constant-coefficient is very different than constant-coefficient in recursion relations.
For this particular example, don't know if there is a simpler expression for a_n

(2) $$a_{n+1}=2a_n + (2n-1), \quad a_1=2$$

$$a_{n+1} = 2(2a_{n-1}+2(n-1)-1) + (2n-1) = 2^2 a_(n-1) + [2n+2^2(n-1)]-(1+2)=\cdots$$
$$= 2^n a_1 + \displaystyle{\sum_{i=1}^n 2^i (n+1-i)-\sum_{i=0}^{n-1} 2^i} = 2^{n+1}+(2^{n+2}-2n-4)-(2^n-1)= 2^n 5-2n-3$$.
So$$\quad \quad \quad \quad a_n = 2^{n-1}5-2n-1 \quad\quad (n = 1,2,\cdots)$$

(3) $$a_1=1, \quad a_{m+n} = a_m+a_n+mn$$

$$a_{n+1}=a_n+n+1$$ so $$\displaystyle{a_n = (n(n+1))/2}$$
Check: $$\displaystyle{\frac{m(m+1)}{2}+\frac{n(n+2)}{2}+mn}=\displaystyle{\frac{n^2+n+​m^2+m+2mn}{2}}$$
$$\displaystyle{= \frac{(m+n)^2+(m+n)}{2}=\frac{(m+n)(m+n+1)}{2}}$$

(4) $$a_1=10 \quad a_{n+1} = ((n+1)/(n^4)) a_n^4$$

$$a_{n+1}/(n+1) = (a_n/n)^4 = (a_{n-1}/(n-1))^{4^2}=\cdots=(a_1)^{4^n}=10^{4^n}$$ thus $$a_n = 10^{4^{n-1}} n$$. Check:
$$((n+1)/(n^4)) a_n^4 = ((n+1)/(n^4)) (10^{4^{n-1}}n)^4 = 10^{4^n}(n+1)=a_{n+1}$$`

(5) $$a_1=1 \quad a_{n+1}=2a_n+n-1$$
This means that $$a_{n+1}+n+1 = 2(a_n+n) = \cdots = 2^n (a_1+1) = 2^{n+1}$$
and so $$a_n = 2^n - n$$. Check:
$$2 (2^n-n)+n-1 = 2^{n+1}-n-1 = 2^{n+1}-(n+1)=a_{n+1}$$

(6) $$a_1=2 \quad a_{n+1} = \displaystyle{\frac{n}{n+1}} a_n +1$$
$$(n+1)a_{n+1} - n a_n =n+1 \Rightarrow (n+1)a_{n+1}-a_1 = \sum_1^n (i+1)= (n(n+3))/2$$
$$\Rightarrow a_n = (n^2+n+2)/(2n)$$
Check: $$\displaystyle{\frac{n}{n+1}\frac{n^2+n+2}{2n} +1 = \frac{n^2+n+2+2(n+1)}{2(n+1)} = \frac{(n+1)^2+(n+1)+2}{2(n+1)}}$$

(7) $$a_1=2, \quad a_{n+1}=a_n (n-1)/n + 2/n$$
We have $$na_{n+1}=(n-1)a_n+2 =>na_{n+1}=2n =>a_n -=2$$

(8) $$a_1 = 1, \quad S_n = n^2 a_n$$ where $$S_n = a_1+\cdots+a_n$$
$$a_{n+1} = S_{n+1}-S_n = (n+1)^2 a_{n+1}-n^2 a_n => a_{n+1} = a_n n/(n+2) = \cdots$$
$$= a_1(n(n-1)\cdots 1)/((n+2)(n+1)\cdots 3) = 2/((n+1)(n+2))$$
Or $$a_n = 2/(n(n+1)) = 2(1/n - 1/(n+1)) => S_n = 2(1-1/(n+1))=(2n)/(n+1)=n^2 a_n$$

(9) $$a_1 = 10, \quad a_{n+1} =\sqrt[4]{10 a_n}$$
Let $$b_n = \log a_n$$ then $$b_{n+1} = (1+ b_n) /4=> 4 b_{n+1}-b_n-1=0 => b_n = \alpha / 4^n + 1/3 = 2/3 4^{1-n}+1/3$$
Now $$a_n = 10^{b_n}$$
03-23-2010, 01:58 PM
Post: #2
 elim Moderator Posts: 581 Joined: Feb 2010 Reputation: 0
Find close form for the sequence by a matrix recursion

$$\begin{bmatrix}a_1\\b_1 \end{bmatrix}=\begin{bmatrix}-10\\-13 \end{bmatrix}$$, $$\begin{bmatrix}a_{n+1}\\b_{n+1} \end{bmatrix}=\begin{bmatrix}-2 & 4\\ -5&7 \end{bmatrix}\begin{bmatrix}a_n\\b_n \end{bmatrix}$$

$$A =\begin{bmatrix}-2 & 4\\ -5&7 \end{bmatrix}$$ has characteristic polynomial $\begin{vmatrix}\lambda+2 & -4\\ 5&\lambda-7\end{vmatrix}=\lambda^2-5\lambda+6=(\lambda-2)(\lambda-3)$ and the corresponding characteristic vectors $$\begin{bmatrix}1\\1 \end{bmatrix}$$ and $$\begin{bmatrix}4\\5 \end{bmatrix}$$
The inverse of $$B=\begin{bmatrix}1 & 4\\ 1&5 \end{bmatrix}$$ is $$\begin{bmatrix}5 & -4\\ -1&1 \end{bmatrix}$$ thus $B^{-1}AB=\begin{bmatrix}5 & -4\\ -1&1 \end{bmatrix}\begin{bmatrix}-2 & 4\\ -5&7 \end{bmatrix}\begin{bmatrix}1 & 4\\ 1&5 \end{bmatrix}=\begin{bmatrix}2 & 0\\ 0&3 \end{bmatrix}$
Let $$\begin{bmatrix}c_n\\d_n \end{bmatrix}=B^{-1}\begin{bmatrix}a_n\\b_n \end{bmatrix}$$, then we have $$\begin{bmatrix}c_1\\d_1 \end{bmatrix}=\begin{bmatrix}5 & -4\\ -1&1 \end{bmatrix}\begin{bmatrix}-10\\-13 \end{bmatrix}=\begin{bmatrix}2\\-3 \end{bmatrix}$$ and \begin{align} \begin{bmatrix}c_{n+1}\\d_{n+1} \end{bmatrix} = & B^{-1}\begin{bmatrix}a_{n+1}\\b_{n+1} \end{bmatrix}=B^{-1}A\begin{bmatrix}a_n\\b_n \end{bmatrix}=B^{-1}AB\begin{bmatrix}c_n\\d_n \end{bmatrix}\\ =& \begin{bmatrix}2 & 0\\ 0&3 \end{bmatrix}\begin{bmatrix}c_n\\d_n \end{bmatrix}=\cdots=\begin{bmatrix}2^n & 0\\ 0&3^n \end{bmatrix}\begin{bmatrix}c_1\\d_1 \end{bmatrix} \end{align}
Therefore $$\quad\quad \begin{bmatrix}a_n\\b_n \end{bmatrix}=B\begin{bmatrix}c_n\\d_n \end{bmatrix}=\begin{bmatrix}1 & 4\\ 1&5 \end{bmatrix}\begin{bmatrix}c_n\\d_n \end{bmatrix}=\begin{bmatrix}1 & 4\\ 1&5 \end{bmatrix}\begin{bmatrix}2^n\\-3^n \end{bmatrix}=\begin{bmatrix}2^n-3^n 4 \\ 2^n-3^n 5 \end{bmatrix}$$.
 « Next Oldest | Next Newest »

Forum Jump: