티스토리 툴바


A simple problem

Math Talk 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}$.
저작자 표시
Posted by sos440

댓글을 달아 주세요

  1. hyddox 2014/03/02 01:12  댓글주소  수정/삭제  댓글쓰기

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

  2. 나그네 2014/03/12 16:57  댓글주소  수정/삭제  댓글쓰기

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

  3. 오르비수험생 2014/03/30 23:08  댓글주소  수정/삭제  댓글쓰기

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

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

    • sos440 2014/04/03 11:45  댓글주소  수정/삭제

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

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

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

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

  4. 오르비수험생 2014/04/07 15:55  댓글주소  수정/삭제  댓글쓰기

    우문현답 감사합니다.