Đến nội dung

Hình ảnh

Một số bài toán tính tổng chọn lọc

- - - - - dark templar hxthanh for all

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

#1
hxthanh

hxthanh

    Tín đồ $\sum$

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

Bài toán 1 :

Với $1\le n\in\mathbb N$

Tính tổng $S=\sum_{k=1}^n k\left\lfloor\sqrt k\right\rfloor$

 

Bài toán 2 :

Với $a\ne 1<p<n;\;\;n,p\in\mathbb N$

Tính tổng $S=\sum_{k=1}^na^k\left\lfloor\dfrac{k}{p}\right\rfloor$

__________________________

 

Lời giải hai bài toán này các bạn có thể tham khảo ở đây

 

Bây giờ sẽ là đề mới:

 

Bài toán 3 :

Với $n$ nguyên dương, hãy tính tổng sau:

$S=\sum_{k=1}^n (-1)^k\left\lfloor\dfrac{(-1)^kk(k+1)}{3}\right\rfloor$

 

Bài toán 4 :

Cho dãy số $Fibonacci \;\;\{F_n\}_0^\infty\;\; :\;\begin{cases}F_0=0,\quad F_1=1\\ F_n=F_{n-1}+F_{n-2}\quad(n\ge 2)\end{cases}$

Hãy tính tổng:
$S=\sum_{k=1}^n (-1)^kkF_k$

______________________________________________________________

Update: Sửa lỗi bài số 3 (bớt đi nhân tử k, nếu không thì "khủng bố" quá! :) )


Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 03-04-2013 - 18:52


#2
dark templar

dark templar

    Kael-Invoker

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

Bài toán 3 :

Với $n$ nguyên dương, hãy tính tổng sau:

$S=\sum_{k=1}^n (-1)^kk\left\lfloor\dfrac{(-1)^kk(k+1)}{3}\right\rfloor$

 

Bài toán 4 :

Cho dãy số $Fibonacci \;\;\{F_n\}_0^\infty\;\; :\;\begin{cases}F_0=0,\quad F_1=1\\ F_n=F_{n-1}+F_{n-2}\quad(n\ge 2)\end{cases}$

Hãy tính tổng:
$S=\sum_{k=1}^n (-1)^kkF_k$

Ý tưởng giải:

Spoiler

Lời giải bài 4:

Bằng SPTP,ta có :

 

\[\begin{array}{rcl}\sum\limits_{k = 1}^n {{{\left( { - 1} \right)}^k}k{F_k}}  &=&  - 1 + \sum\limits_{k = 2}^n {\Delta \left[ {{{\left( { - 1} \right)}^{k - 1}}{F_{k - 2}}} \right]} k\\&=&  - 1 + \left[ {{{\left( { - 1} \right)}^{k - 1}}k{F_{k - 2}}} \right]_{k = 2}^{n + 1} + \sum\limits_{k = 2}^n {{{\left( { - 1} \right)}^{k + 1}}{F_{k - 1}}\Delta k} \\&=&  - 1 + {\left( { - 1} \right)^n}\left( {n + 1} \right){F_{n - 1}} - 1 + \sum\limits_{k = 3}^n {\Delta \left[ {{{\left( { - 1} \right)}^k}{F_{k - 3}}} \right]} \\&=&  - 2 + {\left( { - 1} \right)^n}\left( {n + 1} \right){F_{n - 1}} + \left[ {{{\left( { - 1} \right)}^k}{F_{k - 3}}} \right]_{k = 3}^{n + 1}\\&=&  - 2 + {\left( { - 1} \right)^n}\left( {n + 1} \right){F_{n - 1}} + {\left( { - 1} \right)^{n + 1}}{F_{n - 2}}\end{array}\]
 
**********
Ý tưởng giải:
Spoiler
Lời giải bài 3:
Phân đoạn $k$ theo modulo 3 thì khi đó,tổng cần tính sẽ là :
\[\begin{array}{rcl}\sum\limits_{k = 1}^n {{{\left( { - 1} \right)}^k}k\left\lfloor {\frac{{{{\left( { - 1} \right)}^k}k\left( {k + 1} \right)}}{3}} \right\rfloor }  &=& \underbrace {3\sum\limits_{m = 1}^{\left\lfloor {\frac{n}{3}} \right\rfloor } {{m^2}\left( {3m + 1} \right)} }_{ = {S_1}} + \underbrace {\sum\limits_{m = 1}^{\left\lfloor {\frac{n+1}{3}} \right\rfloor } {{{\left( {3m - 1} \right)}^2}m} }_{ = {S_2}}\\&+& \underbrace {\sum\limits_{m = 1}^{\left\lfloor {\frac{n+2}{3}} \right\rfloor } {{{\left( { - 1} \right)}^m}\left( {3m - 2} \right)\left\lfloor {\frac{{{{\left( { - 1} \right)}^m}\left( {3m - 2} \right)\left( {3m - 1} \right)}}{3}} \right\rfloor } }_{ = {S_3}}\end{array}\]
 
2 tổng $S_1;S_2$ không khó để tính toán,chủ yếu dựa vào 3 tổng sau :
  • $1+2+...+n=\frac{n(n+1)}{2}$.
  • $1^2+2^2+...+n^2=\frac{n(n+1)(2n+1)}{6}$.
  • $1^3+2^3+...+n^3=\frac{n^2(n+1)^2}{4}$.

 

Điều quan trọng là ta phải tính được tổng ${S_3} = \sum\limits_{m = 1}^{\left\lfloor {\frac{n+2}{3}} \right\rfloor } {{{\left( { - 1} \right)}^m}\left( {3m - 2} \right)\left\lfloor {\frac{{{{\left( { - 1} \right)}^m}\left( {3m - 2} \right)\left( {3m - 1} \right)}}{3}} \right\rfloor } $

 

Dễ thấy rằng :

 

\[\begin{array}{rcl}\left\lfloor {\frac{{{{\left( { - 1} \right)}^m}\left( {3m - 2} \right)\left( {3m - 1} \right)}}{3}} \right\rfloor  &=& \left\lfloor {\frac{{{{\left( { - 1} \right)}^m}}}{3}\left( {9{m^2} - 9m + 2} \right)} \right\rfloor \\&=& \left\lfloor {3m{{\left( { - 1} \right)}^m}\left( {m - 1} \right) + \frac{{{{\left( { - 1} \right)}^m} + 2}}{3}} \right\rfloor \\&=& \left\{ \begin{eqnarray*}3m{\left( { - 1} \right)^m}\left( {m - 1} \right) \quad &\text{($m$ lẻ)}\\3m{\left( { - 1} \right)^m}\left( {m - 1} \right) + 1 \quad &\text{($m$ chẵn)}\end{eqnarray*} \right.\end{array}\]
 
Từ đây,ta có thể tách tổng $S_3$ thành 2 tổng con phụ thuộc vào tính chẵn lẻ của $m$. :)
 
Spoiler
 
 

Bài viết đã được chỉnh sửa nội dung bởi dark templar: 15-04-2013 - 20:23

"Do you still... believe in me ?" Sarah Kerrigan asked Jim Raynor - Starcraft II:Heart Of The Swarm.

#3
hxthanh

hxthanh

    Tín đồ $\sum$

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

Thực ra ý tưởng của bài 3 cũng là SPTP :luoi:

 

dark templar thử chứng minh điều này xem :

 

$\Delta\left((-1)^k\left\lfloor\dfrac{(-1)^kk(k+1)}{3}\right\rfloor\right)=\left\lfloor\dfrac{k+2}{2}\right\rfloor+\left\lfloor\dfrac{k+2}{6}\right\rfloor$

 

P/s @to dark templar: Kết quả bài 4 của em mặc dù đúng, nhưng chưa hợp lý! (khi thay $n=1$ vào thì xuất hiện $F_{-1}$ chưa được định nghĩa! :closedeyes: )

 

:))



#4
dark templar

dark templar

    Kael-Invoker

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

Thực ra ý tưởng của bài 3 cũng là SPTP :luoi:

 

dark templar thử chứng minh điều này xem :

 

$\Delta\left((-1)^k\left\lfloor\dfrac{(-1)^kk(k+1)}{3}\right\rfloor\right)=\left\lfloor\dfrac{k+2}{2}\right\rfloor+\left\lfloor\dfrac{k+2}{6}\right\rfloor$

 

P/s @to dark templar: Kết quả bài 4 của em mặc dù đúng, nhưng chưa hợp lý! (khi thay $n=1$ vào thì xuất hiện $F_{-1}$ chưa được định nghĩa! :closedeyes: )

 

:))

Em hơi dở mấy hàm Số học,nhưng em cũng sẽ thử. :)

 

Còn vấn đề về $F_{-1}$ thì thật ra là có tồn tại dãy "đối" Fibonacci,định nghĩa theo công thức $F_{-n}=(-1)^{n+1}F_{n} \quad \forall n \in \mathbb{N}$.

 

@hxthanh: Vẫn biết là có định nghĩa đó, nhưng đề bài không cho mà! (Chỉ cần thay $F_{n-2}=F_{n}-F_{n-1}$ thì sẽ ok)

 

@supermember: bài Toán số 4 có thể dùng cách tương tự bài này:

 

       http://www.artofprob...p?f=56&t=366103


Bài viết đã được chỉnh sửa nội dung bởi supermember: 04-04-2013 - 20:49

"Do you still... believe in me ?" Sarah Kerrigan asked Jim Raynor - Starcraft II:Heart Of The Swarm.

#5
hxthanh

hxthanh

    Tín đồ $\sum$

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

Đề mới:

 

Bài toán 5:

Tính tổng sau:

$T=\sum_{k=1}^n (-1)^{\frac{k(k+1)}{2}} k2^k$

 

Bài toán 6:

Số điều hòa (bậc 1) thứ $m$ được định nghĩa như sau:

$\begin{cases}H_0=0\\H_m=\sum_{k=1}^m\dfrac{1}{k}\end{cases}$

 

Hãy tính tổng:

$S=\sum_{k=0}^n{n\choose k}^2H_k$



#6
dark templar

dark templar

    Kael-Invoker

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

Đề mới:

 

Bài toán 5:

Tính tổng sau:

$T=\sum_{k=1}^n (-1)^{\frac{k(k+1)}{2}} k2^k$

Chém tạm bài này vậy,bài dưới "bá đạo" quá ! :(

**********

Ý tưởng giải:

Spoiler

Lời giải bài 5:

Phân đoạn $k$ theo module 2 thì ta sẽ có ngay :

 

\[\begin{array}{rcl}S &=& \sum\limits_{k = 1}^n {{{\left( { - 1} \right)}^{\frac{{k\left( {k + 1} \right)}}{2}}}k{2^k}} \\&=& 2\sum\limits_{m = 1}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {{{\left( { - 1} \right)}^m}m{4^m}}  + \frac{1}{2}\sum\limits_{m = 1}^{\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor } {{{\left( { - 1} \right)}^m}\left( {2m - 1} \right){4^m}} \end{array}\]
 
Ta tính từng tổng con riêng :

\[\begin{array}{rcl}2\sum\limits_{m = 1}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {{{\left( { - 1} \right)}^m}m{4^m}}  &=& \frac{2}{5}\sum\limits_{m = 1}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {\Delta \left[ {{{\left( { - 1} \right)}^{m - 1}}{4^m}} \right]m} \\&=& \frac{2}{5}\left\{ {\left[ {{{\left( { - 1} \right)}^{m - 1}}m{4^m}} \right]_{m = 1}^{\left\lfloor {\frac{n}{2}} \right\rfloor  + 1} + 4\sum\limits_{m = 1}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {{{\left( { - 1} \right)}^{m + 1}}{4^m}} } \right\}\\&=& \frac{2}{5}\left\{ {\left[ {{{\left( { - 1} \right)}^{m - 1}}m{4^m}} \right]_{m = 1}^{\left\lfloor {\frac{n}{2}} \right\rfloor  + 1} + \frac{4}{5}\left[ {{{\left( { - 1} \right)}^m}{4^m}} \right]_{m = 1}^{\left\lfloor {\frac{n}{2}} \right\rfloor  + 1}} \right\}\\&=& \frac{2}{5}\left[ {{{\left( { - 1} \right)}^m}{4^m}\left( {\frac{4}{5} - m} \right)} \right]_{m = 1}^{\left\lfloor {\frac{n}{2}} \right\rfloor  + 1} = \frac{2}{5}\left[ {4.{{\left( { - 4} \right)}^{\left\lfloor {\frac{n}{2}} \right\rfloor }}\left( {\frac{1}{5} + \left\lfloor {\frac{n}{2}} \right\rfloor } \right) - \frac{4}{5}} \right]\\&=& \frac{8}{5}\left[ {{{\left( { - 4} \right)}^{\left\lfloor {\frac{n}{2}} \right\rfloor }}\left( {\frac{1}{5} + \left\lfloor {\frac{n}{2}} \right\rfloor } \right) - \frac{1}{5}} \right]\end{array}\]
 
Và :
\[\begin{array}{rcl}\frac{1}{2}\sum\limits_{m = 1}^{\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor } {{{\left( { - 1} \right)}^m}{4^m}\left( {2m - 1} \right)}  &=& \frac{1}{{10}}\sum\limits_{m = 1}^{\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor } {\Delta \left[ {{{\left( { - 1} \right)}^{m - 1}}{4^m}} \right]\left( {2m - 1} \right)} \\ &=& \frac{1}{{10}}\left\{ {\left[ {{{\left( { - 1} \right)}^{m - 1}}{4^m}\left( {2m - 1} \right)} \right]_{m = 1}^{\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor  + 1} - 8\sum\limits_{m = 1}^{\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor } {{{\left( { - 1} \right)}^m}{4^m}} } \right\}\\&=& \frac{1}{{10}}\left\{ {\left[ {{{\left( { - 1} \right)}^{m - 1}}{4^m}\left( {2m - 1} \right)} \right]_{m = 1}^{\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor  + 1} - \frac{8}{5}\left[ {{{\left( { - 1} \right)}^{m - 1}}{4^m}} \right]_{m = 1}^{\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor  + 1}} \right\}\\&=& \frac{1}{{10}}\left[ {{{\left( { - 1} \right)}^{m - 1}}{4^m}\left( {2m - \frac{13}{5}} \right)} \right]_{m = 1}^{\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor  + 1}\\&=& \frac{1}{{10}}\left[ {4{{\left( { - 4} \right)}^{\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor }}\left( {2\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor  - \frac{{3}}{5}} \right) + 4.\frac{{3}}{5}} \right]\\&=& \frac{2}{5}\left[ {{{\left( { - 4} \right)}^{\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor }}\left( {2\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor  - \frac{{3}}{5}} \right) + \frac{{3}}{5}} \right]\end{array}\]
 
Suy ra :
$$S=\dfrac{2}{5}\left[(-4)^{\left\lfloor\frac{n+2}{2}\right\rfloor}\left(\dfrac{4}{5}-\left\lfloor\dfrac{n+2}{2}\right\rfloor\right)+(-4)^{\left\lfloor\frac{n+1}{2}\right\rfloor}\left(2\left\lfloor\dfrac{n+1}{2}\right\rfloor-\dfrac{3}{5}\right)-\dfrac{1}{5}\right]$$
 
Spoiler
 

 


Bài viết đã được chỉnh sửa nội dung bởi dark templar: 15-04-2013 - 20:28

"Do you still... believe in me ?" Sarah Kerrigan asked Jim Raynor - Starcraft II:Heart Of The Swarm.

#7
hxthanh

hxthanh

    Tín đồ $\sum$

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

Đáp án bài số 5

 

Để ý rằng $(-1)^{\frac{k(k+1)}{2}}=\begin{cases}1,\quad k\equiv \{0,3\}\pmod 4\\-1,\quad k\equiv \{1,2\}\pmod 4\end{cases}=\cos\frac{k\pi}{2}-\sin\frac{k\pi}{2}$

 

Vậy tổng cần tính sẽ là:

 

$T=\sum_{k=1}^n(-1)^{\frac{k(k+1)}{2}} k 2^k=-\underbrace{\sum_{k=1}^n k2^k\sin\frac{k\pi}{2}}_{A}+\underbrace{\sum_{k=1}^n k2^k\cos\frac{k\pi}{2}}_{B}$

_________________________________________________________

Trước khi tính các tổng $A$ và $B$ ta xét các tổng sau:

$A'=\sum_{k=1}^n 2^k\sin\frac{k\pi}{2}$ và $B'=\sum_{k=1}^n 2^k\cos\frac{k\pi}{2}$

 

Ta có:

$\begin{align*}A'&=\sum_{k=1}^n\sin\frac{k\pi}{2}\Delta(2^k)\\&=\left.2^k\sin\frac{k\pi}{2}\right|_{k=1}^{n+1}-\sum_{k=1}^n 2^{k+1}\left[\sin\frac{(k+1)\pi}{2}-\sin\frac{k\pi}{2}\right]\\&=2^{n+1}\cos\frac{k\pi}{2}-2+2A'-2B'\end{align*}$

tương tự:

$\begin{align*}B'&=\sum_{k=1}^n\cos\frac{k\pi}{2}\Delta(2^k)\\&=\left.2^k\cos\frac{k\pi}{2}\right|_{k=1}^{n+1}-\sum_{k=1}^n 2^{k+1}\left[\cos\frac{(k+1)\pi}{2}-\cos\frac{k\pi}{2}\right]\\&=-2^{n+1}\sin\frac{k\pi}{2}+2A'+2B'\end{align*}$

 

Từ hai điều trên dễ dàng suy ra:

 

$A'=\sum_{k=1}^n 2^k\sin\frac{k\pi}{2}=\dfrac{1}{5}\left[2^{n+2}\sin\frac{n\pi}{2}-2^{n+1}\cos\frac{n\pi}{2}+2\right]$

$B'=\sum_{k=1}^n 2^k\cos\frac{k\pi}{2}=\dfrac{1}{5}\left[2^{n+2}\cos\frac{n\pi}{2}+2^{n+1}\sin\frac{n\pi}{2}-4\right]$

_________________________________________________________

Quay trở lại việc tính tổng $A$ và $B$, ta có:

$\begin{align*}A&=\sum_{k=1}^n k2^k\sin\frac{k\pi}{2}=\sum_{k=1}^n \sin\frac{k\pi}{2}\Delta\left[(k-2)2^k\right]\\&=\left.(k-2)2^k\sin\frac{k\pi}{2}\right|_{k=1}^{n+1}-\sum_{k=1}^n 2^{k+1}(k-1)\left[\sin\frac{(k+1)\pi}{2}-\sin\frac{k\pi}{2}\right]\\&=(n-1)2^{n+1}\cos\frac{n\pi}{2}+2-\sum_{k=1}^n 2^{k+1}k\cos\frac{k\pi}{2}+\sum_{k=1}^n 2^{k+1}\cos\frac{k\pi}{2}\\&\qquad\qquad\qquad\qquad\qquad+\sum_{k=1}^n 2^{k+1}k\sin\frac{k\pi}{2}-\sum_{k=1}^n 2^{k+1}\sin\frac{k\pi}{2}\\&=(n-1)2^{n+1}\cos\frac{n\pi}{2}+2-2B+2B'+2A-2A'\end{align*}$

tương tự:

$\begin{align*}B&=\sum_{k=1}^n k2^k\cos\frac{k\pi}{2}=\sum_{k=1}^n \cos\frac{k\pi}{2}\Delta\left[(k-2)2^k\right]\\&=\left.(k-2)2^k\cos\frac{k\pi}{2}\right|_{k=1}^{n+1}-\sum_{k=1}^n 2^{k+1}(k-1)\left[\cos\frac{(k+1)\pi}{2}-\cos\frac{k\pi}{2}\right]\\&=-(n-1)2^{n+1}\sin\frac{n\pi}{2}+\sum_{k=1}^n 2^{k+1}k\sin\frac{k\pi}{2}-\sum_{k=1}^n 2^{k+1}\sin\frac{k\pi}{2}\\&\qquad\qquad\qquad\qquad\qquad+\sum_{k=1}^n 2^{k+1}k\cos\frac{k\pi}{2}-\sum_{k=1}^n 2^{k+1}\cos\frac{k\pi}{2}\\&=-(n-1)2^{n+1}\sin\frac{n\pi}{2}+2A-2A'+2B-2B'\end{align*}$


Từ đây tính được $A$ và $B$

và cuối cùng ta có:

 

$\begin{align*}T&=\sum_{k=1}^n (-1)^{\frac{k(k+1)}{2}}k2^k=-A+B\\&=\dfrac{(15n+1)2^{n+1}}{25}\cos\frac{n\pi}{2}-\dfrac{(5n+7)2^{n+1}}{25}\sin\frac{n\pi}{2}-\dfrac{2}{25}\end{align*}$



#8
hxthanh

hxthanh

    Tín đồ $\sum$

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

Đề mới:

...

Bài toán 6:

Số  điều hòa (bậc 1) thứ $m$ được định nghĩa như sau:

$\begin{cases}H_0=0\\H_m=\sum_{k=1}^m\dfrac{1}{k}\end{cases}$

 

Hãy tính tổng:

$S=\sum_{k=0}^n{n\choose k}^2H_k$

Sau đây là đáp án bài toán 6 (ảo lắm đấy! :D)

 

Xét hàm $f(x)={x+a\choose b}=\dfrac{(x+a)(x+a-1)...(x+a-b+1)}{b!}$

Lấy đạo hàm (theo $x$) thì ta được

${x+a\choose b}_{x}^{\prime}=\dfrac{(x+a)(x+a-1)...(x+a-b+1)}{b!} \sum_{j=1}^b \dfrac{1}{x+a+1-j}$

và tại điểm $x=0$ thì ta có:

$$\boxed{\displaystyle \quad{x+a\choose b}_{x=0}^{\prime}={a\choose b}(H_{a}-H_{a-b})\qquad(1)}$$

Đẳng thức $(1)$ chính là chìa khóa của bài toán này :)

 

Rồi từ đẳng thức Vardermonde

$\sum_{k=0}^n{n\choose k}{x+n\choose n-k}={x+2n\choose n}$

Lấy đạo hàm hai vế theo $x$, tại $x=0$ (áp dụng $(1)$), ta được:

 

$\quad\sum_{k=0}^n{n\choose k}{n\choose n-k}(H_n-H_{n-(n-k)})={2n\choose n}(H_{2n}-H_{2n-n})$

$\Leftrightarrow \sum_{k=0}^n {n\choose k}{n\choose n-k}H_n-S={2n\choose n}(H_{2n}-H_{n})$

$\Leftrightarrow {2n\choose n}H_n-S={2n\choose n}(H_{2n}-H_{n})$

 

Và cuối cùng ta có:

$S=\sum_{k=0}^n{n\choose k}^2H_k={2n\choose n}(2H_n-H_{2n})$

 

@supermember: ảo thì cũng chả phải ảo :), đây là 1 dạng " bổ đề" dùng rộng rãi cho mấy bài kiểu này, vậy thì đâu gọi là ảo :D


Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 13-04-2013 - 08:15


#9
hxthanh

hxthanh

    Tín đồ $\sum$

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

Đề mới:

__________

Bài toán 7:

Tính tổng sau:

$S=\sum_{k=1}^n \dfrac{k}{(\sqrt k+\sqrt{k+1})(\sqrt{k+1}+\sqrt{k+2})(\sqrt{k+2}+\sqrt{k})}$

 

Bài toán 8:

Với số nguyên dương $n\ge 2$, hãy tính tổng sau:

$S=\sum_{k=0}^{n^2}{n\choose \left\lfloor\sqrt k\right\rfloor}$

 

@ supermember : thầy thanh gửi cái bài 8 mang tính chất " hù doạ- nguy hiểm" này cho báo THTT là đúng y bóc với cái tinh thần của cái tờ báo ấy.


Bài viết đã được chỉnh sửa nội dung bởi supermember: 08-04-2013 - 19:11


#10
dark templar

dark templar

    Kael-Invoker

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

Đề mới:

__________

Bài toán 7:

Tính tổng sau:

$S=\sum_{k=1}^n \dfrac{k}{(\sqrt k+\sqrt{k+1})(\sqrt{k+1}+\sqrt{k+2})(\sqrt{k+2}+\sqrt{k})}$

 

Bài toán 8:

Với số nguyên dương $n\ge 2$, hãy tính tổng sau:

$S=\sum_{k=0}^{n^2}{n\choose \left\lfloor\sqrt k\right\rfloor}$

Spoiler

Ý tưởng giải:

Spoiler

Lời giải bài 7:

\[\sum\limits_{k = 1}^n {\frac{k}{{\left( {\sqrt k  + \sqrt {k + 1} } \right)\left( {\sqrt {k + 1}  + \sqrt {k + 2} } \right)\left( {\sqrt {k + 2}  + \sqrt k } \right)}}}  = \frac{1}{2}\sum\limits_{k = 1}^n {k\left( {\sqrt {k + 1}  - \sqrt k } \right)\left( {\sqrt {k + 2}  - \sqrt k } \right)\left( {\sqrt {k + 2}  - \sqrt {k + 1} } \right)} \]

 

Dễ thấy rằng:

 

\[\begin{array}{rcl}k\left( {\sqrt {k + 1}  - \sqrt k } \right)\left( {\sqrt {k + 2}  - \sqrt k } \right)\left( {\sqrt {k + 2}  - \sqrt {k + 1} } \right) &=& k\left( {2\sqrt {k + 1}  - \sqrt k  - \sqrt {k + 2} } \right)\\&=&  - k\left( {\Delta \sqrt {k + 1}  - \Delta \sqrt k } \right)\\&=&  - k{\Delta ^2}\left[ {\sqrt k } \right]\end{array}\]
 
Nên theo SPTP thì:


\[\begin{array}{rcl}S &=&  - \frac{1}{2}\sum\limits_{k = 1}^n {k{\Delta ^2}\left[ {\sqrt k } \right]} \\&=& \frac{1}{2}\left\{ {\left[ { - k\Delta \sqrt k } \right]_{k = 1}^{n + 1} + \sum\limits_{k = 1}^n {\Delta \left[ {\sqrt {k + 1} } \right]} } \right\}\\&=& \frac{1}{2}\left\{ { - \left( {n + 1} \right)\left( {\sqrt {n + 2}  - \sqrt {n + 1} } \right) + \sqrt 2  - 1 + \left[ {\sqrt {k + 1} } \right]_{k = 1}^{n + 1}} \right\}\\&=& \frac{{\left( {n + 1} \right)\sqrt {n + 1}  - n\sqrt {n + 2}  - 1}}{2}\end{array}\]
 
Vậy $\boxed{S=\frac{{\left( {n + 1} \right)\sqrt {n + 1}  - n\sqrt {n + 2}  - 1}}{2}}$.
 
**********
Ý tưởng giải:
Spoiler
Lời giải bài 8:
Ta có chút nhận xét sau:
 
Với $n^2-1 \ge k \ge (n-1)^2$ thì $\left\lfloor \sqrt{k} \right\rfloor=n-1$
 
Với $(n-1)^2-1 \ge k \ge (n-2)^2$ thì $\left\lfloor \sqrt{k} \right\rfloor =n-2$.
 
....
Một cách tổng quát thì khi $i^2-1 \ge k \ge (i-1)^2$,ta sẽ có $\left\lfloor \sqrt{k} \right\rfloor =i-1$ và có tổng cộng $i^2-1-(i-1)^2+1=2i-1$ số hạng như vậy.
 
Từ đó,tổng cần tính sẽ là:

\[\begin{eqnarray*}S &=& \sum\limits_{k = 0}^{{n^2}} {\binom{n}{\left\lfloor {\sqrt k } \right\rfloor }} \\&=& 1 + \sum\limits_{k = 0}^{{n^2} - 1} {\binom{n}{\left\lfloor {\sqrt k } \right\rfloor }} \\&=& 1 + \sum\limits_{i = 1}^n {\left( {2i - 1} \right)\binom{n}{i - 1}} \\&=& 1 + \sum\limits_{i = 1}^n {\binom{n}{i - 1}}  + 2\sum\limits_{i = 1}^n {\left( {i - 1} \right)\binom{n}{i - 1}} \\&=& 1 + {2^n} - 1 + 2n\sum\limits_{i = 2}^n {\binom{n - 1}{i - 2}} \quad &\text{(Quy tắc hút)} \\&=& {2^n} + 2n\left( {{2^{n - 1}} - 1} \right)\\&=& {2^n}\left( {n + 1} \right) - 2n\end{eqnarray*}\]
 
Vậy $\boxed{S={2^n}\left( {n + 1} \right) - 2n}$.
 
 

 


Bài viết đã được chỉnh sửa nội dung bởi dark templar: 15-04-2013 - 20:33

"Do you still... believe in me ?" Sarah Kerrigan asked Jim Raynor - Starcraft II:Heart Of The Swarm.

#11
dark templar

dark templar

    Kael-Invoker

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

Lâu nay toàn anh Thanh ra đề,thôi thì hôm nay em sẽ "đáp lễ" 2 bài sau : :)

 

Bài toán 9: Tính $S=\sum_{k=0}^{n}\binom{2n-k}{k}2^{k}$.

 

Bài toán 10: Tính $S=\sum_{k=0}^{n}\binom{n}{k}(k+a)^{k-1}(n-k+b)^{n-k-1} \quad (a,b \in \mathbb{N^*})$.


Bài viết đã được chỉnh sửa nội dung bởi dark templar: 09-04-2013 - 20:28

"Do you still... believe in me ?" Sarah Kerrigan asked Jim Raynor - Starcraft II:Heart Of The Swarm.

#12
hxthanh

hxthanh

    Tín đồ $\sum$

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

Lâu nay toàn anh Thanh ra đề,thôi thì hôm nay em sẽ "đáp lễ" 2 bài sau : :)

 

Bài toán 9: Tính $S=\sum_{k=0}^{n}\binom{2n-k}{k}2^{k}$.

Trước hết hxthanh xin giải Bài toán 9 như sau:

 

Đặt $S_n=\sum_{k=0}^n 2^k{2n-k\choose k}$ và $P_n=\sum_{k=0}^n 2^k{2n-1-k\choose k}$

Ta có:

$\begin{align*}S_n-P_n&=\left[1+\sum_{k=1}^n 2^k {2n-k\choose k}\right]-\left[1+\sum_{k=1}^n 2^k {2n-1-k\choose k}\right]\\&=\sum_{k=1}^n 2^k{2n-1-k\choose k-1}\\&=\sum_{k=0}^{n-1}2^{k+1}{2n-2-k\choose k}\\&=2S_{n-1}\end{align*}\quad(1)$

Mặt khác:

$\begin{align*}S_{n+1}&=1+\sum_{k=1}^{n+1} 2^k {2n+2-k\choose k}\\&=1+\sum_{k=1}^{n+1} 2^k\left[{2n+1-k\choose k-1}+{2n-k\choose k-1}+{2n-k\choose k}\right]\\&=\left[1+\sum_{k=1}^{n+1}2^k{2n-k\choose k}\right]+\sum_{k=0}^{n}2^{k+1}\left[{2n-k\choose k}+{2n-1-k\choose k}\right]\\&=3S_n+2P_n\end{align*}\quad(2)$

 

Từ $(1)$ và $(2)$ dễ dàng suy ra $S_{n+1}-5S_n+4S_{n-1}=0$

Với giá trị (tính được) $S_0=1, S_1=3$ ta dễ dàng suy ra được công thức tổng quát cho $S_n$

$$\boxed{\displaystyle S_n=\sum_{k=0}^n 2^k{2n-k\choose k}=\dfrac{2^{2n+1}+1}{3}}$$



#13
dark templar

dark templar

    Kael-Invoker

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

Bài toán 9: Tính $S=\sum_{k=0}^{n}\binom{2n-k}{k}2^{k}$.

Em xin đưa ra 1 lời giải bằng hàm sinh như sau :)

**********

Trước tiên,theo quy tắc đảo chiều thì :

\[S = \sum\limits_{k = 0}^n {{2^k}\binom{2n - k}{k}}  = \sum\limits_{k = 0}^n {{2^{n - k}}\binom{n + k}{n - k}}  = \sum\limits_{k = 0}^n {{2^{n - k}}\binom{n + k}{2k}} \]

 

Nhắc lại định lý A sau :

\[\sum\limits_k {\binom{n + ak}{m + bk}{z^{n - m + \left( {a - b} \right)k}}{f_k}}  = \left[ {{t^n}} \right]\frac{{{t^m}}}{{{{\left( {1 - zt} \right)}^{m + 1}}}}f\left( {\frac{{{t^{b - a}}}}{{{{\left( {1 - zt} \right)}^b}}}} \right)\quad \left( {b > a} \right)\]

 

Áp dụng vào bài toán,ta có:

 

\[\begin{array}{rcl}S &=& \left[ {{t^n}} \right]\frac{1}{{1 - 2t}}\left[ {\left. {\frac{1}{{1 - u}}} \right|u = \frac{t}{{{{\left( {1 - 2t} \right)}^2}}}} \right]\\&=& \left[ {{t^n}} \right]\frac{{1 - 2t}}{{{{\left( {1 - 2t} \right)}^2} - t}}\\&=& \left[ {{t^n}} \right]\frac{{1 - 2t}}{{\left( {1 - t} \right)\left( {1 - 4t} \right)}}\\&=& \left[ {{t^n}} \right]\frac{1}{{1 - t}} + \left[ {{t^n}} \right]\frac{{2t}}{{\left( {1 - t} \right)\left( {1 - 4t} \right)}}\\&=& 1 + \frac{2}{3}\left[ {{t^n}} \right]\left( {\frac{1}{{1 - 4t}} - \frac{1}{{1 - t}}} \right)\\&=& \frac{1}{3} + \frac{2}{3}{.4^n} = \frac{{{2^{2n + 1}} + 1}}{3}\end{array}\]

"Do you still... believe in me ?" Sarah Kerrigan asked Jim Raynor - Starcraft II:Heart Of The Swarm.

#14
hxthanh

hxthanh

    Tín đồ $\sum$

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

Bài toán 10: Tính $S=\sum_{k=0}^{n}\binom{n}{k}(k+a)^{k-1}(n-k+b)^{n-k-1} \quad (a,b \in \mathbb{N^*})$.

Bài này bá đạo quá!

 

Spoiler



#15
dark templar

dark templar

    Kael-Invoker

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

Bài này bá đạo quá!

 

Spoiler

Kết quả của anh đúng rồi nhưng em cũng không có lời giải cho bài này đâu anh ạ :P Bài này em lấy từ ML...

 

Thôi thì ta cứ để bài này nghiên cứu sau,anh post tiếp đề mới đi ạ :)


"Do you still... believe in me ?" Sarah Kerrigan asked Jim Raynor - Starcraft II:Heart Of The Swarm.

#16
hxthanh

hxthanh

    Tín đồ $\sum$

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

Để lấy lại cảm hứng mời các bạn thư giãn với 4 bài khá đơn giản sau:

 

Bài toán 11

Tính $S=\sum_{k=1}^nk(-1)^k2^{k(-1)^k}$

 

Bài toán 12

Tính $S=\sum_{k=0}^n\dfrac{k}{4k^4+1}$

 

Bài toán 13

Tính $S=\sum_{k=0}^n\left[{3n-k\choose n+k}+{3n+k\choose n-k}\right]$

 

Bài toán 14

Tính $S=\sum_{k=1}^n(-1)^{{k+2\choose 3}}2^k$

Spoiler



#17
hxthanh

hxthanh

    Tín đồ $\sum$

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

$\Delta\left((-1)^k\left\lfloor\dfrac{(-1)^kk(k+1)}{3}\right\rfloor\right)=\left\lfloor\dfrac{k+2}{2}\right\rfloor+\left\lfloor\dfrac{k+2}{6}\right\rfloor$

 

Không phải "vô cớ" mà tìm ra được cái này! :)

Đặt $f(k)=\left((-1)^k\left\lfloor\dfrac{(-1)^kk(k+1)}{3}\right\rfloor\right)$

Trước khi nghĩ đến việc tìm sai phân của $f(k)$, ta hãy khảo sát $f(k)$ theo các số dư modulo $6$.

Tại sao lại xét theo modulo $6?$ mà không phải là $3$?

Tại vì $(-1)^k$ biến thiên tuần hoàn theo modulo $2$, phân thức còn lại thì biến thiên tuần hoàn theo modulo $3$.

Vậy kết hợp lại ta cần khảo sát $f(k)$ theo modulo $6$


Đặt $k=6m+r$ ở đây $r$ là tập hợp (từng trường hợp tương ứng) các số dư. Ta viết dạng thống kê là $r=\{0,1,2,3,4,5\}$

Khi đó ta có:

$\begin{align*}f(k)&=(-1)^{6m+r}\left\lfloor\dfrac{(-1)^{6m+r}(6m+r)(6m+r+1)}{3}\right\rfloor\\&=(-1)^r\left\lfloor(-1)^r\left(12m^2+4mr+2m+\dfrac{r(r+1)}{3}\right)\right\rfloor\\&=12m^2+4mr+2m+(-1)^r\left\lfloor\dfrac{(-1)^rr(r+1)}{3}\right\rfloor\\&=12m^2+4mr+2m+\{0,1,2,4,6,10\}\end{align*}$

(Tập hợp cuối được tính theo mỗi trường hợp từ $r=0$ đến $r=5$)

Tương tự

$\begin{align*}f(k+1)&=(-1)^{6m+r+1}\left\lfloor\dfrac{(-1)^{6m+r+1}(6m+r+1)(6m+r+2)}{3}\right\rfloor\\&=(-1)^{r+1}\left\lfloor(-1)^{r+1}\left(12m^2+4mr+6m+r+\dfrac{r^2+2}{3}\right)\right\rfloor\\&=12m^2+4mr+6m+r+(-1)^{r+1}\left\lfloor\dfrac{(-1)^{r+1}(r^2+2)}{3}\right\rfloor\\&=12m^2+4mr+6m+r+\{1,1,2,3,6,9\}\\&=12m^2+4mr+6m+\{1,2,4,6,10,14\}\end{align*}$

Suy ra:

$\Delta f(k)=f(k+1)-f(k)=4m+\{1,1,2,2,4,4\}$

$\qquad=4\left\lfloor\dfrac{k}{6}\right\rfloor+\{1,1,2,2,3,3\}+\{0,0,0,0,1,1\}$

$\qquad=4\left\lfloor\dfrac{k}{6}\right\rfloor+\left\lfloor\dfrac{r+2}{2}\right\rfloor+\left\lfloor\dfrac{r+2}{6}\right\rfloor$

$\qquad=4\left\lfloor\dfrac{k}{6}\right\rfloor+\left\lfloor\dfrac{k-6\left\lfloor\frac{k}{6}\right\rfloor+2}{2}\right\rfloor+\left\lfloor\dfrac{k-6\left\lfloor\frac{k}{6}\right\rfloor+2}{6}\right\rfloor$

$\qquad=4\left\lfloor\dfrac{k}{6}\right\rfloor-3\left\lfloor\dfrac{k}{6}\right\rfloor+\left\lfloor\dfrac{k+2}{2}\right\rfloor-\left\lfloor\dfrac{k}{6}\right\rfloor+\left\lfloor\dfrac{k+2}{6}\right\rfloor$

$\qquad=\left\lfloor\dfrac{k+2}{2}\right\rfloor+\left\lfloor\dfrac{k+2}{6}\right\rfloor$

:))



#18
dark templar

dark templar

    Kael-Invoker

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

Để lấy lại cảm hứng mời các bạn thư giãn với 4 bài khá đơn giản sau:

 

Bài toán 11

Tính $S=\sum_{k=1}^nk(-1)^k2^{k(-1)^k}$

 

Bài toán 12

Tính $S=\sum_{k=0}^n\dfrac{k}{4k^4+1}$

Spoiler

Ý tưởng giải:

Spoiler

Lời giải bài 11:

Phân đoạn $k$ theo modulo 2 thì:

 

\[\begin{array}{rcl}S &=& \sum\limits_{k = 1}^n {k{{\left( { - 1} \right)}^k}{2^{k{{\left( { - 1} \right)}^k}}}} \\&=& 2\sum\limits_{m = 1}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {m{4^m}}  - 2\sum\limits_{m = 1}^{\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor } {\frac{{2m - 1}}{{{4^m}}}} \\&=& \frac{2}{3}\sum\limits_{m = 1}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {m\Delta \left[ {{4^m}} \right]}  + \frac{2}{3}\sum\limits_{m = 1}^{\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor } {\left( {2m - 1} \right)\Delta \left[ {\frac{1}{{{4^{m - 1}}}}} \right]} \\&=& \frac{2}{3}\left[ {m{4^m}} \right]_{m = 1}^{\left\lfloor {\frac{{n + 2}}{2}} \right\rfloor } - \frac{8}{9}\sum\limits_{m = 1}^{\left\lfloor {\frac{n}{2}} \right\rfloor } {\Delta \left[ {{4^m}} \right]} \\&+& \frac{2}{3}\left( {\left[ {\frac{{2m - 1}}{{{4^{m - 1}}}}} \right]_{m = 1}^{\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor  + 1} + \frac{2}{3}\sum\limits_{m = 1}^{\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor } {\Delta \left[ {\frac{1}{{{4^{m - 1}}}}} \right]} } \right)\\&=& \frac{2}{3}\left[ {\left( {m - \frac{4}{3}} \right){4^m}} \right]_{m = 1}^{\left\lfloor {\frac{{n + 2}}{2}} \right\rfloor } + \frac{2}{3}\left[ {\frac{{2m - \frac{1}{3}}}{{{4^{m - 1}}}}} \right]_{m = 1}^{\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor  + 1}\end{array}\]

 

Sau khi rút gọn,ta sẽ thu được kết quả là:

\[\boxed{\displaystyle S = \frac{{{{8.4}^{\left\lfloor {\frac{n}{2}} \right\rfloor }}\left( {3\left\lfloor {\frac{n}{2}} \right\rfloor  - 1} \right)}}{9} + \frac{{12\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor  + 10}}{{{{9.4}^{\left\lfloor {\frac{{n + 1}}{2}} \right\rfloor }}}} - \frac{2}{9}}\]

 

**********

Ý tưởng giải:

Spoiler

Lời giải bài 12:

Ta xét số hạng tổng quát:

 

\[\begin{array}{rcl}\frac{k}{{4{k^4} + 1}} &=& \frac{k}{{{{\left( {2{k^2} + 1} \right)}^2} - 4{k^2}}}\\&=& \frac{k}{{\left( {2{k^2} + 2k + 1} \right)\left( {2{k^2} - 2k + 1} \right)}}\\&=& \frac{1}{4}\left( {\frac{1}{{2{k^2} - 2k + 1}} - \frac{1}{{2{k^2} + 2k + 1}}} \right)\\&=& \frac{1}{4}\left[ {\frac{1}{{2{k^2} - 2k + 1}} - \frac{1}{{2{{\left( {k + 1} \right)}^2} - 2\left( {k + 1} \right) + 1}}} \right]\\&=& \frac{{ - 1}}{4}\Delta \left[ {\frac{1}{{2{k^2} - 2k + 1}}} \right]\end{array}\]
 
Từ đó theo SPTP thì ta sẽ có:
\[\boxed{\displaystyle S = \frac{1}{4}\left[ {\frac{1}{{2{k^2} - 2k + 1}}} \right]_{k = n + 1}^0 = \frac{{n\left( {n + 1} \right)}}{{2\left( {2{n^2} + 2n + 1} \right)}}}\]
 
____________________________________
@hxthanh: Tinh thần chung của cả hai bài đều đúng, tuy nhiên bài 11 em tính sai rồi! :luoi:
@Dark templar: Đã sửa. :P

Bài viết đã được chỉnh sửa nội dung bởi dark templar: 15-04-2013 - 20:42

"Do you still... believe in me ?" Sarah Kerrigan asked Jim Raynor - Starcraft II:Heart Of The Swarm.

#19
hxthanh

hxthanh

    Tín đồ $\sum$

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

Đáp án bài số 11

 

$\begin{align*}\sum_{k=1}^nk(-1)^k2^{k(-1)^k}&=\sum_{m=1}^{\left\lfloor\frac{n}{2}\right\rfloor}m2^{2m+1}+\sum_{m=1}^{\left\lfloor\frac{n+1}{2}\right\rfloor}\dfrac{1-2m}{2^{2m-1}}\\&=\sum_{m=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\Delta\left[\dfrac{(3m-4)2^{2m+1}}{9}\right]+\sum_{m=1}^{\left\lfloor\frac{n+1}{2}\right\rfloor}\Delta\left[\dfrac{6m-1}{9.2^{2m-3}}\right]\\&=\left[\dfrac{(3m-4)2^{2m+1}}{9}\right]_{m=1}^{\left\lfloor\frac{n}{2}\right\rfloor+1}+\left[\dfrac{6m-1}{9.2^{2m-3}}\right]_{m=1}^{\left\lfloor\frac{n+1}{2}\right\rfloor+1}\\&\\&=\dfrac{\left(24\left\lfloor\frac{n}{2}\right\rfloor-8\right)4^{\left\lfloor\frac{n}{2}\right\rfloor}}{9}+\dfrac{\left(12n+10-12\left\lfloor\frac{n}{2}\right\rfloor\right)4^{\left\lfloor\frac{n}{2}\right\rfloor}}{9.4^n}-\dfrac{2}{9}\end{align*}$



#20
dark templar

dark templar

    Kael-Invoker

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

Bài toán 14

Tính $S=\sum_{k=1}^n(-1)^{{k+2\choose 3}}2^k$

Spoiler

Spoiler

 

Bài toán 14: 

Spoiler

Bài viết đã được chỉnh sửa nội dung bởi dark templar: 12-04-2013 - 17:31

"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: dark templar, hxthanh, for all

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

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