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}$$
$$F_{n+1}=\sum_{k=0}^{\left \lfloor \frac{n}{2} \right \rfloor}\binom{n-k}{k}$$
Bắt đầu bởi dark templar, 11-11-2012 - 21:58
hxthanh
#2
Đã gửi 11-11-2012 - 22:10
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}$
- E. Galois và perfectstrong thích
#3
Đã gửi 11-11-2012 - 22:18
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ồiThế 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?
_____________________
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
Toán thi Học sinh giỏi và Olympic →
Số học →
$$...\sum^{n-1}_{k=1}(-1)^{\left[\frac{km}{n}\right]}.\left\{\frac{km}{n}\right\}$$Bắt đầu bởi WhjteShadow, 15-04-2013 hxthanh |
|
|||
Toán thi Học sinh giỏi và Olympic →
Số học →
$$\sum^{(p-1)(p-2)}_{k=1}\left[\sqrt[3]{kp}\right]=\frac{(3p-5)(p-2)(p-1)}{4}$$Bắt đầu bởi WhjteShadow, 11-04-2013 hxthanh |
|
|||
Toán thi Học sinh giỏi và Olympic →
Các dạng toán khác →
Một số bài toán tính tổng chọn lọcBắt đầu bởi hxthanh, 02-04-2013 dark templar, hxthanh, for all |
|
|||
Toán thi Học sinh giỏi và Olympic →
Dãy số - Giới hạn →
$$S=\sum_{k=1}^{\infty}\frac{F_{2k+1}}{L_{k}L_{k+1}L_{k+2}}$$Bắt đầu bởi dark templar, 07-11-2012 hxthanh, perfecstrong, and vmfers |
|
|||
Toán thi Học sinh giỏi và Olympic →
Số học →
$$3^{\frac{F_{m}-1}{2}} \equiv -1(\mod F_{m})$$Bắt đầu bởi dark templar, 03-11-2012 hxthanh, nguyenta98, perfecstrong |
|
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh