Nào! Bây giờ để mình giúp các bạn bước đầu tiên!
Để tránh nhầm lẫn mình sẽ ký hiệu lại:
\begin{align}
\label{p1} x^n+y^n&=\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor} V(n,k) (xy)^k(x+y)^{n-2k}\quad\\
\label{p2} \cos(nx)&=\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor} T(n,k) \cos^{n-2k}x\quad
\end{align}
Bước đầu ta sẽ chứng minh
\begin{equation}\label{p3}
V(n,k)=(-1)^k\left[{n+1-k\choose k}-{n-1-k\choose k-2}\right]
\end{equation}
Trong \eqref{p3} thì $n>0$ vì trường hợp đặc biệt
Khi $n=0$ thì \eqref{p1} sẽ trở thành:
$x^0+y^0=V(0,0)(xy)^0(x+y)^0$
Một cách hợp lý thì “người ta” quy ước rằng $V(0,0)=2$.
Ta có:
$(x+y)(x^{n-1}+y^{n-1})=x^n+y^n+(xy)(x^{n-2}+y^{n-2})$
Thay vào trong \eqref{p1} ta được:
\begin{align*}
\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} V(n-1,k)(xy)^k(x+y)^{n-2k}&=\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor} V(n,k)(xy)^k(x+y)^{n-2k}+\sum_{k=0}^{\left\lfloor\frac{n-2}{2}\right\rfloor} V(n-2,k)(xy)^{k+1}(x+y)^{n-2-2k}\\
&=\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor} V(n,k)(xy)^k(x+y)^{n-2k}+\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor} V(n-2,k-1)(xy)^{k}(x+y)^{n-2k}
\end{align*}
Từ đây suy ra
\begin{equation}\label{p4}
V(n,k)=V(n-1,k)-V(n-2,k-1)
\end{equation}
Với \eqref{p4} việc chứng minh \eqref{p3} bằng quy nạp (theo $k$ và $n$) không còn là vấn đề khó khăn. Đặt vấn đề ngược lại, từ các dữ kiện đã biết ta “tìm ra” \eqref{p3} như thế nào?
Tiếp tục vấn đề nêu trên: Ngoài định nghĩa \eqref{p1} với quy ước $V(0,0)=2$ ta mới chỉ tìm được thêm được hệ thức \eqref{p4}
Trong \eqref{p1} cho $y=1$ ta có:
$x^n+1=\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}V(n,k)x^k(x+1)^{n-2k}$
Do hệ số $x^n$ ở vế trái bằng $1$ nên suy ra:
\begin{equation}\label{p5}
V(n,0)=1, \forall n>0;\quad V(0,0)=2
\end{equation}
$\diamond$ Tiếp theo ta tính $V(n,1)$
$V(n,1)=V(n-1,1)-V(n-2,0)=V(n-1,1)-1\quad$ (theo \eqref{p4})
Viết lại:
\begin{align*}
V(n,1)&=V(n-1,1)-1\\
V(n-1,1)&=V(n-2,1)-1\\
… &= …\\
V(3,1)&=V(2,1)-1\\
V(2,1)&=V(1,1)-2
\end{align*}
Cộng vế theo vế ta có
$V(n,1)=(-1)(n-2)-2$ (Dĩ nhiên $V(n,k)=0, \forall k>\frac{n}{2}$)
\begin{equation}\label{p6}
V(n,1)=-n, \forall n>1
\end{equation}
$\diamond$ Tính $V(n,2)$. Theo \eqref{p4} và \eqref{p6}
\begin{align*}
V(n,2)&=V(n-1,2)+(n-2)\\
V(n-1,2)&=V(n-2,2)+(n-3)\\
… &= …\\
V(4,2)&=V(3,2)+2
\end{align*}
Cộng vế theo vế ta có:
\begin{align*}
V(n,2)&=\sum_{k=2}^{n-2}k\\ &=\sum_{k=2}^{n-2}\left({k+1\choose 2}-{k\choose 2}\right)\\ &={n-1\choose 2}-1
\end{align*}
Vậy
\begin{equation}\label{p7}
V(n,2)={n-1\choose 2}-1
\end{equation}
Đến đây mọi thứ đang dần dần “sáng tỏ”
$\diamond$ Tính $V(n,3)$
Theo \eqref{p4} và \eqref{p7}, ta có:
\begin{align*}
V(n,3)&=V(n-1,3)-{n-3\choose 2}+1\\
V(n-1,3)&=V(n-2,3)-{n-4\choose 2}+1\\
… &= …\\
V(6,3)&=V(5,3)-{3\choose 2}+1
\end{align*}
Cộng vế theo vế, ta được:
\begin{align*}
V(n,3)&=\sum_{k=3}^{n-3}\left(1-{k\choose 2}\right)\\
&=(n-5)-{n-2\choose 3}+{3\choose 3}
&=-\left[{n-2\choose 3}-{n-4\choose 1}\right]
\end{align*}
Vậy
\begin{equation}\label{p8}
V(n,3)=-\left[{n-2\choose 3}-{n-4\choose 1}\right]
\end{equation}
Clear!!! Quy nạp \eqref{p3} theo $k$ được rồi!
$\diamond$ Chứng minh quy nạp
Giả thiết quy nạp \eqref{p3} đúng với $k=0,1,2,3$. Giả sử \eqref{p3} đúng với $k$. Xét với $k+1$
Theo \eqref{p4}, ta có:
\begin{align*}
V(n,k+1)&=V(n-1,k+1)-V(n-2,k)\\
\Rightarrow V(n,k+1)&=V(n-1,k+1)+(-1)^{k+1}\left[{n-1-k\choose k}-{n-3-k\choose k-2}\right]\\
\Rightarrow V(n-1,k+1)&=V(n-2,k+1)+(-1)^{k+1}\left[{n-2-k\choose k}-{n-4-k\choose k-2}\right]\\
\Rightarrow …&=…\\
\Rightarrow V(2k+2,k+1)&=V(2k+1,k+1)+(-1)^{k+1} \left[{k+1\choose k}-{k-1\choose k-2}\right]
\end{align*}
Cộng vế theo vế ta được:
\begin{align*}
V(n,k+1)&=(-1)^{k+1}\sum_{j=k+1}^{n-1-k}\left[{j\choose k}-{j-2\choose k-2}\right]\\
&=(-1)^{k+1}\left[{n-k\choose k+1}-{k+1\choose k+1}-{n-k-2\choose k-1}+{k-1\choose k-1}\right]\\
&=(-1)^{k+1}\left[{n-k\choose k+1}-{n-k-2\choose k-1}\right]
\end{align*}
Vậy \eqref{p3} đúng với $k+1$
Theo nguyên lý quy nạp ta có điều phải chứng minh.
DONE!
…
Giờ đến phần “liên hệ” giữa $V(n,k)$ với $T(n,k)$
các bạn hãy “tiếp sức” nhé!
Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 01-04-2023 - 00:41
Như vậy là vấn đề “Khai triển tổng và tích” đã được giải quyết xong! \eqref{p2} lại là một bài toán khác: Công thức tổng quát cho $\cos(nx)$ là một thứ nhìn rất quen thuộc với chúng ta, đó chính là Đa thức Chebychev loại I Nghe cứ thấy nó “sai sai” thế nào ấy?
Từ công thức Moivre
$e^{ix}=\cos(nx)+i\sin(nx)=(\cos x+i \sin x)^n$
Khai triển ra ta có ngay:
\begin{align}\label{p9}
\cos(nx)=\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor} {n \choose 2k}(\cos^2x-1)^k\cos^{n-2k}x
\end{align}
Mấy cái công thức lượng giác này thì liên quan gì đến hệ số khai triển Viète ở \eqref{p1} kia chứ?
Để làm rõ hơn về \eqref{p3}, lần này ta biểu diễn lại dưới dạng gọn hơn là:
\begin{equation}\label{p10}
V(n,k)=\dfrac{(-1)^kn}{n-k} {n-k\choose k},\;\;(n>0)
\end{equation}
… còn tiếp …
Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 01-04-2023 - 16:20
… Có vẻ như chưa có ai sẵn sàng tiếp sức, thôi thì mình tiếp tục cố gắng vậy! (Mình đã viết toàn bộ “nghiên cứu” về bài toán này trong một cuốn sổ tay cách đây… 12 năm trước, giờ tìm đâu cũng không thấy )
Bây giờ có hai hướng để giải quyết. Một là xây dựng công thức truy hồi cho $T(n,k)$ tương tự như \eqref{p4} rồi dựa trên công thức \eqref{p10} chứng minh bằng quy nạp cho $T(n,k)$. Hướng thứ hai phức tạp hơn một chút là từng bước lần mò “dự đoán” công thức xác định cho $T(n,k)$ để thấy rõ hơn mối quan hệ giữa $V(n,k)$ và $T(n,k)$ hay các “số” tương tự.
Mình sẽ bắt đầu với hướng thứ nhất trước!
Dựa trên công thức lượng giác “tích thành tổng” ta có đẳng thức sau:
\begin{equation*}
2\cos((n-1)x)\cos x=\cos(nx)+\cos((n-2)x)
\end{equation*}
Kết hợp đẳng thức này với định nghĩa \eqref{p2}, ta có công thức truy hồi:
\begin{equation}\label{p11}
T(n,k)=2T(n-1,k)-T(n-2,k-1)
\end{equation}
Dựa trên \eqref{p3}, ta sẽ chứng minh bằng quy nạp công thức
\begin{equation}\label{p12}
T(n,k)=(-1)^k2^{n-1-2k}\left[{n+1-k\choose k}-{n-1-k\choose k-2}\right] \;(n>0)
\end{equation}
Còn nữa: $T(0,0)=2^{-1}V(0,0)=1$
Ta có \eqref{p12} đúng với $k=0,1,2,…$ cái này bạn đọc tự kiểm chứng (tương tự như ở phần đầu)
Giả thiết quy nạp đúng đến $k$. Xét với $k+1$
\begin{align*}
T(n,k+1)&=2T(n-1,k+1)-T(n-2,k) \\
2T(n-1,k+1)&=2^2T(n-2,k+1)-2T(n-3,k) \\
…&=…\\
2^{n-2-2k}T(2k+2,k+1)&=2^{n-1-2k}T(2k+1,k+1)-2T(2k,k)
\end{align*}
Cộng vế theo vế ta được:
\begin{align*}
&T(n,k+1)=-\sum_{j=0}^{n-2-2k} 2^jT(n-2-j,k)\\
\;\;&=-\sum_{j=0}^{n-2-2k}2^j.2^{n-3-j-2k}(-1)^k\left[{n-1-j-k\choose k}-{n-3-j-k\choose k-2}\right]\quad(gtqn)\\
&=(-1)^{k+1}2^{n-3-2k}\sum_{j=0}^{n-2-2k}\left[{j+1+k\choose k}-{j-1+k\choose k-2}\right]\quad(invert \;index)\\
&=(-1)^{k+1}2^{n-3-2k}\left[{n-k\choose k+1}-{k+1\choose k+1}-{n-2-k\choose k-1}+{k-1\choose k-1}\right]\\
&=(-1)^{k+1}2^{n-3-2k}\left[{n-k\choose k+1}-{n-2-k\choose k-1}\right]
\end{align*}
Chứng minh quy nạp hoàn tất.
Bài toán được giải quyết xong!
…
Còn tiếp…
Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 02-04-2023 - 20:56
Trước khi nói về hướng giải quyết thứ hai, ta hãy đào sâu thêm về một số “thành quả” thu được:
Từ \eqref{p9} và \eqref{p10} ta có Bài toán
Với số nguyên dương $n$ chứng minh rằng:
$\sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor} {n\choose 2j} {j\choose k}=\frac{2^{n-1-2k}n}{n-k} {n-k\choose k}$
Ta biết rằng tổng các hệ số của đa thức Chebychev bằng $1$. Vậy tổng các hệ số “đa thức Viète” bằng bao nhiêu?. Ta có: Bài toán
Với số nguyên dương $n$ chứng minh rằng:
$\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor} \frac{(-1)^{k}n}{n-k} {n-k\choose k}=2\cos\left(\frac{n\pi}{3}\right)$
Nếu chi lấy tổng trị tuyệt đối các hệ số $V(n,k)$ thì ta có: Bài toán
Với số nguyên dương $n$ chứng minh rằng:
$\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor} \frac{n}{n-k} {n-k\choose k}=L_n$
Trong đó: $(L_n)$ là dãy số Lucas
$L_1=1; L_2=3;\;\; L_n=L_{n-1}+L_{n-2}$
Ba bài toán này còn có vế phải để mà gợi ý. Thử bỏ đi vế phải và đặt câu hỏi tính vế trái thì… phê!
Các bạn có thấy “ảo” không? Hãy thử giải quyết các bài toán trên nhé!
Mình sẽ trở lại sau!
Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 02-04-2023 - 23:02
Do đó VT thực chất là hệ số của $x^k$ trong khai triển $$u_n(x) = \frac{\left(\sqrt{x+1}+1\right)^n+\left(1 - \sqrt{x+1}\right)^n}{2}$$
Dễ dàng nhận thấy $u_{n+2}(x) = 2u_{n+1}(x) + xu_n(x)$, do đó đặt $F(n,t)$ là hệ số của $x^t$ trong $u_n(x)$ thì \begin{equation}\label{(1)} f(n,t) = 2f(n-1,t) + f(n-2,t-1)\end{equation}
Đặt $T(n,t) = \frac{F(n,t)}{(-1)^t}$ thì $(1)$ trở thành $$T(n,t) = 2T(n-1,t) - T(n-2,t-1)$$
Do đó hàm $T$ ở đây trùng với hàm $T$ của bài viết. Vậy $\boxed{\displaystyle \sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor} {n\choose 2j} {j\choose k}=\frac{2^{n-1-2k}n}{n-k} {n-k\choose k}}$.
P/s: Ban đầu em có đọc post kia của thầy Thành trước nhưng chỉ làm được đến $(1)$. Đọc post này mới nhận ra hai hàm này gần như giống nhau.
Bài viết đã được chỉnh sửa nội dung bởi Hoang72: 04-04-2023 - 11:06
Làm tốt lắm @Hoang72 !
Vậy là mình không còn “độc diễn” trong topic này nữa . Sở dĩ mình “đẩy” các bài toán này ra bên ngoài là muốn tìm thêm các phương án tiếp cận khác, từ đó phát triển một lớp các bài toán về “Truy hồi 2 biến”
Trong bài này là một ví dụ!
Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 04-04-2023 - 11:17
Đã gửi 04-11-2011 - 00:21
)
. Sở dĩ mình “đẩy” các bài toán này ra bên ngoài là muốn tìm thêm các phương án tiếp cận khác, từ đó phát triển một lớp các bài toán về “Truy hồi 2 biến”
newton, khai triển
