1. **Nêu bài toán:** Cho hai dãy số $(u_n)$ và $(v_n)$ với $u_0 = v_0 = 0$ và với mọi $n \geq 1$ thỏa mãn $$u_n = 2u_{\lfloor n/2 \rfloor} + n, \quad v_n = 3v_{\lfloor n/3 \rfloor} + n.$$ Đặt dãy $x_n = 2^{u_n} - 3^{v_n}$. Chứng minh dãy $(x_n)$ đổi dấu vô hạn lần. 2. **Phân tích bài toán:** Ta cần chứng minh rằng $x_n$ có giá trị dương và âm xen kẽ nhau vô hạn lần, tức là tồn tại vô hạn các $n$ sao cho $x_n > 0$ và vô hạn các $n$ sao cho $x_n < 0$. 3. **Xét tính chất của $u_n$ và $v_n$:** - Công thức truy hồi cho $u_n$ và $v_n$ đều có dạng: $$u_n = a u_{\lfloor n/b \rfloor} + n, \quad v_n = c v_{\lfloor n/d \rfloor} + n,$$ trong đó $a=2, b=2$ với $u_n$ và $c=3, d=3$ với $v_n$. 4. **Giải xấp xỉ cho $u_n$:** Áp dụng định lý chính cho các phương trình truy hồi dạng $T(n) = a T(n/b) + f(n)$ với $f(n) = n$. Ở đây, $a=2$, $b=2$, $f(n) = n$. Ta có $\log_b a = \log_2 2 = 1$. Theo định lý chính: - Nếu $f(n) = \Theta(n^{\log_b a} \log^k n)$ với $k=0$, thì $$u_n = \Theta(n^{\log_b a} \log^{k+1} n) = \Theta(n \log n).$$ 5. **Tương tự cho $v_n$:** Ở đây $a=3$, $b=3$, $f(n) = n$. Ta có $\log_b a = \log_3 3 = 1$. Áp dụng định lý chính tương tự, ta được $$v_n = \Theta(n \log n).$$ 6. **Kết luận về $u_n$ và $v_n$:** Cả hai dãy đều tăng xấp xỉ theo $n \log n$. 7. **Xét dãy $x_n = 2^{u_n} - 3^{v_n}$:** Ta có $$x_n = 2^{u_n} - 3^{v_n} = \exp(u_n \ln 2) - \exp(v_n \ln 3).$$ 8. **So sánh tốc độ tăng của $2^{u_n}$ và $3^{v_n}$:** Vì $u_n \approx C_1 n \log n$ và $v_n \approx C_2 n \log n$ với các hằng số dương $C_1, C_2$. Ta xét tỉ số $$\frac{\ln(2^{u_n})}{\ln(3^{v_n})} = \frac{u_n \ln 2}{v_n \ln 3} \approx \frac{C_1 n \log n \ln 2}{C_2 n \log n \ln 3} = \frac{C_1 \ln 2}{C_2 \ln 3}.$$ 9. **Tính các hằng số $C_1, C_2$:** Từ công thức truy hồi, ta có thể tìm gần đúng: $$u_n \approx 2n \log_2 n, \quad v_n \approx \frac{3}{2} n \log_3 n.$$ Chuyển đổi log: $$u_n \approx 2 n \frac{\ln n}{\ln 2}, \quad v_n \approx \frac{3}{2} n \frac{\ln n}{\ln 3}.$$ Vậy $$\frac{u_n \ln 2}{v_n \ln 3} \approx \frac{2 n \frac{\ln n}{\ln 2} \ln 2}{\frac{3}{2} n \frac{\ln n}{\ln 3} \ln 3} = \frac{2 n \ln n}{\frac{3}{2} n \ln n} = \frac{2}{\frac{3}{2}} = \frac{4}{3} > 1.$$ 10. **Ý nghĩa:** Tỉ số lớn hơn 1 nghĩa là $2^{u_n}$ tăng nhanh hơn $3^{v_n}$ về mặt mũ. 11. **Xét các giá trị $n$ dạng $n=2^k$ và $n=3^k$:** - Với $n=2^k$, ta có $$u_{2^k} = 2 u_{2^{k-1}} + 2^k,$$ nhưng do $\lfloor n/2 \rfloor = 2^{k-1}$, ta có thể tính dãy này dễ dàng. - Tương tự với $n=3^k$. 12. **Tính $x_{2^k}$ và $x_{3^k}$:** - Với $n=2^k$, $v_{2^k}$ nhỏ hơn nhiều so với $u_{2^k}$ vì $v_n$ phụ thuộc vào $v_{\lfloor n/3 \rfloor}$. - Do đó, $x_{2^k} = 2^{u_{2^k}} - 3^{v_{2^k}} > 0$ với $k$ lớn. - Với $n=3^k$, tương tự, $u_{3^k}$ nhỏ hơn nhiều so với $v_{3^k}$, nên $$x_{3^k} = 2^{u_{3^k}} - 3^{v_{3^k}} < 0$$ cho $k$ lớn. 13. **Kết luận:** Dãy $x_n$ có giá trị dương tại các số $n=2^k$ và giá trị âm tại các số $n=3^k$ với $k$ lớn. Do đó, dãy $(x_n)$ đổi dấu vô hạn lần. **Đáp số:** Dãy $(x_n)$ đổi dấu vô hạn lần.