Gọi s n ​ là số cách viết số tự nhiên n thành tổng của một dãy có tính thứ tự gồm các số 1, 3, 4. Chứng minh rằng s 2 n ​ là số chính phương.

Giải thích

Đáp án: Công thức truy hồi của dãy này là: { s 1 ​ = 1 , s 2 ​ = 1 , s 3 ​ = 2 , s 4 ​ = 4 s n + 4 ​ = s n + 3 ​ + s n + 1 ​ + s n ​ , n ≥ 1 ​ Tính toán trực tiếp, ta thấy rằng: s 2 ​ = 1 2 , s 4 ​ = 2 2 , s 6 ​ = 3 2 , s 8 ​ = 5 2 và dự đoán được s 2 n ​ = F n + 1 2 ​ với F n ​ là dãy Fibonacci. Ta sẽ chứng minh bằng quy nạp. Với n = 2 thì khẳng định đúng. Giả sử khẳng định đúng đến n = 2m, ta có s 2 m + 2 ​ = s 2 m + 1 ​ + s 2 m − 1 ​ + s 2 m − 2 ​ = ( s 2 m ​ + s 2 m − 2 ​ + s 2 m − 3 ​ ) + s 2 m − 1 ​ + s 2 m − 2 ​ = s 2 m ​ + 2 s 2 m − 2 ​ + s 2 m − 1 ​ + s 2 m − 3 ​ = s 2 m ​ + 2 s 2 m − 2 ​ + ( s 2 m ​ − s 2 m − 4 ​ ) = 2 s 2 m ​ + 2 s 2 m − 2 ​ − s 2 m − 4 ​ = 2 F m + 1 2 ​ + 2 F m 2 ​ − F m − 1 2 ​ = ( F m + 1 ​ + F m ​ ) 2 + ( F m + 1 ​ − F m ​ ) 2 − F m − 1 2 ​ = F m + 2 2 ​ Theo nguyên lý quy nạp, ta có điều phải chứng minh.