Arithmetic Sequence

Bài toán (Vietnam Team Selection Test 2011)

Cho dãy số nguyên dương $(u_n)$ :

$$\{\begin{array}{c}{u}_0=1,u_1=3\\ u_{n+2}=1+\lfloor \frac{u_{n+1}^2}{u_n}\rfloor ,\forall n\ge 0\end{array}$$

Chứng minh rằng :

$$u_{n+2}{u}_n-u_{n+1}^2=2^n,\forall n\in \mathbb{N}$$

Lời giải :

Dễ thấy dãy $(u_n)$ xác định như trên là duy nhất.

Bằng cách tính thêm giá trị $u_2,u_3$ ta tuyến tính hóa dãy $(u_n)$. Xét dãy $(v_n)$ :

$$\{\begin{array}{c}{v}_0=1,v_1=3\\ v_{n+2}=4v_{n+1}-2v_n\end{array}$$

Cũng dễ thấy dãy $(v_n)$ xác định như trên là duy nhất. Ta dễ chứng minh được $v_{n+2}{v}_n-v_{n+1}^2=2^n$ bằng quy nạp.

Tiếp theo ta chứng minh :

$$v_{n+2}=1+\lfloor \frac{v_{n+1}^2}{v_n}\rfloor$$

Thật vậy, ta có :

$v_{n+2}{v}_n-v_{n+1}^2$$=2^n$$\Rightarrow v_{n+1}^2$$<v_n{v}_{n+2}$$\Rightarrow \frac{v_{n+1}^2}{v_n}$$<v_{n+2}$

Hơn nữa có :

$\frac{v_{n+1}^2}{v_n}$$>v_{n+2}-1$$\iff 1$$>\frac{v_{n+2}{v}_n-v_{n+1}^2}{v_n}$$=\frac{2^n}{v_n}$$\iff v_n$$<2^n$

Không khó để ta chỉ ra điều này bằng quy nạp. Như vậy :

$\frac{v_{n+1}^2}{v_n}-1$$<v_{n+2}-1$$<\frac{v_{n+1}^2}{v_n}$$\Rightarrow v_{n+2}-1$$=\lfloor \frac{v_{n+1}^2}{v_n}\rfloor$

Chú ý tính duy nhất của $(u_n)$ và $(v_n)$ mà ta có $(u_n)$ trùng $(v_n)$. Dễ có điều phải chứng minh.