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

[Math04]

Cho dãy $a_{1},a_{2},a_{3},...,a_{n}$ sao cho $a_{i} \in \left \{ 0,1,2 \right \}$ và $\left | a_{i}-a_{i+1} \right |\leq 1, \forall i$. Tìm số các dãy $a_{1},a_{2},a_{3},...,a_{n}$ thỏa điều kiện đã cho.

[perfectstrong]

Thử dùng truy hồi xem sao

Gọi $S(n,k)$ là số dãy số có độ dài $n$ thỏa đề và tận cùng là $k$, tức $a_n = k \in \{ 0, 1, 2\}$. Ta cần tìm số dãy số thỏa đề $T(n) = S(n,0)+S(n,1)+S(n,2)$.

Mà từ điều kiện $|a_i - a_{i+1}| \le 1$ thì có thể thấy :

- Nếu $a_{n}=0$ thì $a_{n-1}\in{0,1}$, nên $S(n,0) = S(n-1,0) + S(n-1,1)$.

- Nếu $a_{n}=2$ thì $a_{n-1} \in {1,2}$, nên $S(n,2) = S(n-1,1) + S(n-1,2)$.

- Nếu $a_{n}=1$ thì $a_{n-1} \in {0, 1,2}$, nên $S(n,1) = S(n-1,0) + S(n-1,1) + S(n-1,2)=T(n-1)$.

Vậy $$\begin{align*} T(n) & = S(n,0)+S(n,1)+S(n,2) \\ & = S(n-1,0)+2S(n-1,1)+S(n-1,2)+T(n-1) \\ & =2T(n-1)+T(n-2) \end{align*}$$

Lại có $T(1)=3$ và $T(2)=7$, ta tìm ra CTTQ \[T\left( n \right) = \frac{{{{\left( {1 + \sqrt 2 } \right)}^{n + 1}} + {{\left( {1 - \sqrt 2 } \right)}^{n + 1}}}}{2}\]

Hoặc đơn giản hơn tí thì:

\[T\left( n \right) = \left\lfloor {\frac{{{{\left( {1 + \sqrt 2 } \right)}^{n + 1}} + 1}}{2}} \right\rfloor \]

[hxthanh]

Cho dãy $a_{1},a_{2},a_{3},...,a_{n}$ sao cho $a_{i} \in \left \{ 0,1,2 \right \}$ và $\left | a_{i}-a_{i+1} \right |\leq 1, \forall i$. Tìm số các dãy $a_{1},a_{2},a_{3},...,a_{n}$ thỏa điều kiện đã cho.

Bài này có đáp án bằng hàm sinh là:
$$[x^{n}]:\quad \dfrac{1+x}{1-2x-x^2}$$
Nhưng quả thực mình đọc không hiểu họ xây dựng sao ra như vậy!?
@Nobodyv3 hay ai đó có thể giải thích giúp mình được không?

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 28-03-2023 - 21:45

[Nobodyv3]

Lỗi rồi...
Em xin phép viết lại hệ thức truy hồi của anh @perfectstrong là :
$\begin {cases}
T_n=2T_{n-1}+T_{n-2}\\
T_0=1,\quad T_1=3
\end {cases}$
Đặt $G(x)=\sum_{n=0}^{\infty }T_nx^n$. Nhân $x^n$ cả 2 vế:
$T_nx^n=2T_{(n-1)}x^n+T_{(n-2)}x^n$
Cho $n$ chạy từ $2$ đến $\infty $ rồi cộng vế với vế:
$\sum_{n=2}^{\infty }T_nx^n=\sum_{n=2}^{\infty }2T_{(n-1)}x^n+\sum_{n=2}^{\infty }T_{(n-2)}x^n$
Suy ra :
$\begin {align*}
&\Rightarrow \sum_{n=0}^{\infty }T_nx^n-T_0-T_1x=\sum_{n=2}^{\infty }T_{(n-1)}2x.x^{n-1}+\sum_{n=2}^{\infty }T_{(n-2)}x^2.x^{n-2}\\
&\Rightarrow
G(x)-1-3x=2x(G(x)-T_0)+x^2G(x)\\
&\Rightarrow G(x)(1-2x-x^2)=1+x\\
&\Rightarrow \boldsymbol {G(x)=\frac {1+x}{1-2x-x^2}}
\end{align*}$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 28-03-2023 - 17:41

[hxthanh]

\begin {align*}
&…\\
&\Rightarrow \boldsymbol {G(x)=\frac {1+x}{1-2x-x^2}}
\end{align*}

Bây giờ xem như bạn đã tìm ra lời giải bằng hàm sinh cho bài toán này. Giờ làm sao khai triển ra đây?

[Nobodyv3]

Continued.
Ta đã biết :
$\frac{1}{1-\alpha x}=1+\alpha x+\alpha^2x^2+...$ $(1)$
$\frac{1}{1-\beta x}=1+\beta x+\beta^2x^2+...$ $(2)$
Nhân $(1)\times A, (2)\times B$ rồi cộng vế với vế, ta có :
Vế trái :
$$\frac {A}{1-\alpha x}+\frac {B}{1-\beta x}=\frac {A+B+(-A\beta-B\alpha)x}{1-(\alpha+\beta) x+\alpha \beta x^2}$$
Vế phải :
$$(A+B)+(A\alpha+B\beta)x+(A\alpha^2+B \beta^2)x^2+...$$
$\Rightarrow \begin{cases}
1+x=A+B+(-A\beta-B\alpha)x\\
1-2x-x^2=1-(\alpha +\beta )x+\alpha \beta x^2
\end{cases}$ $(3)$
Ta được :
\begin {align*}
G(x)=\frac {1+x}{1-2x-x^2}&=\frac {A+B+(-A\beta-B\alpha)x}{1-(\alpha +\beta )x+\alpha \beta x^2}\\&=\frac {A}{1-\alpha x}+\frac {B}{1-\beta x}\\&=(A+B)+(A\alpha+B\beta)x+(A\alpha^2+B\beta^2)x^2+...
\end {align*}
Suy ra : $T_n=A\alpha^n+B\beta^n$
Giải $(3)$:Từ:
$\begin{cases}
A+B=1\\
-A\beta-B\alpha=1\\
\alpha +\beta =2\\
\alpha \beta =-1
\end{cases}
\Rightarrow
\begin{cases}
\alpha=1+\sqrt 2\\
\beta=1-\sqrt 2 \\
A =\frac {1+\sqrt 2}{2}\\
B =\frac {1-\sqrt 2}{2}
\end{cases}$ hoặc :
$\begin{cases}
\alpha=1-\sqrt 2\\
\beta=1+\sqrt 2 \\
A =\frac {1-\sqrt 2}{2}\\
B =\frac {1+\sqrt 2}{2}
\end{cases}$
Ta thấy $\alpha, \beta $ đối xứng, $A, B$ cũng vậy, nên đặt $\alpha=1+\sqrt 2, \beta=1-\sqrt 2, A =\frac {1+\sqrt 2}{2}, B =\frac {1-\sqrt 2}{2}$.
Lúc này khai triển của $G(x)$ có dạng :
$\begin {align*}
G(x)=\frac {1+x}{1-2x-x^2}&=(A+B)+(A\alpha+B\beta)x+(A\alpha^2+B\beta^2)x^2+...\\
&=1+\left( \frac {(1+\sqrt 2)^2}{2}+ \frac {(1-\sqrt 2)^2}{2} \right) x+\left( \frac {(1+\sqrt 2)}{2}(1+\sqrt 2)^2+ \frac {(1-\sqrt 2)}{2}(1-\sqrt 2)^2 \right) x^2+...
\end{align*}$
Do đó :
$$\boldsymbol {T_n=\frac {(1+\sqrt 2)^{n+1}+(1-\sqrt 2)^{n+1}}{2}}$$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 29-03-2023 - 00:05
Lỗi $\LaTeX$ thôi mà align lồng trong cases!