Một hệ thống đèn gồm \(n\) bóng đèn được bố trí từ trái qua phải và được đánh số lần lượt từ 1 đến \(n\). Mỗi bóng đèn có 2 trạng thái tắt và mở. Người ta ký hiệu trạng thái tắt là 0 và mở là 1. Bóng đèn ở vị trí đầu tiên (vị trí 1) luôn ở trạng thái mở (trạng thái 1).

Yêu cầu: Hãy cho biết có bao trạng thái khác nhau của hệ thống đèn gồm \(\mathbf{n}\) bóng đèn thỏa điều kiện sau:

+ Bóng đèn ở vị trí đầu tiên luôn mở.

+ Không tồn tại 2 bóng đèn mở bất kỳ liên tiếp nhau trong hệ thống.

Dữ liệu vào:

+ Số nguyên dương \(n\ (n \leq 100)\).

Kết quả:

+ Ghi một số duy nhất là số trạng thái khác nhau của hệ thống bóng đèn.

Ví dụ: