Bài 1: Dãy số Fibonaci
Như các bạn đã biết dãy số Fibonaci là dãy 1, 1, 2, 3, 5, 8, Dãy này cho bởi công
thức đệ qui sau:
F
1
= 1, F
2
=1, F
n
= F
n-1
+ F
n-2
với n > 2
1. Chứng minh khẳng định sau:
Mọi số tự nhiên N đều có thể biểu diễn duy nhất dưới dạng tổng của một số số trong
dãy số Fibonaci.
N = a
k
F
k
+ a
k-1
F
k-1
+ a
1
F
1
Với biểu diễn như trên ta nói N có biểu diễn Fibonaci là akak
-1

CRY. Nếu có nhiều hành tinh thoả mãn thì ghi ra hành tinh có chỉ số nhỏ nhất.
Ví dụ: