간단한 문제 하나

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

---

문제. $a \in \mathbb{R}$ 라고 하자. 또한 수열 $a_{n} \in \mathbb{C}$ 가 다음의 점화식을 만족시킨다고 하자.

\begin{align*} a_{n} = a_{n-1} + \frac{a}{n} a_{n-2}, \quad n \geq 2. \end{align*}

그러면 아래와 같은 estimate 가 성립함을 보여라:

\begin{align*} a_{n} = \mathcal{O}\left( n^{a} \right). \end{align*}

 

증명. 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. $ \square $

---

이 계산의 아이디어에 대해 살짝 설명하자면 다음과 같다:

 

1. 주어진 점화식을 $a_{n} - a_{n-1} = (a/n)a_{n-2}$ 와 같이 적어보자. 이를 차분방정식으로 이해하면, 그와 쌍을 이루는 미분방정식 $y' = (a/x) y$ 을 얻는대. 이때 이 방정식의 해가 $y = c x^{a}$ 꼴임은 쉽게 확인할 수 있다. 따라서 원래의 차분방정식의 해 역시 동일한 증가속도를 보일 것이라 기대할 수 있다.

 

2. 행렬 $B_{n}$ 의 열벡터들은 ($\mathcal{O}(n^{-2})$ 정도의 차이를 무시하면) $A_{n}$ 의 고유벡터들과 매우 가깝다. 따라서 $\tilde{A}_{n}$ 는 거의 $A_{n}$ 의 대각화와 다름없다.