간단한 문제 하나

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

---

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

$$\begin{array}{r}{a}_n=a_{n-1}+\frac{a}{n}{a}_{n-2},n\ge 2.\end{array}$$

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

$$\begin{array}{r}{a}_n=\mathcal{O}\left(n^a\right).\end{array}$$

 

증명. Let $A_n$ and $B_n$ be sequences of $2\times 2$ matrices defined by

$$\begin{array}{r}{A}_n=\left(\begin{array}{cc}1& \frac{a}{n}\\ 1& 0\end{array}\right),B_n=\left(\begin{array}{cc}-\frac{a}{n}& 1+\frac{a}{n}\\ 1& 1\end{array}\right).\end{array}$$

Then it is easy to check that

$$\begin{array}{r}\left(\begin{array}{c}{a}_n\\ a_{n-1}\end{array}\right)=A_n\cdots A_2\left(\begin{array}{c}{a}_1\\ a_0\end{array}\right),n\ge 2.\end{array}$$

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{array}{rl}{\tilde{A}}_n& =\frac{1}{n(n+2a+1)}\left(\begin{array}{cc}-an-a(a+1)& (a-1)a\\ -a^2& n^2+(3a+1)n+(a^2+2a)\end{array}\right)\\ & =\left(\begin{array}{cc}-\frac{a}{n}& 0\\ 0& 1+\frac{a}{n}\end{array}\right)+\mathcal{O}\left(\frac{1}{n^2}\right).\end{array}$$

Thus for sufficiently large $n$, the operator norm $\Vert {\tilde{A}}_n\Vert$ of ${\tilde{A}}_n$ satisfies the following bound

$$\begin{array}{r}\Vert {\tilde{A}}_n\Vert \le 1+\frac{a}{n}+\mathcal{O}\left(\frac{1}{n^2}\right).\end{array}$$

Applying this to $A_n\cdots A_2$, we have

$$\begin{array}{rl}\Vert A_n\cdots A_2\Vert & =\Vert B_{n+1}{\tilde{A}}_n\cdots {\tilde{A}}_2{B}_2\Vert \lesssim \exp \{\sum _{k=2}^n\frac{a}{k}+\mathcal{O}\left(\frac{1}{k^2}\right)\}\lesssim n^a.\end{array}$$

This proves our bound as desired. $◻$

---

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

 

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

 

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