## 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

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

2. 나그네 2014/03/12 16:57

ㅎㅎ 요즘도 글 올리시네요. 아주아주 옛날에 들어왔던기억이나서 들려여 ㅋㅋ

3. 오르비수험생 2014/03/30 23:08

sos440님꼐선
순수수학은 천재의 영역이라고 생각하시나요? 아니면 범인들도 열심히 하면 필즈메달을 딸 수 있다고 생각하시나요?

수험생인 저로썬, 이 질문의 대한 답을
내가 과연 수능수학 고정 100점을 찍을 수 있을까 하는
질문으로 축소해석해서 받아들일 생각입니다.

• sos440 2014/04/03 11:45

1. 순수수학이 천재들만의 영역이라고 생각하지는 않습니다. 하지만 순수수학의 많은 것들을 이해하기 위해 투자해야 하는 시간과 그에 따른 희생을 생각해보면, 어지간히 프로 정신으로 무장하지 않으면 접근하기 힘든 게 사실이지요.

2. 제가 이해하는 천재성이라는 것은, '공부 시간을 단축시키는 능력'입니다. 즉 평범한 사람들도 충분히 노력하고 투자하면 이해할 수 있지만, 아무래도 시간이 더 걸릴 수는 있겠지요.

그리고 필즈메달이라는 것은 어지간한 천재 수학자들도 운이 따라주지 않으면 받기 힘든 물건입니다. 무슨 경시대회 금상같은 개념이 아니라는 것입니다. 사실 필즈메달을 목표로 수학을 한다는 것도 웃기고요. (그리고 그런 수학자들은 없습니다.)

3. 수능 공부는 천재성이 문제가 아니라 '성실성'의 문제입니다. (이는 심지어 대학교 학점에도 마찬가지로 적용됩니다.) 천재성이 있다면 공부 시간을 단축시킬 수는 있겠지만, 일반 학생들도 충분히 노력을 투자하면 고등학교라는 시간 내에서 커버가 가능하다는 것이 제 생각입니다.

• itcantbe 2014/04/24 16:17

고딩 수학은 기본 아닙니까? 당연히 자세히 알수록 좋겠지만서도 수능 100점 찍는다해도 이미 몇 백년전 지식 좀 아는거고 완벽히 안다고도 할 수 없지요. 요즘 지식의 팽창속도가 어마어마한대 겨우 대한민국 수능 100점 맞았다고 천재라 불리겠습니까? 그저 앞으로 천재가 될 가능성이 있는거죠.

4. 오르비수험생 2014/04/07 15:55

우문현답 감사합니다.

5. itcantbe 2014/04/24 16:14

미쿠미쿠시면서 너무 똑똑한 거 아닌가요? 반칙입니다. 지식인 답변 퀄리티랑 프로필 사진의 갭이 너무 심해서 함 와봤는데 상상 이상이군요.