Post Reply 
 
Thread Rating:
  • 0 Votes - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Examples of General Recursions
03-03-2010, 10:34 AM
Post: #1
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}\)
Find all posts by this user
Quote this message in a reply
03-23-2010, 01:58 PM
Post: #2
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}\).
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