Đến nội dung

Hình ảnh

$$F_{n+1}=\sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor}\binom{n-k}{k}$$

- - - - - hxthanh

  • Please log in to reply
Chủ đề này có 2 trả lời

#1
dark templar

dark templar

    Kael-Invoker

  • Hiệp sỹ
  • 3788 Bài viết
Khuyến cáo:Không xài quy nạp :)
Bài toán: Ký hiệu $F_{n}$ là dãy số Fibonancci.Chứng minh công thức sau:
$$F_{n+1}=\sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor}\binom{n-k}{k}$$
"Do you still... believe in me ?" Sarah Kerrigan asked Jim Raynor - Starcraft II:Heart Of The Swarm.

#2
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết

Khuyến cáo:Không xài quy nạp :)
Bài toán: Ký hiệu $F_{n}$ là dãy số Fibonancci.Chứng minh công thức sau:
$$F_{n+1}=\sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor}\binom{n-k}{k}$$


Thế chuyển thành bài toán đếm có được không?

$\fbox{Bài toán: }$
Có bao nhiêu cách viết số tự nhiên $n$ thành tổng của các số $1$ và $2$, hai cách viết khác nhau nếu có số hạng khác nhau hoặc thứ tự lấy tổng khác nhau?
_____________________

Đếm cách 1:

Gọi $S_n$ là số cách viết số $n$ thoả yêu cầu đề bài
Chia ra hai trường hợp:
- Tổng đó có số 1 đứng đầu: $n=1+(...)$ trong ngoặc là những số $1$ hoặc $2$
hay $n-1=(...)$
Từ đó có $S_{n-1}$ cách
- Tổng đó có số 2 đứng đầu: $n=2+(...)$ trong ngoặc là những số $1$ hoặc $2$
hay $n-2=(...)$
Từ đó có $S_{n-2}$ cách

Vậy $S_n=S_{n-1}+S_{n-2}$ mà dễ thấy $S_1=1; S_2=2$ nên $S_n=F_{n+1}$

Đếm cách 2:

Với $k$ số $2$ và $n-2k$ số $1$ ta tạo thành một "số" có $n-k$ chữ số

như vậy có $\binom{n-k}{k}$ số cách tạo (cách đặt $k$ số $2$ vào $n-k$ vị trí)

Coi mỗi chữ số là một số hạng của tổng cần phân tích

Rõ ràng số cách viết bằng $\quad \sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor} \binom{n-k}{k}$

#3
dark templar

dark templar

    Kael-Invoker

  • Hiệp sỹ
  • 3788 Bài viết

Thế chuyển thành bài toán đếm có được không?

$\fbox{Bài toán: }$
Có bao nhiêu cách viết số tự nhiên $n$ thành tổng của các số $1$ và $2$, hai cách viết khác nhau nếu có số hạng khác nhau hoặc thứ tự lấy tổng khác nhau?
_____________________

Em nghĩ bài này tồn tại cách giải thuần túy Đại số nhưng chưa nghĩ ra,còn phép đếm thì em từng thấy rồi :P
P/s:Anh có tài liệu hay về TỔ hợp hay hỏi anh Lộc giúp em chưa ? :)
"Do you still... believe in me ?" Sarah Kerrigan asked Jim Raynor - Starcraft II:Heart Of The Swarm.





Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: hxthanh

0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh