## A simple problem

2014/03/01 22:39

간단한 문제 하나로 오랜만에 블로그의 정적이나 깨 볼까 합니다.

Problem. Let $a \in \Bbb{R}$. Suppose that $a_{n} \in \Bbb{C}$ satisfies the recurrence relation \begin{align*} a_{n} = a_{n-1} + \frac{a}{n} a_{n-2}, \quad n \geq 2. \end{align*} prove that it satisfies the bound \begin{align*} a_{n} = \mathcal{O}\left( n^{a} \right). \end{align*}

Proof. Let $A_{n}$ and $B_{n}$ be sequences of $2\times 2$ matrices defined by \begin{align*} A_{n} = \begin{pmatrix} 1 & \tfrac{a}{n} \\ 1 & 0 \end{pmatrix}, \quad B_{n} = \begin{pmatrix} -\tfrac{a}{n} & 1+\tfrac{a}{n} \\ 1 & 1 \end{pmatrix}. \end{align*} Then it is easy to check that \begin{align*} \begin{pmatrix} a_{n} \\ a_{n-1} \end{pmatrix} = A_{n} \cdots A_{2} \begin{pmatrix} a_{1} \\ a_{0} \end{pmatrix}, \quad n \geq 2. \end{align*} Now we introduce $\tilde{A}_{n} = B_{n+1}^{-1} A_{n} B_{n}$. After some tedious calculation, it is easy to check that \begin{align*} \tilde{A}_{n} %&= \frac{1}{n (n+2a+1)} \begin{pmatrix} -a n - a(a+1) & (a-1) a \\ -a^{2} & n^{2} + (3a+1) n + (a^{2} + 2 a) \end{pmatrix} \\ &= \begin{pmatrix} -\tfrac{a}{n} & 0 \\ 0 & 1 + \tfrac{a}{n} \end{pmatrix} + \mathcal{O}\left( \frac{1}{n^{2}} \right). \end{align*} Thus for sufficiently large $n$, the operator norm $\| \tilde{A}_{n} \|$ of $\tilde{A}_{n}$ satisfies the following bound \begin{align*} \| \tilde{A}_{n} \| \leq 1 + \frac{a}{n} + \mathcal{O}\left( \frac{1}{n^{2}} \right). \end{align*} Applying this to $A_{n} \cdots A_{2}$, we have \begin{align*} \| A_{n} \cdots A_{2} \| &= \| B_{n+1} \tilde{A}_{n} \cdots \tilde{A}_{2} B_{2} \| \lesssim \exp \left\{ \sum_{k=2}^{n} \frac{a}{k} + \mathcal{O}\left( \frac{1}{k^{2}} \right) \right\} \lesssim n^{a}. \end{align*} This proves our bound as desired. ////

Intuition behind this proof is as follows:

1. Write the recurrence equation as $a_{n} - a_{n-1} = (a/n)a_{n-2}$. Heuristically, its continuous analogue is $y' = (a/x) y$. Then it is easy to check that the solution is of the form $y = c x^{a}$. So we can expect a similar asymptotic behavior for $a_{n}$.
2. The column vectors of $B_{n}$ are very close (up to $\mathcal{O}(n^{-2})$) to eigenvectors of $A_{n}$. Thus $\tilde{A}_{n}$ is essentially the matrix representation of $A_{n}$ with respect to eigenvectors of $A_{n}$ and $A_{n+1}$.

### 댓글을 달아 주세요

1. hyddox 2014/03/02 01:12

오 ㅋㅋ 오랜만에 글 올리시네요
블로그 글 잘 보고 있습니다.
요즘 공부는 잘 되시나요?

• sos440 2014/03/03 04:35

공부야 그냥마냥이죠 -ㅁ-;; 여차저차 잘 살고는 있는 것 같습니다.