Chủ đề này có 2 trả lời

[Zaraki]

Ta gọi tribi của một số nguyên dương $k$ (ký hiệu là $T(k)$) là số tất cả các cặp $11$ trong biểu diễn nhị phân của $k$. Ví dụ $$T(1)=T(2)=0; T(3)=1; T(4)=T(5)=0; T(6)=1; T(7)=2; \, v.v...$$

Hãy tính \[S_n=\sum_{k=1}^{2^n} T(k)\]

Thầy Hoàng Xuân Thanh

[baopbc]

Mình thành thật xin lỗi, minh đã gõ vào Word rồi nhưng không post lên được!

Mình sẽ gửi lên sau:

P/s: Anh Toàn cho em hỏi: $S_{n+1}=S_{n}+2^{n-1}$ có đúng không ạ!

Bài viết đã được chỉnh sửa nội dung bởi baopbc: 15-02-2016 - 11:38

[baopbc]

Lời giải của mình: Ta có:$S_{n+1}=\sum_{k=1}^{2^{n+1}}T(k)=\sum_{k=1}^{2^{n}}T(k)+\sum_{k=2^{n}+1}^{2^{n+1}}T(k)=S_{n}+\sum_{k=2^{n}+1}^{2^{n+1}}$

Do $T(2^{n+1})=0$ nên $\sum_{k=2^{n}+1}^{2^{n+1}}=\sum_{k=2^{n}+1}^{2^{n}+(2^{n}-1)}$

Ta xét các số có dạng: $2^{n}+k (1\leq k\leq 2^{n}-1)$

Trường hợp 1: $k<2^{n-1}\Rightarrow 2^{n}+k=1.2^{n}+0.2^{n-1}+k\Rightarrow T(2^{n}+k)=T(k)$(1)

Trường hợp 2: $k\geq 2^{n-1}\Rightarrow 2^{n}+k=1.2^{n}+1.2^{n-1}+k-2^{n-1}\Rightarrow T(2^{n}+k)=T(k)+1$(2)

Từ (1)(2): $\Rightarrow \sum_{k=2^{n}+1}^{2^{n}+(2^{n}-1)}=\sum_{k=1}^{2^{n}}+2^{n-1}=S_{n}+2^{n-1}$

$\Rightarrow S_{n+1}=2S_{n}+2^{n-1}$

Áp dụng công thức sai phân ta tìm được $S_{n}$.

P/s: Chỗ cuối cũng có thể giải thích như sau:

$S_{n+1}=2S_{n}+2^{n-1}=2^{2}S_{n-1}+2.2^{n-1}=...=2^{n}.S_{1}+n.2^{n-1}=n.2^{n-1}$

Bài viết đã được chỉnh sửa nội dung bởi baopbc: 15-02-2016 - 13:23